Making A Rare Hash of It

Wherein we say confuse scarcity for value

THE WEEKLY CHALLENGE – PERL & RAKU #102

---

episode one:
“Maybe Nobody Want Them”

---

Task 1

Rare Numbers

Submitted by: Mohammad S Anwar

You are given a positive integer $N.

Write a script to generate all Rare numbers of size $N if exists. Please checkout the page for more information about it.

Examples

(a) 2 digits: 65
(b) 6 digits: 621770
(c) 9 digits: 281089082

Method

Checking a candidate for what Gupta calls “rareness” is a pretty straightforward operation: take the number, reverse its digits, then alternately add and subtract the reversed version from the original. If both the sum and the difference are perfect squares, then you have found a rare number.

If you do this 100 times, then you will find the number 65 fits the bill. Ok, now do it a hundred billion times. Ahh, there’s the rub, and we’re only up to ten digits.

There’s nothing in the task specification indicating any sort of time constraints on the solution. So, if we implement the above steps in a loop, trying a value and then adding 1 and trying again, eventually we will find any rare numbers we require. Empires may rise and fall, the seas may dry up, the Sun may no longer burn, but eventually, save the coming of the heat-death of the universe, we will get our answer.

So really, the focus shifts to an unbounded problem of optimization: How far are we willing to go? How many digits can we reasonably compute?

Mr. Gupta claims to have constructed a program capable of computing values up to 10²³, but perhaps wishing we should draw some favorable associations with Fermat, declines to publish it. He does, however, list a number of properties of the rare numbers that we can draw on to limit the candidates to check. There are also some known properties of perfect squares suggested, that can further filter out some expensive calculations. Rather than paraphrase all his collected commentary, I’ll leave you the link and just refer to that.

One last note, though: As there are known to be an infinite number of rare palindromes, it’s an interesting thought experiment to consider the ramifications of calling anything that there is an infinite quantity of “rare”. Of course the idea does make sense, and even has practical applications, but I would argue the whole matter is rather profoundly weird.

PERL 5 SOLUTION

Let’s start by making the broad statement that fast as Perl may be, using an interpreted language for this sort of massive raw computation is just foolish. There is a reason Mr. Gupta chose FORTRAN I assume, for same reason it persists to this day among certain scientific data-crunching adherents: it’s fast — very, very fast — at numerical processing.

Perl, in all the joy of expressiveness it brings to the table, is just ill-suited. Of course it can be used to attack the problem, but will always run up against certain walls when processing 10 billion numbers.

The biggest optimization is limiting the first digit to 2,4,6, or 8, and advancing the iterator one at the outer order of magnitude rather than a simple next. This cuts the number of iterations 55% immediately at the cost of the performing one substr on the test value.

After this, however, it becomes a trade-off on doing more expensive substr operations, poking about at extracting individual digits, and the associated conditionals to determine whether to jump to the next iteation, against the rather expensivve sqrt operation to check for perfect squares.

Needless to say the gains in jumping over a hundred million values are quite a bit more obvious than short-circuiting out to the next incremental candidate.

Unfortunately the further “optimizations” given were not as effective, ultimately becoming a tradeoff between the iterations and expensive computation saved versus the added overhead of implementation, leading to diminishing returns.

The next set of properties, of examining the relationships between the first and last digits, yielded quite good results, reducing the number of square root operations about 5 times further. At this point the iterations for a 4-digit value have been reduced from 8999 to start (numbers between 1000 and 9999), to 4399 after filtering for even lead digits, to about 800 after skipping impossible combinations of first and last digits.

Simply short-circuiting out of an invalid combination of digits did not, however, produce much gain in computation time. Using next did not change the actual number of iterations, only avoiding further intensive computation within a given loop. The substr operations to gather the relevant digits and the the added complexity ate in to any effort saved, resulting in only a small time reduction.

The potential gains were not truly realized until I managed to not just short-circut the loop but reconfigure things entirely to skip whole blocks of values in the incrementation phase, essentially unrolling the large pattern of allowed values over each set of permissable combinations. This required a new counter for the tens place that allowed proper rollovers between the sets.

This was pretty tedious work, but paid off in a nearly fourfold increase in execution speed.

Further implementation of the second and second-to-last digits was not nearly as effective. In the end the reduction was minimal and all the unrolled incrementation was, well let’s just say “tedious” no longer covered it.

It felt a lot like coding in assembler, to be honest, so rather than attempt to refine it further it was clear there would be no more orders of magnitude available to trim ahead of us. I threw in the towel at 10-digit numbers, taking 509 seconds to find the 2 rare numbers there.

As for the abandoned next level of complexity, unrolling these loops could be done, but would be maddening, and the only way to see any gains.

Here’s an example of one of Gupta’s derived properties, which we use to optimize a number in the form AB…(digits)…PQ

If A == 8 then Q == 2, 3, 7 or 8: 
    if Q = 2 then: 
        B + tens == 9, 
    if Q = 3 then:
        B - tens == 7  when B > tens 
        B - tens == -3 when B < tens 
        B can never be equal to tens, 
    if Q == 7 then:
        B + tens == 11 when B > 1 
        B + tens == 1  when B < 1, 
    if Q == 8 then B == tens.

This particular rule didn’t make the final cut, but I left the implementation in a commented-out, rejected section.

I think of my optimization strategy as kind of like stripping out the back seat, bumpers and the door panels of your hot rod to save weight.

use warnings;
use strict;
use feature ":5.26";

my $then = time;

my $order = shift @ARGV || 9;

my $test = 10**($order-1);
my $end  = 10**$order;
my @out;

my $tens = 0;

while ($test < $end) {
    
    my $A = substr $test, 0, 1;
    if ($A % 2 == 1) { 
        $test += 10**($order-1);
        next;
    }

    my $Z = substr $test, -1, 1; 

    ## 2s
    if ($A == 2 and $Z == 0) {
        $test += 2;
    }
    elsif ($A == 2 and $Z > 2) {
        if ($tens == 9) {
            $test += 7;
            $tens = 0;
            next;
        }
        $test += 9;
        $tens++;
    }
    
    ## 4s
    if ($A == 4 and $Z > 0) {
        if ($tens == 9) {
            $test += 9;
            $tens = 0;
            next;
        }
        $test += 9;
        $tens++;
    }

    ## 6s 
    if ($A == 6 and $Z == 1) {
        $test += 4;
    }
    elsif ($A == 6 and $Z == 6) {
        if ($tens == 9) {
            $test += 4;
            $tens = 0;
            next;
        }
        $test += 4;
        $tens++;
    }

    ## 8s
    if    ($A == 8 and $Z == 0) {
        $test += 2;
    }
    elsif ($A == 8 and $Z == 4) {
        $test += 3;
    }
    elsif ($A == 8 and $Z == 9) {
        if ($tens == 9) {
            $test += 1;
            $tens = 0;
            next;
        }
        $test +=3;
        $tens++;
    }

    
## the second and second-to-last optimizations, not yet unrolled:
## 333 seconds for order == 9    
# 
#     my $A = substr $test, 0, 1;    
#     $A % 2 == 1 and $test += 10**($order-1);
#     
#     my $B = substr $test,  1, 1;
#     my $P = substr $test, -2, 1;
#     my $Q = substr $test, -1, 1;
# 
#     if ($A == 2)    {
#         next if $Q != 2;
#         next unless ($B - $P) % 2 == 0;
#     } 
#     elsif ($A == 4) {
#         next if $Q != 0;
#         next unless abs(($B - $P) % 2) == 1;
#     } 
#     elsif ($A == 6) {
#         next unless ($Q == 0 or $Q == 5);
#     } 
#     else {                                      ## $A == 8
#         if    ($Q == 2) {
#             next unless $B + $P == 9;
#         }
#         elsif ($Q == 3) {
#             next if $B == $P;
#             if ( $B > $P ) {
#                 next unless $B - $P == 7;
#             }
#             next unless $B - $P == -3;
#         }
#         elsif ($Q == 7) {
#             if ($B > 1) {
#                 next unless $B + $P == 11;
#             }
#             if ($B == 0) {
#                 next unless $P == 1;
#             }
#         }
#         elsif ($Q == 8) {
#             next unless $B == $P;
#         }
#         else {
#             next;
#         }              
#     }

    my $rev = reverse $test;
    if (    $test == $rev 
         or $test - $rev < 0
         or int(sqrt($test-$rev))**2 != ($test-$rev)
         or int(sqrt($test+$rev))**2 != ($test+$rev)  ) {
                $test++;
                next;
    }

    push @out, $test;
    $test++;
}

---

episode two:
“Quite the Hash of It”

---

task 2

Hash-counting String

Submitted by: Stuart Little

You are given a positive integer $N.

Write a script to produce Hash-counting string of that length.

The definition of a hash-counting string is as follows:

1. the string consists only of digits 0-9 and hashes, ‘#’
2. there are no two consecutive hashes: ‘##’ does not appear in your string
3. the last character is a hash
4. the number immediately preceding each hash (if it exists) is the position of that hash in the string, with the position being counted up from 1

It can be shown that for every positive integer N there is exactly one such length-N string.

Examples:

(a) "#" is the counting string of length 1
(b) "2#" is the counting string of length 2
(c) "#3#" is the string of length 3
(d) "#3#5#7#10#" is the string of length 10
(e) "2#4#6#8#11#14#" is the string of length 14

Method

This seems complex, but a simple strategy makes all that weirdness fall away, revealing a quite compact solution: we solve the whole thing in reverse.

We start with the third rule, that the very last character is a hash. This fixes one known character in the string, and so makes a good starting point. From rule 2 we then know the character before that cannot be a hash, so we must instead have a number. As we know the overall string length, then it immediately follows that that number is the length of the string. So far so good: we have successfully constructed a number-hashmark couplet at the end of our string. The big leap is then to realize that the substring before what we’ve just filled in is just another slightly shorter hash-string, and we can repeat the process unaltered.

Either by looping or recursion we will soon find ourselves at the beginning of the string, writing in segments from the back forward. The only remaining challenge is to know when to stop.

PERL 5 SOLUTION

We use a loop to add position-hashmark couplets, keeping a counter until we’ve runt out of string. When the position is down to 0 or 1 we exit the loop, either adding the final hash at the beginning or not.

 1 -> #
 2 -> 2#
 3 -> #3#
 4 -> 2#4#
 5 -> #3#5#
 6 -> 2#4#6#
 7 -> #3#5#7#
 8 -> 2#4#6#8#
 9 -> #3#5#7#9#
10 -> #3#5#7#10#
11 -> 2#4#6#8#11#
12 -> #3#5#7#9#12#
13 -> #3#5#7#10#13#
14 -> 2#4#6#8#11#14#
15 -> #3#5#7#9#12#15#

Here’s the code:

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

for (1..32) {
    say sprintf "%2d -> %s", $_, get_hash_string( $_ );
}

sub get_hash_string ( $num ) {
    my $str = '';
    
    while ( my $pos = $num - length $str )  {
        $str = '#' . $str;
        return $str if $pos == 1;
        $str = $pos . $str;
    }
    
    return $str;
}