The Woven Lights of Langmere

Personal Rating: Hard

This coding challenge would have been very challenging, if I had not found a specific website that already contained sample code close to what I needed.

The task was this: Say you map the letter A-Z to the numbers 1-26. Then 111 can be decoded as AAA, AK or KA. Find the number of possible decodings for the given input. submit it modulo 1000000007. The input will be a single line with a string of digits and the result should be a single integer with no leading zeroes.

This is the website I found after some research: https://blog.finxter.com/decipher-the-code-5-python-methods-to-count-decode-ways/

I took the code from the website and edited it to suit my needs.

# take in the number
code = input()

def get_count(code: str) -> int:
    if not code or code[0] == '0':
        return 0

    decodings = [0] * (len(code) + 1)           # Create array initialized with 0, with a length of len(code) + 1. decodings[0] is 1, which represents an empty string with 1 way of decoding. decodings[1] represents the number of possible decodings of number 1 etc.
    decodings[0:2] = [1, 1]                     # Set the first two places to 1, since an empty code and the first letter can each only be decoded in one way

    for i in range(2, len(code) + 1):           # For each character in the code (after the first two):
        if code[i-1] != '0':                    # If the previous character is not 0:
            decodings[i] += decodings[i-1]      # Add the value previous to decodings[i] to decodings[i]. In the first case i=2, decodings[1] which is 1, is added to decodings[2], which is 0 at the start.
        if 10 <= int(code[i-2:i]) <= 26:        # If the value of the previous two characters is between 10 and 26 (inclusive):
            decodings[i] += decodings[i-2]      # Add the second last value before decodings[i] to decodings[i]. In the first non-trivial case i=3, decodings[1], which is 1, is added to decodings[3], which is 0.
    return decodings[len(code)]%1000000007      # Return the value in decodings at the index "length of code" %1000000007

print(get_count(code))

This shows the function in the code snipped mathematically.

And here is an example of a manual iteration to explain the concept:

Example: 1111

f(0) = 1
f(1) = 1
decodings = [1, 1, 0, 0, 0]

for f(2), the last value for f(2-1) is valid, so add f(2-1)=1 to f(2).
for f(2), the last two values are valid as number 10-26, so add f(2-2)=1 to f(2).
decodings = [1, 1, 2, 0, 0]

for f(3), the last value for f(3-1) is valid, so add f(3-1)=2 to f(3)
for f(3), the last two values are valid as number 10-26, so add f(3-2)=1 to f(3)
decodings = [1, 1, 2, 3, 0]

for f(4), the final last digit for f(4-1) is valid, so add f(4-1)=3 to f(4)
for f(4), the final last two digits for f(4-2) are valid as number 10-26, so add f(4-2)=2 to f(4)
decodings = [1, 1, 2, 3, 5]

The length of the string is 4 and so the number of combinations now is decodings[4]