Perl Weekly Challenge: Week 114
Challenge 1:
Next Palindrome Number
You are given a positive integer
$N.Write a script to find out the next
Palindrome Numberhigher than the given integer$N.
Example
Input: $N = 1234
Output: 1331
Input: $N = 999
Output: 1001
To solve this, I started from $N + 1. ($N itself could be a palindrome number but the spec says "higher than
the given integer.") Then for every successive number I checked if it is a palindrome by comparing it to its reverse; which
can be easily produced in Perl with the aptly named reverse() function. If it is a palindrome we can stop and print it out
otherwise we keep going. The rarely seen do...until loop makes this quite succint yet readable.
my $next = $N + 1;
do $next++ until $next == reverse $next;
say $next;
In Raku, you use .flip() instead of reverse() as that function is reserved for reversing lists. Other than that, it also comes
in at a sleek three lines of code.
my $next = $N + 1;
do $next++ until $next == $next.flip;
say $next;
Challenge 2:
Higher Integer Set Bits
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.
This was another of those cases where I only had the faintest notion about how to proceed and had to look up the algorithm on the Internet. Luckily this page taught me all I needed to know. My answers are basically a translation of the C++ solution given there.
Perl first. We start by finding the smallest 1 bit in $N which will be the rightmost one. A simple way to do this is by doing
a bitwise AND between $N and its inverse.
my $rightmostOneBit = $N & -$N;
This bit might be part of a sequence of 1's (stretching left.) If it is, we can capture the sequnce by adding $rightmostOneBit
back to $N.
my $nextHigherOneBit = $N + $rightmostOneBit;
and bitwise XORing the result with $N.
my $rightOnesSequence = $N ^ $nextHigherOneBit;
We want all the bits of this sequence except the leftmost, shunted to the right. The next two lines do that.
$rightOnesSequence /= $rightmostOneBit;
$rightOnesSequence >>= 2;
Now when we bitwise OR $nextHigherOneBit and $rightOnesSequence we have the answer and we can print it.
say $nextHigherOneBit | $rightOnesSequence;
Perl uses the same bitwise and shift operators as C/C++ so I was somewhat familiar with them. Raku names them differently, putting
a + in front. Once I overcame that little hurdle translating the Perl code to Raku was simple.
my $rightmostOneBit = $N +& -$N;
my $nextHigherOneBit = $N + $rightmostOneBit;
my $rightOnesSequence = $N +^ $nextHigherOneBit;
$rightOnesSequence /= $rightmostOneBit;
$rightOnesSequence +>= 2;
say $nextHigherOneBit +| $rightOnesSequence;