Capital test and ambiguous encoding

Proper capitalisation

Task 1 this week gives us a string comprising capital and lower case letters and asks us to determine whether it follows one of these patterns of capitalisation: Challenge, challenge, CHALLENGE.

Generally I steer clear of hard-to-follow one-liners, but this one is fairly simple:

$test =~ m/^[A-Z]?([a-z]*|[A-Z]*)$/ ? 1 : 0;

In words, the string follows the rule if:

• it starts with zero or one capital letter, and
• it continues with either zero or more capital letters, or zero or more lower case letters.

 So that wasn't too hard, was it?

A strange encoding

Task 2 gives us a string of digits and asks us to decode it left to right, assuming 1 means A, 2 means B down to 26 means Z. Of course this is ambiguous, because 11 could mean AA or it could be 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, answers.

The easy way to handle problem 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 one of three things:

• 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(the new $so_far, the new $test)
• or if not, it's found an answer (the new $so_far) which it stores in a global hash, 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, and 
• if there are still more characters in $test then it calls analyse(the new $so_far, the new $test), 
• or if $test is exhausted, it's found an answer (the new $so_far) which it stores in a global hash, 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.