Task — Decoded List

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.

Examples

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

The complication of this challenge is that the encoding is ambiguous, because 11 could mean AA or it could mean the 11th letter, which is L. So we are to find all the possible decodings and present them in alphabetical order.

If we start at the beginning of the string, the first digit must be 1-9, and that could correspond to A-I. But of course there is an alternative decoding if the first two digits are in the range 10 to 26, that could mean J to Z.

So as we proceed along the string, at each step there are potentially two paths for us to explore, and for a long string that means a large, and initially unknown, number of answers.

The easy way to handle problems like this is recursion. Let's have a subroutine analyse that takes two arguments: $so_far and $test. $so_far contains the answer we have built up already, and $test is the rest of the input string that we haven't got to yet.

Our initial call is therefore analyse('', $test) - we haven't found anything so far and we have the whole of $test to examine.

Subroutine analyse does the following:

• it takes the first digit off $test, converts it to a character,
  • appends it to $so_far
  • if there are still more characters in $test then it recursively calls analyse($so_far, $test)
  • or if not, it's found an answer (the new $so_far) which it stores in %answers, and returns.
• it then takes the first two digits of (the input value of) $test and
  • if they are in the range 10 to 26, it appends the corresponding character to (the input value of) $so_far
  • if there are still more characters in $test then it calls analyse($so_far, $test),
  • or if $test is exhausted, it's found an answer (the new $so_far) which it stores in %answers, and returns.

That will find all the possible decodings of the input string. They are all stored as keys in the hash %answers, and all that remains is to sort the hash by key and output the answers.

However, the task definition is silent about the possibility of input such as 3405. 34 decodes to CD, but neither 0 nor 05 is a defined sequence.

Try it 

Script

#!/usr/bin/perl

# Peter Campbell Smith - 2022-11-07
# PWC 190 task 2

use v5.28;
use utf8;
use warnings;
binmode(STDOUT, ':utf8');

my (@tests, $base, $string, $answer, %answers, $test);

@tests = qw[11 1115 127 16518122051920];
$base = ord('A') - 1;   # so that we can convert a number to a character as $char = chr($base + $number)

# loop over tests
while ($test = shift @tests) {
    
    # analyse the input string
    say qq[\nInput:  $test];
    %answers = ();
    analyse('', $test);
    
    # format and output the answers
    $string = '';
    for $answer (sort keys %answers) {
        $string .= $answer . ', ';
    }
    say qq[Output: ] . substr($string, 0, -2);
}

sub analyse {
    
    my ($so_far, $test, $test_length, $first_two);
    
    # recursively tries taking the first 1 or 2 digits off test and adding them as a character to $so_far
    
    $so_far = $_[0];  # the character string so far
    $test = $_[1];    # the remaining digit string
    $test_length = length($test);
    return if substr($test, 0, 1) eq '0';   # won't happen for a valid $test
    
    # take the first digit of $test and add the corresponding character to so_far
    $so_far .= chr($base + substr($test, 0, 1));
    
    # if anything remains in $test, analyse(the new $so_far, the rest of $test)
    if ($test_length > 1) {
        analyse($so_far, substr($test, 1)) if length($test) > 1;
        
    # else we've exhausted $test and found an answer
    } else {
        $answers{$so_far} = 1;
        return;
    }
    
    # if $test is >= 2 digits and they are 10-26 then add them as a character to $so_far
    $so_far = $_[0];
    $first_two = substr($test, 0, 2);
    if ($test_length >= 2 and $first_two ge '10' and $first_two le '26') {
        $so_far .= chr($base + $first_two);
        
        # if anything remains in $test analyse(the new $so_far, the rest of $test)
        if (length($test) > 2) {
            analyse($so_far, substr($test, 2));
            
        # else we've exhausted $test and found an answer        
        } else {
            $answers{$so_far} = 1;
            return;
        }
    }
}

Output

Input:  11
Output: AA, K

Input:  1115
Output: AAAE, AAO, AKE, KAE, KO

Input:  127
Output: ABG, LG

Input:  16518122051920
Output: AFEAHABTEAIT, AFEAHABTEST, AFEAHLTEAIT, AFEAHLTEST, AFERABTEAIT, AFERABTEST, AFERLTEAIT, AFERLTEST, PEAHABTEAIT, PEAHABTEST, PEAHLTEAIT, PEAHLTEST, PERABTEAIT, PERABTEST, PERLTEAIT, PERLTEST