Perl Weekly Challenge 114: Next Palindrome Number and Higher Integer Set Bits
These are some answers to the Week 114 of the Perl Weekly Challenge organized by Mohammad S. Anwar.
Spoiler Alert: This weekly challenge deadline is due in a few days (May 30, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.
Task 1: Next Palindrome Number
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
Next Palindrome Number in Raku
In theory, we could build directly the next palindrome number from the current one. But there are different situations to cover, depending for example on whether the input number has an odd or even number of digits. Also, there are various edge cases. It is not so easy to be sure you’ve covered all possible cases. The alternative is to check each number in ascending order until you get a match. This brute force approach is much easier and in fact quite efficient for small and moderately large input numbers, as it is in most cases quite fast to find a palindrome larger than a given input number. We’ll use this second approach. We assume here that the input is a correct integer.
use v6;
my $input = @*ARGS[0] // 1234;
for $input .. Inf -> $candidate {
next unless $candidate eq $candidate.flip;
say $candidate;
last;
}
This program displays the following output:
$ raku ./palin.raku
1331
$ raku ./palin.raku 3445
3553
Next Palindrome Number in Perl
We use the same algorithm, except that we use a while loop instead of a for because it is not possible to define an infinite range in Perl.
use strict;
use warnings;
use feature "say";
my $num = shift // 1234;
$num =~ s/^0+//; # remove leading 0s just in case
while (++ $num) {
say $num and last if $num eq reverse $num;
}
This program displays the following output:
$ perl palin.pl
1331
$ perl palin.pl 3554
3663
$ perl palin.pl 075
77
Next Palindrome in Scala
Scala doesn’t have a last or break statement (there is a break method, but it is not very practical). So we will use a while loop with an explicit value incrementation.
object palindrome extends App {
var num = 1234
var found = 0
while (found == 0) {
if (num.toString == num.toString.reverse) {
println(num)
found = 1
}
num += 1
}
}
This program duly prints 1331.
Next Palindrome in Python
import sys
num = int(sys.argv[1])
while (1):
if str(num) == str(num)[::-1]:
print(num)
break
num += 1
Output:
$ python3 palin.py 1234
1331
Task 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.
It is easy to show that we can always find one such number with the same number of bits set to 1 for any strictly positive integer (you can just add a 1 at the front of the binary representation of the number and set any other 1 bit to 0, but that of course does not necessarily yields the next higher integer).
Higher Integer Set Bits in Raku
To count the number of 1 bits, we just add all digits of the binary representation of the input number (in the number_of_1 subroutine). Then we just test all successive numbers larger than the input number until we find one that has the same number of bits set to 1.
use v6;
sub number_of_1 (Int $in) {
my $count = [+] $in.base(2).comb;
}
my $input = @*ARGS[0] // 3;
my $target = number_of_1 $input.Int;
for $input ^.. Inf -> $candidate {
next unless $candidate.Int.&number_of_1 == $target;
say $candidate;
last;
}
This program displays the following output for a few input values:
$ raku ./nextbin.raku 5
$ raku ./nextbin.raku 12 17
$ raku ./nextbin.raku 123 125
Higher Integer Set Bits in Perl
This is essentially a port to Perl of the above Raku program with just a couple of changes: we use a loop to count the bits set to 1 and we use a while loop instead of a for loop
use strict;
use warnings;
use feature "say";
sub number_of_1 {
my $in = shift;
my $count = 0;
$count += $_ for split //, sprintf "%b", $in;
return $count;
}
my $num = shift // 3;
my $target = number_of_1 $num;
while (++ $num) {
say $num and last if $target == number_of_1 $num;
}
This program displays the following output for a few input values:
$ perl nextbin.pl
5
$ perl nextbin.pl 111
119
$ perl nextbin.pl 256
512
Higher Integer Set Bits in Scala
object nextbin extends App {
def number_of_1(in: Int): Int = {
val binlist = in.toBinaryString.toList
var count = 0
for (char <- binlist) {
if (char == '1') count += 1
}
return count
}
var num = 111
val target = number_of_1(num)
var found = 0
while (found == 0) {
num += 1
if (number_of_1(num) == target) {
println(num)
found = 1
}
}
}
This program duly prints 119.
Wrapping up
The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, June 6, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.
I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.