Strobelight: One-Zero-One-Zero

Wherein we visit the upside down world that mirrors our own, where truth becomes false and false becomes true when everything is reflected in the mirror of nothingness.

THE WEEKLY CHALLENGE – PERL & RAKU #69

TASK #1 › Strobogrammatic Number

Submitted by: Mohammad S Anwar

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

ANALYSIS AND DEFINITIONS

The crux of this challenge, turning the output upside down, immediately leads the mind back to grade-school calculator humor, where the crudeness of a seven segment LED displays on a pocket calculator (or cool digital watch) matched the juvenile crudeness of the schoolyard.

What on Earth am I on about? 58008, or BOOBS. There, I said it. Googling that number will provide versions of the contrived story behind the punchline, where the calculator is inverted to reveal the naughtiness. With that out of the way, what does happen when you flip a number upside-down? Technological limitations on the ubiquitous aforementioned display element reduced the resolution of the numbers significantly, so mapping a 5 to an S worked out fine. But the sophistication of real fonts don’t map numbers to either themselves or other numbers nearly so well. At some point we need to decide some general guidelines and draw a line.

There will presumably be some disagreements here. Ultimately it doesn’t matter what rules we choose, as no spacecraft survival is dependent on our answer.

1 2 3 4 5 6 7 8 9 0

As an aside, and I find somewhat surprisingly, there is no Unicode block for a complete upside down font, named <LATIN SAN-SERIF INVERTED> or such. It seems instead that any contrived cleverness such as this: uʍop ǝpᴉsdn is in fact just selecting from the entire corpus for characters with appropriately similar shapes. This resemblance is variable and incomplete over the characters in the alphabet, numbers and symbols, and the best examples, like that above, must be carefully selected for their content. So whereas it would be nice to just present the upside-down numbers in a list like we have above, it can’t just be easily done with a font¹.

Back to the problem at hand, what numbers look like numbers when turned upside-down? Turning one’s head a little sideways at the list above shows that only 0 and 8 are clear candidates, as they are highly symmetrical on both the horizontal and vertical axes. A minimal further effort reveals that 6 inverted maps to 9 and vice versa. So that’s four. What of the 1 you ask? The 1 makes for an interesting case because the short stroke at the top of the shaft isn’t really a serif per se, and is almost always drawn in some form in san-serif fonts, when the bottom serif is omitted. Even that bottom serif malingers sometimes on sans fonts, as it can help to distinguish the glyph from the lowercase l, a common cause for confusion. (Type designers think long and hard about confusion and readability and such.) But it’s also quite true that the stroke is not always present and is not strictly speaking necessary, and there are plenty of examples drawn without. Because four numbers isn’t really very many at all, let’s allow 1. What could possibly go wrong?

Which finally leads us to the numbers 2 and 5. I probably shouldn’t mention it, but at first I thought they would map to each other. But my brain was pulling a trick on me: they approximately map when mirrored on the x-axis, but they are chiral as well, and the action of turning a character upside-down also reverses that character left to right. It is somewhat amazing how the brain can flip familiar text shapes around, allowing one to read things upside down or in a mirror, and sometimes it will quietly fix things without bothering to tell you exactly what it’s done. Such was the case with 5 and 2, for they certainly do not flip over and map to each other.

The case could be made, however, that they might, in a minimal way, map to themselves. For those 7-segment calculator LEDs, this is certainly true. But in anything approaching normal typography this is hogwash. The 2 has a sharp change in stroke that leads to the lower horizontal arm, and really is never drawn without some version of that defining mark. Likewise the number 5 has a horizontal arm along at the top, with a distinct change in direction connecting to the bottom stroke, distinguishing it from the letter S. In each it is that acute angle that serves as an essential quality to the character. I can see the case for making the 2 into a highly stylized 7, but I’m not thrilled with the idea. I say 2 and 5 are out for now, as just being too different to map to themselves on anything that uses more than 7 linear segments to make a digit. If we feel the need we can always add them back. (Spoiler alert: we don’t.)

    .rotate {
      transform: rotate(180deg);
      . . . {add x-platform legacy hacks here}
    }

Method

Because the left side of the number becomes the right when we flip it, the numbers we are looking for share certain similarities with palindromes. As I was able to come up with a regular expression to match palindromes, my first thoughts were trying a variation on that. Or more accurately, it was more along the lines of “… well I’m not going to be able to write a regex to match that weirdness…” Not one to shy from trouble, of course next in the wild internal monolog that courses through my life I found myself saying to the rabbit: “Hold my beer.”

When we say the number is strobogrammatic, the left side of the number matches its transformed equivalent on the right. In a palindrome the left is simply mirrored on the right, in a strobogram the left is both reflected and inverted. So starting with the left side, in order for this to happen that partial string must be composed of only digits from the allowed subset, as discussed above. The paired numbers are exchanged for their mates, the others are left alone with their symmetries, and then the left is reversed to make the complement. There may or may not be a central pivot character, as in a palindrome, but that digit is restricted to only the symmetrical subset of the allowed values.

sub is_strobogrammatic {
    $_[0] =~ m/^([16890]+)[180]?((??{reverse($1=~tr[69][96]r)}))$/ ? 1 : 0
}

So the upshot is I had to prove myself wrong. This regex:

• captures a match of 0 or more approved digits on the left,
• possibly pivots on the subset of those digits in the center, then on the right
• copies that capture, non-destructively transliterating the 6 to 9 and vice versa,
• reverses the return value of this, and
• installs the result into the regex in place of the expression.

Applying this test to a list of candidates will filter out as many strobogrammatic numbers as are in the range provided.

This works well, and the only problem going about things this way is the specified range in the challenge definition. A brute force loop through a million numbers to find matches is no big deal. Looping through a million billion numbers, on the other hand – that’s going to take a while, and I’ve got things to do. What to do?

Returning to the logical breakdown we made earlier for the regex, what if we built a set of combinations from the set of allowed digits and used those values for the left side of the number? We can then apply a transformation and obtain the right half, and create complete numbers with the addition of either an element from the pivot set or not. Numbers of up to 7 digits, with the optional pivot, will yield numbers up to 7 + 1 + 7 = 15 digits long. We have managed our problem space up to 10^15.

The number of solutions can now be calculated, and we can construct every valid number within the range. There are 5 elements in the basic number set {0, 1, 6, 8, 9} and 4 elements in the set {Null, 0, 1, 8} – this represents the allowed pivot values plus the absence of a digit. This yields (5^7) * 4 = 312,500 solutions over the range 1 to 10¹⁵. Perfectly doable.

There is one more difficulty, and that is ordering. If we can carefully make the list unique and numerically sorted from out of the gate, selecting from within a low to high range is trivial. Otherwise we’ll need to sort and check the final list, which with 312500 solutions is a bother.

If we construct combinations using the subsequent values from an already ordered list, the results will remain ordered throughout. The sort of the final number will be entirely determined increments on the by the left side, so the right becomes inconsequential. The last degree of variance is with the central pivot value, which we can make sure again is ordered. But all of this is complicated by our Null pivot value. If the pivot is Null, then all of the values without a pivot will numerically fall before the solution with pivot 0, but after that the following number will have pivot 1, etc. looping through the possible values before incrementing the combination.

What’s happening is the Null pivot creates even length numbers, and adding a positive value to the centerpoint creates odd. The largest 8 digit number will always be less than the smallest 9. To get around this, we construct two arrays, one for even numbered constructions and one for odd. If we iterate through our ordered set of combinations and create all the final numbers for each grouping in a pass, throwing the evens on the even array and the odds on the odd, we only need to add the even array to the output first to keep everything straight. And if we make sure our very first digit isn’t 0, we can just keep pushing solutions onto the output array as we increase the combination length; the shorter solutions will be constructed from shorter stems and be placed on the list before the longer, again keeping everything sorted, and keeping our values unique at the same time. Okay, maybe with these details it does get a little complicated. On the other hand it is nice and efficient to only create proper stereograms.

Perl Solution

[colincrain@boris:~/Code/PWC]$  perl 69_1_stroboscope.pl 5000 10000000
6009
6119
6699
6889
6969
8008
8118
8698
8888
 ... <snip>
9981866
9988866
9990666
9991666
9998666

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

## ## ## ## ## MAIN:

my ($A, $B) = @ARGV;              ## low, high bounds

# the order is the length of the half number that is modified and
# joined to itself, with or without the pivot digit in the
# center. Thus a given order will generate numbers up to 2n+1
# places long, or numbers up to but less than 10^(2n+1) The order
# is calculated to be large enough to create all numbers as large
# as B. As the maximum of the range scales by magnitude 100, the
# largest number created can still be quite a bit larger, but we
# can guarantee it will be large enough and also that none of the
# next larger order will be required. It serves as an upper bound
# to the calculation space.  
my $order  = int(length($B)/2);   

my @list   = (0, 1, 6, 8, 9);
my @center = (0, 1, 8);

my @num    = @list[1..@list-1];   ## remove leading 0
my @stereo = @center;             ## ensures trivial single digit cases

for (0..$order-1) { 
    my @evens = my @odds  = ();   ## reset holding arrays
    
    for my $left (@num) {
        my $right = reverse($left =~ tr/69/96/r);
            push @evens, "$left$right";

        for my $center (@center) {
            push @odds, "$left$center$right";
        }
    }

    push @stereo, @evens, @odds;    ## keeps things sorted
    
    ## add another digit to the working list
    @num = map { my $c = $_; map "$c$_", @list } @num;
}

## output within the specified range
for ( @stereo ) {
    next if $_ < $A;
    last if $_ > $B;
    say $_;

}

Raku Solution

sub MAIN (Int $A = 96, Int $B = 100001) {

    my $order  = ($B.chars/2).Int;    ## numbers up to 10^(2*$order+1) are generated

    my @list   = 0, 1, 6, 8, 9;
    my @center = 0, 1, 8;

    my @num    = @list.tail(*-1);     ## remove leading 0       ## thanks, Liz!
    my @stereo = @center;             ## ensures trivial single digit cases

    for ^$order { 
        my @evens = Empty;
        my @odds  = Empty;   ## reset holding arrays
    
        for @num -> $left {
            my $right = $left.trans( '69' => '96' ).flip;
               @evens.push: ($left, $right).join;

            for @center -> $c {
                @odds.push: ($left, $right).join: "$c";
            }
        }
        @stereo.append: @evens;
        @stereo.append: @odds;
  
        ## add another digit to the working list
        @num = [X~] @num, @list;
    }
    
    for @stereo {
        next when $_ < $A;
        last when $_ > $B;
        .say;
    }
}

TASK #2 › 0/1 String

Submitted by: Mohammad S Anwar

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))

Method

After the analysis of the internal nature of the strobogrammatic numbers previously, the constructor for the sequence S looks remarkably familiar. When we realize the switch() function described is tr[01][10] the resemblance is even keener.

The key difference to make the sequence is the application, in this case the next element in the sequence is defined as a function of the previous. We only need to build a recursive routine to descend down to the base case to get any value we choose.

About that value, it grows exponentially and gets quite large rather quickly. The length L of the string is related to the index in the sequence by the relationship

L(S_n) = 2ⁿ – 1

which means the value for S₃₀ has over a billion characters, specifically 1,073,741,823. The value for S₁₀₀₀ has 10,715,086,071,862,673,209,484,250,490,600,018,105,614,048,117,055,336,074,437,503,883,703,510,511,249,361,224,931,983,788,156,958,581,275,946,729,175,531,468,251,871,452,856,923,140,435,984,577,574,698,574,803,934,567,774,824,230,985,421,074,605,062,371,141,877,954,182,153,046,474,983,581,941,267,398,767,559,165,543,946,077,062,914,571,196,477,686,542,167,660,429,831,652,624,386,837,205,668,069,375 characters, or ~10³⁰¹, which means there are not enough protons in the universe to make the ink to print this string.

Perl Solution

[colincrain:~/PWC]$  perl 69_2_one-zero-zero-one.pl 30
0010011000110110001001110011011000100110001101110010011100110110001001100011011000100111001101110
0100110001101110010011100110110001001100011011000100111001101100010011000110111001001110011011100
1001100011011000100111001101110010011000110111001001110011011000100110001101100010011100110110001
0011000110111001001110011011000100110001101100010011100110111001001100011011100100111001101110010
 ... (snip)

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

## ## ## ## ## MAIN:

my $num = $ARGV[0] // 7;
say S($num);

## ## ## ## ## SUBS:

sub S {
    my $n = shift;
    return '' if $n == 0;
    my $str = S ($n-1);
    return $str . '0' . reverse( $str =~ tr/01/10/r );
}

Raku Solution

sub MAIN ( Int $n = 26) {
    S($n).say;
}

sub S ($n) {
    return '' unless $n;
    my $str = S($n-1);
    $str ~ '0' ~ $str.trans('01'=>'10').flip;
}