Capital test and

ambiguous encoding

Weekly challenge 190 — 7 November 2022

Week 190 - 7 Nov 2022

Task 2

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 1Input: $s = 11 Output: AA, K 11 can be decoded as (1 1) or (11) i.e. AA or KExample 2Input: $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 3Input: $s = 127 Output: ABG, LG Possible decoded data are: (1 2 7) => (ABG) (12 7) => (LG)

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.

- appends it to
- 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.

- if they are in the range 10 to 26, it appends the corresponding character to (the input value of)

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.

#!/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; } } }

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

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain