Capital letters decoded!

Weekly Challenge 190

Challenge, My solution

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

Task 2: Decoded List

Task

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