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:
P(a)=a.P(ab)=aaifa>=b, i.e., increment the less significant digit to get a palindrome.P(ab)=AAwhereA=a+1ifa<b, i.e., I increment the most significant digit by one and make palindrome.P(asb)=aP(s)aifa>=b, i.e., increment the less significant digit and make a palindrome of the middle digits.=aP(s+1)aifa<bandlength(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.=A000...Aotherwise, whereA=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
# Task 1:
#
# See https://wlmb.github.io/2021/05/24/PWC114/#task-1-next-palindrome-number
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[0]) x 2 if @digits==2 and $digits[0]>=$digits[1];
return ($digits[0]+1) x 2 if @digits==2 and $digits[0]<$digits[1];
return ($digits[0], palindrome(@digits[1..@digits-2]), $digits[0])
if $digits[0]>=$digits[-1];
my @M=palindrome(split('', join('', @digits[1..@digits-2])+1));
return ($digits[0],@M,$digits[0]) if @M==@digits-2;
return ($digits[0]+1, ((0)x(@digits-2), $digits[0]+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
#
# See https://wlmb.github.io/2021/05/24/PWC114/#task-2-next-palindrome-number
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;
#convert to binary and add leading 0
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