laurent_r

These are some answers to the Week 69 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a couple of days (July 19, 2020). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Strobogrammatic Numbers

A strobogrammatic number is a number that looks the same when looked at upside down.

You are given two positive numbers $A and $B such that 1 <= $A <= $B <= 10^15.

Write a script to print all strobogrammatic numbers between the given two numbers.

Example

Input: $A = 50, $B = 100
Output: 69, 88, 96

The first question is: can the digit 1 be part of a strobogrammatic number? Some people handwrite 1 as a simple vertical bar, and some printing fonts also. In most fonts, however, 1 is more complicated than a single vertical bar, including the font used by my text editor to display a 1. So I decided against including 1. This decision does not change the algorithm I’ll use, so it would be very easy to change that and add 1 to the authorized digits..

With this decision made, a strobogrammatic number can only be composed of digits 0, 6, 8, and 9. In addition, the string containing the reversed number must have 0s and 8s in the same position as the original string, and 6s must be replaced by 9s, and conversely.

Strobogrammatic Numbers in Raku

We’ll use some form of brute force: we will loop over all numbers in the range passed to the program, filter out any number containing anything else than 0, 6, 8, and 9, and finally compare each remaining number with the number generated by flipping the input ans substituting 9 with 6 and vice-versa.

use v6;

sub MAIN (Int $i, Int $j where 1 <= $i <= $j <= 1e15) {
    for $i..$j -> $k {
        next if $k ~~ / <-[0689]> /;
        say $k if $k eq $k.flip.map({TR/69/96/});
    }
}

Let’s start by running the program with faulty arguments:

$ raku strobo.raku foo bar
Type check failed in binding to parameter '<anon>'; expected Any but got Mu (Mu)
  in block <unit> at strobo.raku line 1

$ raku strobo.raku 0 5
Type check failed in binding to parameter '<anon>'; expected Any but got Mu (Mu)
  in block <unit> at strobo.raku line 1

$ raku strobo.raku 10 1
Type check failed in binding to parameter '<anon>'; expected Any but got Mu (Mu)
  in block <unit> at strobo.raku line

The error message could be clearer, but the program fails as expected because parameter values don’t match the MAIN subroutine signature. Let’s now run it with correct arguments:

$ raku strobo.raku 1 1000
8
69
88
96
609
689
808
888
906
986

Strobogrammatic Numbers in Perl

We’ll use the same algorithm as in Raku.

use strict;
use warnings;
use feature qw /say/;

for my $k ($ARGV[0]..$ARGV[1]) {
    next unless $k =~ /^[0689]+$/;
    my $i = reverse $k;
    $i =~ tr/69/96/;
    say $k if $i eq $k;
}

Note that input parameter validation (if needed) is very easy and is left as an exercise to the reader.

If we now run it with the same arguments as the last Raku program run, we (fortunately) get the same output:

$ perl strobo.pl 1 1000
8
69
88
96
609
689
808
888
906
986

Task 2: 0/1 Strings

A 0/1 string is a string in which every character is either 0 or 1.

Write a script to perform switch and reverse to generate S30 as described below:

switch:

Every 0 becomes 1 and every 1 becomes 0. For example, “101” becomes “010”.

reverse:

The string is reversed. For example, "001” becomes “100”.

Please follow the rule as below:

S0 = “”
S1 = “0”
S2 = “001”
S3 = “0010011”
…
SN = SN-1 + “0” + switch(reverse(SN-1))

In the original version of the task, it was requested to generate S1000, which is just impossible as the resulting number would have about 1E305 (or 10 to the 305th power) digits, because of the geometric progression (exponential) explosion of the result. That number of digits is much much larger than the number of atoms in the entire universe, so there is just no way it will be stored in the memory of any computer. (Please note that we’re not talking here about the resulting number S1000, but only about the number of digits of that number, i.e. something in the order of the decimal logarithm of S1000.) And, even assuming it were possible to store the number in question, computing S1000 would also take much much much more than the current age of the universe, so all challengers would miss the next Sunday deadline by a very very very large margin.

In fact, even generating S30 turned out to be extremely long, way too long in fact. S20 contains already more than a million digits; running it is quite OK (it runs in about two seconds), but S30 would take days (I gave up and stopped the program when reaching S26 after about a day execution, so that S30 would probably take several weeks). So, for the examples below, I’ll use much smaller input values. Unless, of course, there is a better algorithm, but I fail to figure out one at this point (more on this later).

0/1 Strings in Raku

Rather than printing only the last result (Sxx), I decided to print all intermediate results between S3 and S8, since it makes it possible to check manually the results.

use v6;

sub switch (Str $num) {
    [~] $num.comb.map({$_ eq "0" ?? 1 !! 0});
}

my $prev = '001';
for 3..8 -> $i {
    $prev = $prev ~ "0" ~ switch $prev.flip;
    say "$i $prev";
}

This produces the following output (reformatted to make it look nicer on this blog post):

3 0010011
4 001001100011011
5 0010011000110110001001110011011
6 001001100011011000100111001101100010011000110111001001110011011
7 0010011000110110001001110011011000100110001101110010011100110110
  001001100011011000100111001101110010011000110111001001110011011
8 0010011000110110001001110011011000100110001101110010011100110110
  0010011000110110001001110011011100100110001101110010011100110110
  0010011000110110001001110011011000100110001101110010011100110111
  001001100011011000100111001101110010011000110111001001110011011

We can improve performance using the tr/// operator in the switch subroutine:

sub switch (Str $num is copy) {
    $num ~~ tr/01/10/;
}

Anyway, with a program undergoing such a massive exponential explosion, such small optimizations are probably somewhat pointless.

0/1 Strings in Perl

For the Perl version, I decided to try to get rid of the switch subroutine used in Raku and to use the tr///r operator in a probably quite futile attempt to improve performance.

use strict;
use warnings;
use feature qw /say/;

my $prev = '001';
for my $i (3..8)  {
    $prev = $prev . "0" .  reverse map { tr/01/10/r }  $prev;;
    say "$i $prev";
}

This produces the following output (reformatted to make it look nicer on this blog post):

3 0010011
4 001001100011011
5 0010011000110110001001110011011
6 001001100011011000100111001101100010011000110111001001110011011
7 0010011000110110001001110011011000100110001101110010011100110110
  001001100011011000100111001101110010011000110111001001110011011
8 0010011000110110001001110011011000100110001101110010011100110110
  0010011000110110001001110011011100100110001101110010011100110110
  0010011000110110001001110011011000100110001101110010011100110111
  001001100011011000100111001101110010011000110111001001110011011

Additional Thoughts on 0/1 Strings

If you look carefully at the output, there appears to be repeated patterns. For example, the line for S6 is repeated as the first line of S7 and S8 (not surprisingly, as this is the way the number is constructed), except for the trailing 0, but also as the third line of S8, which is somewhat unexpected. Similarly, the second line of S7 is the same as the second line of S8 (again, by construction) except for the trailing 0, and also the same as the last line of S8, for reasons that are less obvious (and also as the sixth line of S9, not shown above). There are several other repeated patterns (for example S5 is repeated at the beginning of all lines of S6, S7, and S8. Also, the 31 last digits of S6 are repeated at the end of each of the subsequent lines (lines of S7 and s8), except for the trailing digits. This may have to do with the fact that is you apply twice the switch and reverse operations on a sequence of digits, you get back the original sequence. I really don’t have time now to investigate further these patterns, but there might be a way to construct these Sxx numbers that is faster than the recursive definition given in the task specification.

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, July 26, 2020. And, please, also spread the word about the Perl Weekly Challenge if you can.