Daily Programmer - Multiple Encoding

MC706.io
DailyProgrammer, Python

From time to time a programming problem comes a long and hardcore nerd snipes me. Today was no different when someone in the phillydev slack posted:

1
2
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the  number of ways it can be decoded.
For example, the message "111" would give 3, since it could be decoded as  "aaa", "ka", and "ak".

Breaking this down, finding all of the possible decodings of a encoded message seemed like a reasonable place to start. I had recently watched this youtube video doing suduko and finding all of the possible solutions recursively.

So my first pass was able to find the first encoded message type, but stopped there.

1
2
3
4
5
6
7
8
9
10
import string 

mapping = {str(i + 1): l for i, l in enumerate(string.ascii_lowercase)}

def find_possible_messages(data: str, msg: str = '') -> str:
    if not data:
        return msg 
    for num, letter in mapping.items():
        if data.startswith(num):
            return find_possible_message(data[len(num):], msg + letter)

So here it looks through all of the possible mappings and when it matches, it recurses on the left. When there is no more data to check, it returns. This gets the first alphabetically matching message: The given example of 111 comes back aaa.

So to not stop after the first, my instinct was to replace return with yield, but then I just ended up with a ton of recursive generators and unwinding was a pain. So I revisited the video so see how he was doing it with Sudoku and it was through the use of global. Not a fan, but I got a working solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import string 

mapping = {str(i + 1): l for i, l in enumerate(string.ascii_lowercase)}

def count_possible_message(encoded: str) -> int:
    global results
    results = []
    def find_possible_messages(data: str, msg: str = ''):
        global results 
        if not data:
            results.append(msg)
            return 
        for num, letter in mapping.items():
            if data.startswith(num):
                find_possible_messages(data[len(num):], msg + letter)
    
    find_possible_messages(encoded)
    return len(results)

Again not a big fan of using global but it worked and it established a pattern; pass the built string into the child stack frame, and if the search is exhausted for a given branch, append the built string to a global list of results. So using the rescursion to do the search, but not using the recursive results to try and return a data structure that has to be parsed to get the final answer.

With the presence of global, I wasnt quite happy with this solution yet, so I tried using a different global esq pattern, default parameters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import string 
from typing import List 

mapping = {str(i + 1): l for i, l in enumerate(string.ascii_lowercase)}

def find_possible_messages(data: str, msg: str = "", results = []) -> List[str]:
    if not data:
        results.append(msg)
        return 
    for num, letter in mapping.items():
        if data.startswith(num):
            find_possible_messages(data[len(num):], msg + letter)
    return results

def count_possible_messages(encoded: str) -> int:
    return len(find_possible_messages(encoded))

This solution was a lot cleaner, but ultimately I traded one antipattern for another; global for the trick mutable defaults. The problem with mutable defaults immedeiately reared its head when I went to add some doctests. The find_possible_messages caches results (that is how it shares it across stacks), but that also means it only works for 1 call, then all the rest still have the results of the previous runs included.

I went to fix this first by making the list instantiation outside of the function, and therefore it would still be passing a reference to the list all the way down, but then the function basically was a procedure to fill a given list with the results, and the side effect driven nature of that made me feel dirty. So in the interest of functional purity, I fell back to the recommeneded workaround for mutable defaults; None. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import string 
from typing import List 

mapping = {str(i + 1): l for i, l in enumerate(string.ascii_lowercase)}

def find_possible_messages(data: str, msg: str = "", results: list = None) -> List[str]:
    """
    Get a list of all possible message a encoded string can be decoded into 
    >>> find_possible_messages('111')
    ['aaa', 'ak', 'ka']
    >>> find_possible_messages('126')
    ['abf', 'az', 'lf']
    """
    if results is None:
        results = []
    if not data:
        results.append(msg)
        return 
    for num, let in mapping.items():
        if data.startswith(num):
            find_possible_messages(data[len(num):], msg + let, results)
    return results

def count_possible_messages(encoded: str) -> int:
    """
    Count the number of possiblities
    >>> count_possible_messages('111')
    3
    >>> count_possible_messages('126')
    3
    """
    return len(find_possible_messages(encoded))

if __name__ == "__main__":
    import doctest 
    doctest.testmod()

Back to functional purity, and a nice and clean signature and all of my tests are passing. This was a fun little problem and thinking recursively is always a challenge.