RogerBW's Blog

Perl Weekly Challenge 114: Going Higher 27 May 2021

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 (011110).

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.


  1. Posted by Paul Blackwell at 05:47pm on 27 May 2021

    `palindromicity'?

  2. Posted by RogerBW at 03:56pm on 01 June 2021

    For part 1, About half the bloggers did a straightforward search; the rest used some generative system like the one above to reduce the search space.

    Similarly for part 2, really: one can increment and test, or one can build the result directly, and about half the bloggers went for each approach.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 2300ad 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech bayern beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 essen 2024 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1