Simon Green

Posted on

# Capital letters decoded!

## Capital Detection

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

## My solution

This is relatively straight forward task. See if the input string matches the regular expression `^[A-Z]?([A-Z]+|[a-z]+)\$`. Let's break down that expression.

• `^` and `\$` match the start and end of the string
• `[A-Z]?` means that we have zero or 1 capital letter
• `([A-Z]+|[a-z]+)` means the remaining letters are either all upper case or all lower case.

The are multiple other regular expression that are equally as valid. For example `^([A-Z]+|[A-Z]?[a-z]+)\$`. Given that performance isn't really an issue, I don't compare different expressions to see which is the fastest.

## Examples

``````\$ ./ch-1.py Perl
1

\$ ./ch-1.py TPF
1

\$ ./ch-1.py PyThon
0

\$ ./ch-1.py raku
1
``````

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.

## My solution

The first observation I made when approaching this task is that not all numbers can be represented by the letters. If the last digit is 0 and the second last digit isn't one or two, then there isn't going to be any combination of letters that will match.

The first thing I do is create a dict (hash in Perl) called `letter_map`. This has the mapping between numbers and letters (1 is A, 26 is Z). To make life easy, I keep `s` as a string.

There are a variety of ways to solve this. I'm a big fan of recursive functions, and goodness knows I've overused them occasionally in these challenges. But not this time!

Instead, I've gone with the approach of using a stack. While Python does have modules (like queue) to process FIFO queues, I just used a standard list (array in Perl) for this task. Each item in the stack is a tuple (arrayref in Perl) of numbers and letters. The first item in the queue is the original number and an empty string.

I then remove the first item in the queue. If the number string is empty we have a solution, and I add it to the `soutions` list. Otherwise, I'll take one or two numbers off the number, and append the matching letter to the letter part of the tuple. I then append that in the queue. This sequence is then repeated until the queue is empty.

I finally sort the `solutions` list, and print the results.

## Examples

``````\$ ./ch-2.py 11
AA, K

\$ ./ch-2.py 1115
AAAE, AAO, AKE, KAE, KO

\$ ./ch-2.py 127
ABG, LG

\$ ./ch-2.py 170
No solution possible
``````