# Perl Weekly Challenge 114.

My solutions (task 1 and task 2) to the The Weekly Challenge - 114.

# Task 1: Next Palindrome Number

``````Submitted by: Mohammad S Anwar
You are given a positive integer \$N.

Write a script to find out the next Palindrome Number higher
than the given integer \$N.

Example
Input: \$N = 1234
Output: 1331

Input: \$N = 999
Output: 1001
``````

Given a number `N`, the next palindrome is `P(N+1)`, where `P` is a function that returns the next palindrome not smaller than its argument. I define `P` recursively through the following rules, where `a` and `b` denote digits and `s` a string of digits:

1. `P(a)=a`.
2. `P(ab)=aa` if `a>=b`, i.e., increment the less significant digit to get a palindrome.
3. `P(ab)=AA` where `A=a+1` if `a<b`, i.e., I increment the most significant digit by one and make palindrome.
4. `P(asb)`
1. `=aP(s)a` if `a>=b`, i.e., increment the less significant digit and make a palindrome of the middle digits.
2. `=aP(s+1)a` if `a<b` and `length(P(s+1))=length(s)`, i.e., keep the most significant digit, replicate it in the least significant place and look for the next palindrome for the middle digits.
3. `=A000...A` otherwise, where `A=a+1`, i.e., increment by one the most significant digit and replace the middle digits by zeroes to make the smallest possible corresponding palindrome.

.

``````# Perl weekly challenge 114
#
use strict;
use warnings;
use v5.12;
use Scalar::Util qw(looks_like_number);
use POSIX qw(floor);

foreach my \$N(@ARGV){
die "Usage: ./ch-1.pl n m ... with positive integer arguments"
unless looks_like_number \$N and \$N>=0 and \$N==floor \$N;
say "Input: \$N, Output: ", palindrome(split '', \$N+1);
}
sub palindrome {
my @digits=@_;
return @digits if @digits==1;
return (\$digits) x 2 if @digits==2 and \$digits>=\$digits;
return (\$digits+1) x 2 if @digits==2 and \$digits<\$digits;
return (\$digits, palindrome(@digits[1..@digits-2]), \$digits)
if \$digits>=\$digits[-1];
my @M=palindrome(split('', join('', @digits[1..@digits-2])+1));
return (\$digits,@M,\$digits) if @M==@digits-2;
return (\$digits+1, ((0)x(@digits-2), \$digits+1));
}
``````

Example:

``````./ch-1.pl 1234 999
``````

Results:

``````Input: 1234, Output: 1331
Input: 999, Output: 1001
``````

Other examples:

``````./ch-1.pl 9 19 29 191 1991 1992 2991
``````

Results:

``````Input: 9, Output: 11
Input: 19, Output: 22
Input: 29, Output: 33
Input: 191, Output: 202
Input: 1991, Output: 2002
Input: 1992, Output: 2002
Input: 2991, Output: 2992
``````

# Task 2: Higher Integer Set Bits

``````Submitted by: Mohammad S Anwar
You are given a positive integer \$N.

Write a script to find the next higher integer having the
same number of 1 bits in binary representation as \$N.

Example
Input: \$N = 3
Output: 5

Binary representation of \$N is 011. There are two 1 bits. So
the next higher integer is 5 having the same the number of 1
bits i.e. 101.

Input: \$N = 12
Output: 17

Binary representation of \$N is 1100. There are two 1
bits. So the next higher integer is 17 having the same
number of 1 bits i.e. 10001.
``````

To solve this problem it is enough to transpose the rightmost ‘01’ and to move all the following 1’s to the extreme right.

``````# Perl weekly challenge 114
# Task 2: Higher integer set bits
#
use strict;
use warnings;
use v5.12;
use Scalar::Util qw(looks_like_number);
use POSIX qw(floor);

foreach my \$N(@ARGV){
die "Usage: ./ch-2.pl n m ... with positive integer arguments"
unless looks_like_number \$N and \$N>0 and \$N==floor \$N;
my \$binary="0". sprintf("%b", \$N);
my \$next_binary=\$binary;
#replace least significant 01 to 10 and shift following 1's to the right
\$next_binary=~s/01(1*)(0*)\$/10\$2\$1/;
my \$next_dec=sprintf "%d", oct("0b\$next_binary"); #convert to decimal
say "\$N (\$binary)=>\$next_dec (\$next_binary)";
}
``````

Example:

``````./ch-2.pl `seq 20`
``````

Results:

``````1 (01)=>2 (10)
2 (010)=>4 (100)
3 (011)=>5 (101)
4 (0100)=>8 (1000)
5 (0101)=>6 (0110)
6 (0110)=>10 (1010)
7 (0111)=>11 (1011)
8 (01000)=>16 (10000)
9 (01001)=>10 (01010)
10 (01010)=>12 (01100)
11 (01011)=>13 (01101)
12 (01100)=>20 (10100)
13 (01101)=>14 (01110)
14 (01110)=>22 (10110)
15 (01111)=>23 (10111)
16 (010000)=>32 (100000)
17 (010001)=>18 (010010)
18 (010010)=>20 (010100)
19 (010011)=>21 (010101)
20 (010100)=>24 (011000)
``````
Written on May 24, 2021