Where Do We Put the Walls?

Wherein we reflect on where we cleve the world we see into what is a part of us and what is not.

THE WEEKLY CHALLENGE – PERL & RAKU #190 Task 2

---

“Perhaps that’s what I feel, an outside and an inside and me in the middle, perhaps that’s what I am, the thing that divides the world in two, on the one side the outside, on the other the inside, that can be as thin as foil, I’m neither one side nor the other, I’m in the middle, I’m the partition, I’ve two surfaces and no thickness, perhaps that’s what I feel, myself vibrating, I’m the tympanum, on the one hand the mind, on the other the world, I don’t belong to either.”

— Samuel Beckett

---

Decoded List

Submitted by: Mohammad S Anwar

You are given an encoded string consisting of a sequence of numeric characters: 0..9, $s.

Write a script to find the all valid different decodings in sorted order.

Encoding is simply done by mapping A,B,C,D,… to 1,2,3,4,… etc.

Example 1

Input: $s = 11
Output: AA, K

11 can be decoded as (1 1) or (11) i.e. AA or K

Example 2

Input: $s = 1115
Output: AAAE, AAO, AKE, KAE, KO

Possible decoded data are:
(1 1 1 5) => (AAAE)
(1 1 15)  => (AAO)
(1 11 5)  => (AKE)
(11 1 5)  => (KAE)
(11 15)   => (KO)

Example 3

Input: $s = 127
Output: ABG, LG

Possible decoded data are:
(1 2 7) => (ABG)
(12 7)  => (LG)

ANALYSIS

Combinatorially speaking, I’m not sure what the correct term is for the ordered partitioning a string like this, and I’m not exactly sure either on how to phrase the question that would find the answer. Partitions themselves, for instance, assume an unordered set that can be exhaustively rearranged into groups. Here the ordering has meaning and must be preserved, but arbitrary connections can be made between adjacent elements. And analogy of coupling railroad cars on a track comes to mind.

So maybe something in that vein.

However one technically labels the action, though, the mathematics behind the process are actually pretty simple. Each new character up for consideration has only limited choices available to it: either to be included in the previous partition, if any, or become the start of a new partition. Both outcomes, resulting in two diverging partition paths, is also an option. Of note the first character only has no choice, and must initiate a new partition.

So for a list of n items, digits in this case, this constant bifurcation produces n² possibilities when considered without further constraints. Multiplying the result set with every new item after the first results in

(n-1)²

possibilities.

However we will not need to consider nearly all of these, as we are restrained by the fact that valid partitions can only produce the integer values in the range 1 to 26, mapping the complete English alphabet. This removes far more possibilities than it allows.

Thus each partition can only be of length 1 or 2 digits, and should it have two, the first digit can only be 1 or 2. If we put in a condition to check this before constructing these options we can dramatically reduce the number of partition patterns, making it possible for even very large code blocks to be sorted.

METHOD

This sort of open-ended looping calls out for a recursive solution, with each case considered for each new digit as we progress across the input number positionally from left to right. Conditionals are set on each branch which must pass before it is followed. In this way a result set of all possible partitionings is created yielding internal numbering in the range 1 to 26.

A special case must be made for 0, as no letter will map to it in itself but it will required to compose the code numbers 10 and 20. This number can only be concatenated on recursion, resulting in a single case. If it can only form numbers greater than 20 it will neither trigger a new decoded letter as itself or as a compound and will ultimately be ignored. Thus the encoding scheme could throw in random zeros throughout the ciphertext to throw off cryptanalysis’, should that be a priority.

PERL 5 SOLUTION

The solutions given in the form of a decode_partitions() subroutine, that when invoked returns a list reference of possible word translations for the input.

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

## example: 24,000 partitionings possible
my $out = decode_partitions( "1563152118195912152252515211923552095");

sub decode_partitions ( $num ) {
    ## 1 => A, 2 => b, 3 => C, ...  
    my %decode;
    @decode{ 1..26 } = ("A".."Z");
        
    for my $part ( extract_partitions( $num )->@* ) {
        say map {$decode{$_}} $part->@*;
    }
}

sub extract_partitions ( $num ) {
    my $groupings = [];
    
    ## the first partition is always the first character. It may grow later. 
    my @parts = substr $num, 0, 1, '';
    _recurse( $num, $groupings, @parts );

    sub _recurse ( $digits, $groupings, @parts ) {
        if ( length $digits == 0 ) {
            push $groupings->@*, \@parts;
            return;
        }

        my $prev = $parts[-1];
        my $new  = substr($digits, 0, 1);

        ## case make new partition
        if ( $new != 0 ) {
            _recurse( substr($digits, 1), 
                      $groupings, 
                      (@parts, $new) );  
        }
        
        ## case character added to previous partition
        if ( $prev . $new <= 26 ) {
             $parts[-1] .= $new;
             _recurse( substr($digits, 1), 
                       $groupings, 
                       @parts  )
        }
    }

    return $groupings;
}