Well Ain’t That Special

Wherein we ponder the ways we divide out the unique from the multitudes, and consider how much the quotidian really does not repeat itself as much a s the word may suggest…

THE WEEKLY CHALLENGE – PERL & RAKU #195 Task 2

“You’ve made this day a special day, by just your being you. There’s no person in the whole world like you, and I like you just the way you are.” 

― Fred Rogers

Special Integers

Submitted by: Mohammad S Anwar

You are given a positive integer, $n > 0.

Write a script to print the count of all special integers between 1 and $n.

An integer is special when all of its digits are unique.

Example 1:

Input: $n = 15
Output: 14 as except 11 all other integers between 1 and 15 are spcial.

Example 2:

Input: $n = 35
Output: 32 as except 11, 22, 33 all others are special.

ANALYSIS

What makes a number special? Mathematically there is a simple proof that every number is interesting, that was taught to me as a schoolchild many years ago. First, you take any number that we can agree on as interesting: zero is a good one, as it is the only number signifying nothing at all. Or maybe 2, as the smallest prime. Or really any number you like.

Now consider the number next to this value. Well, that number is *right next to* an interesting number, which is in itself interesting. You see where this is going by now, right? And I will posit that any interesting number is special by virtue of its interesting qualities. So all my numbers are special, and I love them all equally. QED.

But are we really taking about numbers, really? Or something more?

A written number is a not exactly just an abstract number, but rather a representation of this concept in a certain specified manner. It is certainly one way we can look at a number, but doesn’t, in this, capture the totality. It is a shadow, a map, describing an outline from a particular point of view.

The chosen manner of representation here is as a decimal expansion, with the spatial symbol placement indicating multiplication by increasing powers of ten. So we are looking, then, a not at number per se, but a written lines of glyphs. Forget about numbers for now. Digits are characters, and what we’re really doing is we’re looking for certain strings where every character is different.

I think it reasonable to say that viewed mathematically the idea is quite complex. There are no simple consistent relationships between the various numerical values for the digits.

Fortunately we don’t really care about the strings as numbers at all, up until the point where the string, viewed as a number, exceeds the given maximum limit, which is about the only easy numerical quality we can check. Perl makes looking at numbers as strings of digits trivial, so it’s a good tool for this job.

METHOD

A brute-force approach would be to check increasing numbers, moving on when a duplicate digit is detected within a number, and compiling a list of all that pass the test. Needless to say this will become very slow with larger numbers, and as we have a total of ten digits available we keep adding new special numbers up to a hard limit of 11 digits. Per the definition then, the largest number we can create will have the largest digits in the largest positions, and that number is 9,876,543,210. Climbing through the last nine billion is going to be quite tedious.

Alternately, we could save some time and throw out any roots that already are not special numbers, growing our list by adding unique digits to existing numbers until we reach out given target. This will in turn require some means of making sure we keep the newly added numbers unique. We’ll need to keep track of the state of the system, either continuously throughout or on-demand as required.

Let’s explore these two options.

A good way to construct arrangements according to a fixed set of incidence rules is to start with a bag of all pemissible elements and remove elements from play as they are used. In this case if we were to have a real bag containing the digits 0 through 9 as physical chits, when we remove one we are assured we cannot draw that one again. Using such a bag we can construct any special number just by drawing chits.

But how do we do that? Well, we could model the act of drawing out a physical chit using a hash table and recursion: with the digits stored as keys in a hash, when we use a digit we can delete that key from the table and pass the altered, smaller table into the next cycle of recursion.

There’s a bunch of hairy edges to this model, however. We will need a large number of separate copies of the table for each go-around, but I think that with the small size of the table this might be ok. We can make a new longer number using each of the remaining available digits for each number of the current longest length, but need to keep the shorter numbers intact at the same time, requiring two pools, one for completed numbers and one for numbers being worked on and available to be lengthened. And we will also need to determine when we can stop recursing. As I said, hairy edges.

All this is kind of unnecessarily complicated, if you ask me. What we really need is just a simple loop, adding digits one at a time. We keep two pools, constructing new numbers from one and then occasionally dumping the results into the other, say at the end of every loop.

And back to out first thought-experiment, keeping a billion bags around probably isn’t exactly healthy. Alternately if we know there are only 10 possible options at most, why not check each of them, but only for exending existing special numbers? As the numbers are a limited subset this will substantically reduce the size of the search space, and a few quick checks will probably outweigh the cost of creating all those bags. Much less confusing, too.

That seems streamlined and more promising.

The focal point of this route is a way to quickly check a candidate digit against the existing values in a number.

Again with the bags — I must have bags on the mind — we can make a bag of digits from an existing number with a single line of code:

my %digits = map { $_ => undef } split '', $num;

Then we can check to see whether a key for a digit is there using exists. This sounds pretty quick, and hash lookups are always in constant time. Long story short, it can calculate every special number in under five minutes on my machine:

$  time perl 195-2-well-aint-that-special.pl 10000000000
8877690

real    4m44.287s
user    4m42.589s
sys    0m1.008s

But wait! That is probably good enough, as it’s a hard upper limit for every special numbers that can exist. There simply aren’t any more. But again we are still constructing ten billion hashes or so, even if we aren’t keeping them around. At the risk of premature optimization I’d think we can probably do better.

We could, for instance, maybe use a regular expression. Ten billion times, give or take.

Hmmm… ok.

The regular expression engine is an artful piece of architecture, but also fundamentally non-trivial. As Neal Stephenson might say, it has infrastructure. Yes this will work wonderfully, and does its magic quite clearly, but still is like sending your car back to the factory to swap out all the the wheels when all you need is some air in a tire. It’s what we say: “a lot of tool for the job”. The analogy of a factory, in fact, is pretty on-point.

It is also, we should note, still faster than making bags, by a significant amount.

There is however a third way that will completely change the game, in the form of the built-in Perl index() function. Given parameters, this searches for a substring within a string, looking from left to right in a single pass, and in doing so avoids almost all of the complexity of the general-purpose regex engine. The results are lightning fast, as it does exactly what we want and nothing more, minimizing extra overhead.

Re-crafting our verification subroutine using index, we get an approximately 11-fold decrease in computational time:

$  time perl 195-2-well-aint-that-special.pl 10000000000
8877690

real    0m25.693s
user    0m25.230s
sys    0m0.429s

I think we’re done here.

PERL 5 SOLUTION

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


my  $input = shift @ARGV // 10_000_000_000;          

my  $count =  make_special( $input );
say $count;

sub make_special ( $max ) {
    my @results = grep { $_ < $max } (1..9);
    my @prev    = @results; 
    my @next;
    for (1..length $max) {
        @next = ();
        for my $base_num ( @prev ) {
            for (0..9) {
                push @next, $base_num . $_ 
                    if allowed_index( $max, $base_num, $_ );
            }
        }
        push @results, @next;
        @prev = @next;
    }
    return @results;
}

## 100_000_000 time ~ 1m05s
sub allowed_bag ( $max, $num, $new ) {
    my %digits = map { $_, undef } split '', $num;
    return 0 if exists $digits{$new};
    return 0 if "$num$new" > $max;
    return 1;
}

## 100_000_000 time ~ 43s
sub allowed_regex ( $max, $num, $new ) {
    return 0 if $num =~ /$new/;
    return 0 if "$num$new" > $max;
    return 1;
}

## 100_000_000 time ~ 6s
sub allowed_index ( $max, $num, $new ) {
    return 0 if index($num, $new) > -1;
    return 0 if "$num$new" > $max;
    return 1;
}