RogerBW's Blog

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.