Combos, convos and cellphones

Wherein we solve to find combinations to the locks, opening our eyes to the hidden texts behind the numbers we look at every day.

THE WEEKLY CHALLENGE – PERL & RAKU #67

TASK #1 › Number Combinations

Submitted by: Mohammad S Anwar

You are given two integers $m and $n. Write a script [to] print all possible combinations of $n numbers from the list 1 2 3 … $m.

Every combination should be sorted i.e. [2,3] is valid combination but [3,2] is not.

Example:

  Input: $m = 5, $n = 2

  Output: [ [1,2], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], [3,4], [3,5], [4,5] ]

Method

I have always enjoyed combinatorics. I once had a great professor on the subject, and apparently it really stuck; to this day I seek out the connections and variations within groups of objects, looking for patterns and dissonance in all of the ways to rearrange them. It’s come to define one of the funny ways my brain works, working through the various connections in the world around me. It’s musical. Generally speaking, it’s fun.

In this case, we are asked to produce very specific lists of numbers, combinations of n elements from the set {1,2,3, … m}. These are specified to be ordered, but as the elements of the set have themselves a natural order, applying that order with a sort should be no problem. Thus the problem isn’t one of permutations, of ordered rearrangements of the set elements, even though ordering is involved. It’s still combinations, with the ordering just pretty way to display the results.

In other words, in permutations (2,3) and (3,2) are different objects, but in combinations they represent the same unordered set. In Set Theory this is known as “n choose k”.

The easy way to do this would be to use a module, like Algorithm::Combinatorics. The combinations() routine available there will do the work for us, and even give us the results sorted and in lexicographical order, exactly as requested.

use Algorithm::Combinatorics qw(combinations);
say "@$_" for combinations([1..$m], $n);

That’s pretty easy. A little less clear but as a one-liner:

[colincrain:~/PWC]$  perl -MAlgorithm::Combinatorics=combinations -e 'print "@$_\n" for combinations([1..$ARGV[0]],$ARGV[1]);' 5 3
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Ok, that is cool, but really, where’s the fun in that? Instead, I decided to do it the hard way.

What if we constructed the combinations out of a looping control flow? We could explicitly add each next element of a given combination from a pool of valid options until we are done. That would work.

Given a range of options for every decision node, it’s pretty straightforward to build a recursive routine to systematically choose every possible path, saving the results as a long list of lists, with the elements of each of the lists recording the decisions taken for that unique path. This is often a useful way to walk trees and graphs, and we have used it quite a bit in earlier weeks. The question, then, lands in selecting the valid ranges for each element. If we can define those we’ve solved it.

Easily said; actually doing this proved a little bit tricky.

Let’s break it down: we’re looking for a range of values that each element can occupy. This range starts, nominally, at the complete list of possible values, (1, 2, 3 … m), but is constrained by the requirements that the list be ordered and that the list contains n elements. For the start of the range, each element must be larger than the element preceding it. That part’s easy. For the end of the range, each element must be small enough so that the list can continue with incrementing elements to completion. For our example three element combination of a list from 1 to 5, the first element cannot be 5, because that leaves no values left to occupy the second place. So the value is constrained by the distance from the end of the list ( …, m-2, m-1, m).

It works out that the maximum value for a given position is the list maximum m, minus the number of elements n (so the last elements can increase up to the max), plus the position from the front of the list counting from 1 (so our restriction diminishes as we approach the end). Once we have the start and ends of the ranges, dependent on the position of the element being added, we can compute exactly only those combinations that are valid, by excluding invalid values before we even start. Works like a dream.

Perl Solution

[colincrain:~/PWC]$  perl 67_1_number_combo.pl 5 3
[[1,2,3], [1,2,4], [1,2,5], [1,3,4], [1,3,5], [1,4,5], [2,3,4], [2,3,5], [2,4,5], [3,4,5]]

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

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



my ($max, $elems) = @ARGV;

($elems > $max or @ARGV < 2) and do {
    say "Usage: ./number_combos.pl max elements
    max cannot be less than # of elements";
    exit };
     
my @list = add_elements( $max, $elems, [[]] )->@*;

say ( "[" . (join ', ', map { "[". (join ',', $_->@*) . "]" } @list) . "]");


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

sub add_elements {
    my ($max, $elems, $list) = @_;    
    return $list if $list->[0]->@* == $elems;
    
    my @newlist = ();
    
    my $pos = $list->[0]->@* + 1;          ## this position, elems of prev list + 1
    
    for my $combo ( $list->@* ) {
        my $prev  = $combo->[-1] // 0;     
        my $start = $prev + 1;             ## value of last elem in list + 1
        my $end   = $max - $elems + $pos;  ## max - length + position
        for ($start .. $end ) {
            push @newlist, [ $combo->@*, $_ ]
        }
    }
    return add_elements( $max, $elems, \@newlist);
}

Raku Solution

In Raku, you get the .combinations() method for free, so it seems a shame not to use it. We already proved we could do the work. Look at this:

sub MAIN ( Int $max = 5, Int $elems = 3 ) {
    .say for (1..$max).combinations: $elems;
}

That’s all there is to it. Nice.

---

---

TASK #2 › Letter Phone

Submitted by: Mohammad S Anwar

You are given a digit string $S. Write a script to print all possible letter combinations that the given digit string could represent.

Example:

  Input: $S = '35'

  Output: ["dj", "dk", "dl", "ej", "ek", "el", "fj", "fk", "fl"].

Method

Years ago, in the dawn of the telephone era, phone numbers were short and easily remembered. As time went on, this new telephone thing caught on, service expanded, and soon the idea of “exchanges” was required, a central hub or clearinghouse to route a group of ten thousand numbers or so. These exchanges were assigned an additional couple of numbers. To aid in remembering these new, longer numbers, a mnemonic was created, with groups of three letters assigned to the numbers 2-9. These in turn were commonly referenced by whole words to avoid confusing similar sounding letters. Which brings us to the popular Glenn Miller number Pennsylvania 6-5000. The word “Pennsylvania” was used for the letters PE, which in turn meant the number 73. So the number dialed was 736-5000, the number for the switchboard at the Pennsylvania Hotel, which held a particularly wining nightclub at the time. I guess when you owned a swanky Hotel in midtown Manhattan you had a little pull when the exchanges were assigned.

One thing about the original numbering system was that it didn’t list the letters “Q” or “Z”. The intent was to provide a mnemonic for the numbers, not to make new words. The letters were picked for the numbers, not the other way around.

After exchanges became just another part of phone numbers, and area codes made them even longer, this method of referring to the first couple of digits fell by the wayside, and the lettering only lived on in advertising, as ways for businesses to make their numbers catchy, clever and easier to remember. It was only with the rise of the cellphone, and their ability to send a text message, that the lettering system rose again. There was suddenly a need to make words out of the phone keyboard. The “Q” and “Z” letters were added to the stack for 7 and 9, respectively, which is why those particular numbers have more letters. I the beginning, you’d push a button repeatedly to scroll through the letters. It was a pain in the ass, but it worked and was a pretty cool to write a short note to someone. A new era was born.

To find out the various way to encode numbers as letter strings, we proceed in a very similar way to the challenge above. A string, although a very different data structure in Perl, can still be considered abstractly as a list of characters. For each number added, there is a list of valid letter options. Only here, instead of appending to a list, we concatenate to a string. As the relationship between numbers and their letter-sets is fixed, the iteration is simplified to a simple lookup rather than a computation. In other ways the logic proceeds the same.

Perl Solution

[colincrain:~/PWC]$  perl 67_2_hooked_on_phonics.pl 45
gj
gk
gl
hj
hk
hl
ij
ik
il

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

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

my $input = $ARGV[0] // '5273';
$input =~ s/\W//g;       ## tolerate phone number formats, strip punct chars
($input =~ /[^2-9]/) and 
    die "only numbers between 2 through 9 can be alphabetized\n";
    
my @digits = split //, $input; 

my %encode = (  2  =>  ["a", "b", "c"], 
                3  =>  ["d", "e", "f"],         
                4  =>  ["g", "h", "i"], 
                5  =>  ["j", "k", "l"],         
                6  =>  ["m", "n", "o"],
                7  =>  ["p", "q", "r", "s"], 
                8  =>  ["t", "u", "v"], 
                9  =>  ["w", "x", "y", "z"]  );                
my $list = $encode{(shift @digits)};

my @list = make_strings(\%encode, \@digits, $list)->@*;
say $_ for @list;

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

sub make_strings {
    my ($encode, $digits, $list) = @_;    
    return $list unless $digits->@*;
    
    my @newlist = ();
    my $digit = shift $digits->@*;
    for my $str ( $list->@* ) {
        for ( $encode->{$digit}->@* ) {
            push @newlist, $str . $_;
        }
    }
    return make_strings( $encode, $digits, \@newlist);
}

Raku Solution

For the Raku version, this is good practice for keeping track of levels of reference in lists of lists, which is always a bit confusing. Note the slip | in

my @list = |%encode{@digits.shift};

which keeps the container being returned from the hash lookup from being tossed into @list as a single element of one list.

sub MAIN ( Int $input = 527  ) {

   my @digits = $input.comb; 

    my %encode = (  2  =>  ("a", "b", "c"), 
                    3  =>  ("d", "e", "f"),         
                    4  =>  ("g", "h", "i"), 
                    5  =>  ("j", "k", "l"),         
                    6  =>  ("m", "n", "o"),
                    7  =>  ("p", "q", "r", "s"), 
                    8  =>  ("t", "u", "v"), 
                    9  =>  ("w", "x", "y", "z")  );  
                    
    my @list = |%encode{@digits.shift};

    @list = make_strings(%encode, @digits, @list);
    .say for @list;

}

sub make_strings (%encode, @digits, @list) {
    return @list unless @digits.elems > 0;
    
    my @newlist;
    my $digit = @digits.shift;
    for @list -> $str {
        for ( %encode{$digit}.list ) {
            @newlist.push: $str ~ $_;
        }
    }
    return make_strings( %encode, @digits, @newlist);
}