## Advent Calendar - December 13, 2022

Tuesday, Dec 13, 2022| Tags: Perl

### |   Day 12   |   Day 13   |   Day 14   |

The gift is presented by `Peter Campbell Smith`. Today he is talking about his solution to “The Weekly Challenge - 190”. This is re-produced for Advent Calendar 2022 from the original post by him.

## 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.
``````

``````#!/usr/bin/perl

# Peter Campbell Smith - 2022-11-07

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

# You are given a string with alphabetic characters only: A..Z and a..z. Write a script to find out if the usage of
# capital letters is appropriate if it satisfies at least one of the following rules:
# 1) Only first letter is capital and all others are small.
# 2) Every letter is small.
# 3) Every letter is capital.

# Blog: https://pjcs-pwc.blogspot.com/2022/11/capital-test-and-ambiguous-encoding.html

my (@tests, \$test);

@tests = qw[Perl PWC PyThon raku   Byron ShakesSpeare miltoN KEATS 123 6-fold Hello! a A];

# loop over tests
while (\$test = shift @tests) {
say qq[\nInput:  \$test\nOutput: ] . (\$test =~ m/^[A-Z]?([a-z]*|[A-Z]*)\$/ ? 1 : 0);
}
``````

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
``````

``````#!/usr/bin/perl

# Peter Campbell Smith - 2022-11-07

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

# You are given a string consisting of a sequence of numeric characters: 0..9.  The string is a concatenation
# of encoded letters A-Z, where A = 1, B = 2 ... Z = 26. Write a script to find the all valid different decodings
# in sorted order. Example: Input: \$s = 11; Ouput: AA, K

# Blog: https://pjcs-pwc.blogspot.com/2022/11/capital-test-and-ambiguous-encoding.html

@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];
analyse('', \$test);

# format and output the answers
\$string = '';
\$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 {
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 {
return;
}
}
}
``````

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.

If you have any suggestion then please do share with us perlweeklychallenge@yahoo.com.

## SO WHAT DO YOU THINK ?

If you have any suggestions or ideas then please do share with us.