## Perl Weekly Challenge 69: Strobogrammatic Numbers and 0/1 Strings

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.

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 `flip`ping 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
``````

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”.
``````

``````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.