I’ve been doing the Perl Weekly
Challenges. The
latest
involved unconventional solutions to numerical problems. (Note that
this is open until 30 May 2021.)
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
.
So the obvious way would be to start at N+1 and test each number for
palindromeness (palindromity?). But instead I wrote a generator for
palindromic numbers. (First check the OEIS
of course, but there doesn't seem to be a handy one there.)
This generator has two modes. In mode 1, it takes an A
-digit number
and reverses it to generate a 2A
-digit number: 123 → 123321. In mode
0, it does the same thing, but without doubling the last digit, to
produce a 2A-1
-digit number: 123 → 12321. So it starts with an
accumulator at 1, in mode 0: that produces just 1..9, all the
(trivial) 1-digit palindromes. Then in mode 1 it runs from 1 to 9
again, generating 11..99, all the 2-digit palindromes. Back to mode 0,
and 10..99 generates 101..999; then in mode 1 10..99 generates
1001..9999. And so on.
Given the input, we take the first half of its digits (rounding up)
and use that to prime the generator. Then run it until we get a
(palindromic) number that's higher than the input.
This is easiest in Perl/Raku where you don't really have to care
whether a thing is a string or an integer.
sub npn {
my $n=shift;
my ($i,$m);
Get the first half of the input, and use it to prime the generator.
my $l=length($n);
if ($l % 2 == 0) {
$i=substr($n,0,$l/2);
$m=1;
} else {
$i=substr($n,0,($l+1)/2);
$m=0;
}
$i--;
Now run the generator repeatedly.
my $pn=0;
while ($pn <= $n) {
my $f=length($i);
$i++;
This is the fiddliest bit. If the number of digits in i
has
overflowed, start a new run in a new mode.
if (length($i) > $f) {
if ($m==0) {
$m=1;
$i=10**($f-1);
} else {
$m=0;
$i=10**$f;
}
}
Actually build the palindromic number.
my $k=reverse($i);
if ($m==0) {
$pn=$i . substr($k,1);
} else {
$pn=$i . $k;
}
}
return $pn;
}
Other languages have other ways of expressing the idea of converting
between strings and integers, and reversing strings, but the code is
basically the same.
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
.
Again, there's an obvious way to do this: calculate the Hamming
weight, and then the
weight of each greater integer until you get a matching one. Python
even has a bit_count()
function, and Perl can do it with unpack
(if you have to use unpack
this is generally a Bad Sign). But
calculating Hamming weight is canonically quite an expensive thing to
do, not to mention something I've done before for these challenges, so
I took a different approach.
So. Consider the input in its binary representation. At some point
there will be at least one occurrence of the pattern "01" (we stick a
leading zero on to be sure). We take the rightmost one of those,
and change it to "10". This resolves test case #1 (011
→ 110
).
However, that's not sufficient. Any other digits to the right of that
rightmost "01" (some number of 1s, and some number of 0s, in that
order, though maybe none of either) get sorted so that the 1s take the
lowest values possible. This resolves test case #2: 01100
becomes
10100
as above, then the last three digits are rearranged to make
10001
.
sub hisb {
my $n=shift;
Get the initial binary representation.
my $s='0'.sprintf('%b',$n);
Search for any leading digits, the rightmost "01", and then any 1s and
0s that might come afterwards.
$s =~ /^(.*?)01(1*0*)$/;
my ($a,$c)=($1,$2);
From that trailing matter, extract the 0s and 1s.
(my $t0=$c) =~ s/1+//g;
(my $t1=$c) =~ s/0+//g;
We parse a binary string using oct
. Because of course we do.
return oct('0b' . $a . '10' . $t0 . $t1);
}
The other languages differ in just how you convert between integer and
string, and how to get the separate 1s and 0s, but the code basically
works the same way.
Full code on
github.