Month: May 2021

Wherein we find a new friend in the arena, who shares the same upstanding principles as we do.

THE WEEKLY CHALLENGE – PERL & RAKU #114

---

episode one:
“A Symmetrical Shiny Disc Above Our Heads”

---

Task 1

Next Palindrome Number

Submitted by: Mohammad S Anwar

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

Method

On first look, I thought this would be more complicated than it would turn out to be. I saw “palindrome” written there and immediately started digging, ending up over at PWC 095 to fetch my palindrome regex, a neat little one-liner I came up with. It had a little dust on it but looked quite serviceable. Armed and ready for action, another look at the problem at hand revealed I might not be needing the regex after all.

You see, the immediate reasoning here is that a palindrome, and here a palindromic number, is constructed from a rigid set of rules: with the least significant digits exactly mirroring the most. The left reflects in the right, and a central pivot digit, if present, can be said to mirror and map to itself. It must read the same forwards as backwards, the essential quality of a palindrome. If we make sure to follow the rules in construction then there’s no need to validate the number we create as we’ll already know it will conform.

So if we are to create our palindrome, how do we go about deciding what to make? As we said, the left side of the number determines the right, and vice-versa. It stands to reason that if we construct a palindrome out of the left half of our base number, then the two values will share the top half of their significant digits. It will have to be in the ballpark. This seems an excellent place to start.

But before we do that, let’s take a slight digression into a what we mean when we ask for the next higher number. Trivially and tautologically, when we have a value in an ascending ordered set of values and we ask for the next highest of these, we’re asking for the next value in the ordered sequence, whatever that may be. If our values are a subset of the whole numbers, as these are, then we inherit the ordering from the whole numbers. Which is to say the numerical comparisons we think of when ordering numbers hold for palindromes as well, as they’re all just numbers in the end. Special numbers, perhaps, but numbers nonetheless.

For example, the comparison 23432 > 12321 holds, just like we assume it would.

When we proceed to the next number in a an ordered sequence of numbers, we increment the least significant digit — the smallest valued digit, in other words the ones place. In a sequence of palindromes, however, the idea of which is the least significant digit itself gets altered. When the tail of the number is fixed by the forward half, the ones position can no longer change without side effects.

The smallest value, therefore, becomes immutably tied to the value of the largest, and to find the next number in the sequence we need to effect the smallest change possible, the smallest increment.

The least significant change we can make to increment the number, then, is to the central pivot digit, if present, or failing that the two central digits, which must be increased together. These are the smallest digits that will change between adjacent palindromic numbers.

So returning to our first course of action: we’ve decided to conform our base number to palindrome status. We construct a palindrome by taking the front half of the number, mirroring a matching tail and gluing them together. The base number and the palindrome will only differ beyond the half-way point in the digit string.

If this number is greater than the base value then we already have the next larger palindrome and we are done. Any decrease in the central pivot, or any higher valued digit position for that matter, will result in a value smaller than the base. If the palindrome we produce is is not, however, larger than the base we will still need a palindrome that is. If we increase the value from the central digit or digits as outlined above we will obtain the next number in the sequence of palindromes. Now the same logic from earlier applies when we increase the pivot value or values: it follows that the base must be lower in value than the new palindrome, as one of the central digits will be smaller and all digits composing the number above that will be same, so it will be ordered beneath the palindrome.

We will devise two ways to make our base into a candidate solution: one to produce the simple palindrome from the base, and one to produce the next palindrome in the sequence. We’ll start looking at the lower and if necessary calculate the larger.

PERL 5 SOLUTION

In Perl we’ll make two routines and a wrapper to call first one, and if necessary the second. The arguments from the command line come in as strings, so a numification step make sure any leading zeros are ignored. The results:

~/Code/PWC/114-1-your-next-pal.pl
--------------------------------------------------------------------------------
Input:  19
Output: 22

And the source:

use warnings;
use strict;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

my $number = shift // 34987;
$number += 0;           ## numification is important

say "Input:  ", $number;
say "Output: ", get_next_palindrome($number);

sub get_next_palindrome ($num) {
    my $base = make_p($num);
    if ($base < $num) {
        return make_inc_p($num);
    }
    return $base;
}

sub make_p ($num) {
    my $len  = length $num;
    my $head = substr $num, 0, $len - int($len/2);
    my $tail = reverse substr $head, 0, $len/2;
    return $head . $tail;
}

sub make_inc_p ($num) {
    my $len  = length $num;
    my $head = substr $num, 0, $len - int($len/2);
    $head++;
    my $tail = reverse substr $head, 0, $len/2;
    return $head . $tail;
}

sub is_palin ($num) {
## from PWC 095, neat but ultimately not used
    return $num =~  m/^(.*).?(??{reverse($1)})$/;
}

raku solution

Raku already gives us some handy routines to smooth our algorithm, such as a built-in ceiling() and floor(). This makes the logic of dividing the number string in half in such a way to accommodate both even and odd numbers considerably simpler. Rolling with this, the logic of the two Perl routines are combined, to only increment the $half value if the resulting palindrome would be too small. The palindrome is constructed from the front half of the number, sized to the ceiling of the split to take the center digit with it, with the reversed floor of the front half, which would leave the center pivot behind. For an even number of digits the floor and ceiling would be the same.

It gets quite compact at the expense of clarity, but it’s nice to see it two ways.

unit sub MAIN ($num = 20001) ;

say next-p( $num );

sub next-p ($n) {
    my $half = $n.substr( 0, ceiling($n.chars/2) );
    $n.substr( *-floor($n.chars/2) ) > $half.substr(0, floor($n.chars/2)).flip
        && $half++;
    $half ~ $half.substr(0, floor($n.chars/2)).flip;
}

---

episode two:
“How Much For the Ham?”

---

task 2

Higher Integer Set Bits

Submitted by: Mohammad S Anwar

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.

Method

The number of 1s in the binary representation of a number is historically known as the population count. It’s certainly an unusual way of looking a number, but it’s been around in computing since the 1950s. Suffice to say it has its uses. The number of 1s in a given sequence of numbers will rise and fall; as numbers get larger there are more places that could be 1s, but on the other hand any power of two will be a single 1 followed by nothing but 0s. The underlying pattern is complex.

We could brute force this task, by creating or borrowing a popcount() function and incrementing until we circle around again, which we know will eventually happen. This approach sounds boring for large numbers but we’re going to reserve the right to fall back on it. It’s a plan, but let’s see if we can do better.

Mathematically, the population count is known as the Hamming weight, or perhaps more accurately a select case of the Hamming weight for binary numbers. The more general Hamming weight counts the non-zero values in a string, against whatever is defined as 0, so for example the weight for the number 43210 is 4, as 4 of the 5 digits are not zero. This could be confusing, so let’s forget about the general case for now. When we talk about “weight” here, or “Hamming weight” let’s understand that we’re always talking about binary strings, not any more general meaning. The Hamming weight of a number will be that of its binary representation, even if we’re talking about it in decimal form. The numbers don’t care how we talk about them; they’re very self-confident that way and know what they are.

The first thing we will do is compare a bunch of binary numbers grouped by their weight. There’s a pattern there, but exactly what that pattern is is… elusive, shall we say.

weight	value	binary	next value same weight
1	1	1	2
	2	10	4
	4	100	8
	8	1000	16
	16	10000	32
	32	100000	64
2	3	11	4
	5	101	6
	6	110	8
	9	1001	10
	10	1010	12
	12	1100	16
	17	10001	18
	18	10010	20
	20	10100	24
	24	11000	32
3	7	111	8
	11	1011	12
	13	1101	14
	14	1110	16
	19	10011	20
	21	10101	22
	22	10110	24
	25	11001	26
	26	11010	28
	28	11100	32
4	15	1111	16
	23	10111	24
	27	11011	28
	29	11101	30
	30	11110	32
5	31	11111	32

Our first observations are:

• when we add one to a number, the weight will increase if the number is even, which we don’t want.
• If the number is odd, then the last bit will carry and the number will become even, and this carrying may or may not trigger a cascading effect. Generally this reduces the weight, or at most leaves it the same.
• If the weight is reduced, we can always add 1 to the number until the weight arrives again at the desired value.

So to review, if we add 1 to any number it will either increase the weight or alternately trigger a carry which will either lower the weight or keep it the same. This behavior will hold true every time we increment the number. A single bit carried forward into a 0 above it keeps the weight the same, as we’ve taken away a single 1 but also have added a 1 above, yielding a neutral result. The only way, it seems, to lower a weight is to trigger a cascade of carries that flip a series of bits together in one incrementation, such as when we roll over into a power of 2: for example the binary value 01111 + 1 = 10000.

It’s not much but it’s a start. Our plan will be to somehow jump ahead over any values with larger weights, straight to a cascading event and then if necessary build the weight up again. We want to avoid ever increasing the weight when we are at weight already. If we were to do that, the only way down again is at a cascading event, so we might as well find that in the first place and go straight to it.

This gives us part of a plan, sort of, but doesn’t solve all of our problems. Sometimes we’ll simply want to add 1, carrying the trailing 1 of an odd number into a vacant 0, keeping the weight that same. But we’re getting closer.

When we add 1 to a number, we add to the least significant binary digit. If that’s a 1, then the number is odd and we’re good, but if it’s a 0 the weight will increase, which is bad. So what if we add the 1 to the least significant 1 instead? This will trigger a carry and the weight will remain the same or lower. If it is the same that will be the next number with the same weight and if it is lower we can build it up again.

This plan indeed works. We construct a function to yield the position of the least significant set bit, and if we add the binary number with 1 at that bit with the rest 0s, then this triggers a carry. That number, conveniently, is 2 raised to the position we found, if it’s all 0-based indexing.

The result of this function is some number equal to or less than the next number with the same Hamming weight, often skipping over a range of values. It can’t, however, be larger and have somehow skipped over our target number, as that would require the the Hamming weight to have gone up and then come cascading down again to equality, and all we’ve done is jump forward to the next carry, which would have been that point.

We’re homing in on it now. As we’ve carried the least significant set bit, the number will now end in a sequence of 0s, one more of these than before. We now need to add as many 1s to that expanse of 0s as required to get the weight correct. Again, we could increment the number and that would eventually work. But if we take the difference between the Hamming weight of the new carried value and our target weight we get the quantity of 1s neccessary to equalize the two. We can then construct a new value from nothing but binary 1s and add that to make up the difference.

The smallest value containing a set number of 1s is a string of 1s of the required length, and the way to construct this number is to raise 2 to that required number of 1s and then subtract 1:

2⁴ – 1 = binary 1111, or 4 × 1s

This corrects the weight difference. Sometimes the number with the carried bit tripped will require no adjustment and the number immediately following will have the same weight, but that’s ok; if the Hamming difference is 0, 2⁰-1 = 0, so nothing is added in the adjustment stage.

In the end our function, to find the next number with the same number of 1s in its binary representation, is to first trigger a carry in the lowest significant set bit and then add a number composed of enough 1s to make up any difference. It works, in two steps, every time.

PERL 5 SOLUTION

~/Code/PWC/114-2-the-weight-of-ham.pl
--------------------------------------------------------------------------------
1         2
2         4
3         5
4         8
5         6
6         9
7         11
8         16
9         10
10        12
11        13
12        17
13        14
14        19
15        23
16        32
17        18
18        20
19        21
20        24
21        22
22        25
23        27
24        33
25        26
26        28
27        29
28        35
29        30
30        39
31        47
32        64

To construct our function we break it down into a set of discreet components as outlined above:

• calculate the Hamming weight
• find the lowest significant set bit position
• construct and add a number to force a carry at that position
• construct a binary number from of a given number of 1s
• take a number, trip the lowest set bit to carry, add as many 1s as required to balance the Hamming weight to that of the input value

We said earlier that the numbers don’t care how we describe them. This is quite true, and leads to the curious observation for an essentially binary process, most of the arithmetic is done in decimal. The relationships between the binary digits remain the same no matter how we represent the numbers, so we can just add them as we would normally.

For this demonstration we’ve eschewed a command line input and simply calculated the first 32 numbers and their following values with the same weight.

use warnings;
use strict;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';
use List::Util qw(sum);

for (1..32) {
    say sprintf "%-8d  %-d", $_,  next_hamming_weight($_);
}

sub next_hamming_weight( $num ) {
    my $ham  = hamming( $num );
    my $trip = trip_carry($num);
    my $next = $trip + ones( $ham - hamming($trip) );
    return $next;
}

sub hamming ($num) {
## given number, returns count of 1s in binary representation
    my $bin  = sprintf "%b", $num;
    my $bits = sum (split //, $bin);
    return $bits;
}

sub trip_carry ($num) {
## given a number, trip the carry on the lowest significant set bit
## 10101000 -> 10110000
    my $ls   = lowsig($num);
    my $trip = 2**$ls;
    return $num + $trip;
}

sub lowsig ($num) {
# returns lowest significant set bit position, 0-based
    return 0 if ! $num;
    my $pos = 0;
    while ( !( $num & 1) ) {
        $num >>= 1;
        $pos++;
    }
    return $pos;
}

sub ones ($count) {
## returns decimal value of binary string composed from $count x 1s 
## ->(3) = 0b111 = 7
    return 2**$count - 1;
}

Raku Solution

In Raku I’ve been playing with encapsulating helper functions within the body of the the functions that use them, minimizing their scope. The whole process is streamlined where we can, albeit, as usual, sometimes at the expense of obvious clarity. We could take many of these refactorings back to the Perl version, but the two represent different coding styles at the moment and I like presenting the difference. Some of the functions in Raku are, as is also usual, notably quite beautiful in their airy simplicity.

unit sub MAIN ( Int $num where $num > 1 = 127) ;

say next_hamming_weight( $num );

sub next_hamming_weight( $num ) {
    my $trip = trip_carry($num);
    return $trip + ones( hamming($num) - hamming($trip) );
    
    sub ones ($count)  { 2**$count - 1 }
    sub hamming ($num) { $num.base(2)
                             .comb
                             .sum   }
}

sub trip_carry ($num) {
## given a number, trip the carry on the lowest significant set bit
    my $ls   = lowsig($num);
    my $trip = 2**$ls;
    return $num + $trip;
    
    sub lowsig ($num is copy, $pos is copy = 0 ) {
    # returns lowest significant set bit position, 0-based
        until $num +& 1 { 
            $num +>= 1;
            $pos++;
        }
        $pos;
    }
}