Practice: Counting the Readings of a Door Code

Letters sent as numbers 1 to 26 run together, and the count of possible readings needs a state and a recurrence.

Counting the ways a run of digits can be read as letters is a dynamic programme with a one-index state, and this exercise asks you to design it from scratch: the state, the recurrence, the base case and the count for one code.

A friend leaves a note with a door code written as letters turned into numbers, A as 1, B as 2 and so on up to Z as 26, with no spaces between them. The note says 1226. It could be 1, 2, 2, 6, or 12, 26, or several other splits, and each split is a different word. A 0 cannot stand alone, and a two-digit number counts only from 10 to 26.

Work out three things before opening the answer. First, a state: what dp[i] means, in one sentence. Second, a recurrence: how dp[i] follows from smaller entries, looking at the last one or two digits of the first i. Third, the base case, and then the number of readings of 1226. Check the count by listing the readings.

Show the state, the recurrence and the count

The state: dp[i] is the number of ways to read the first i digits. The recurrence looks at how the last letter of a reading ends. It is either the single digit i, allowed if that digit is not 0, which leaves dp[i − 1] ways for the rest, or the two digits i − 1 and i, allowed if they make 10 to 26, which leaves dp[i − 2]. So dp[i] is the sum of the allowed terms. The base case is dp[0] = 1: an empty prefix has one reading, reading nothing, and without it the first two-digit letter would add 0.

A run filled the table for 1226.

Counting the readings of the door code 1226

Input1226

dp[0] = 1, the empty prefix
1. 1i
2. -
3. -
4. -
5. -
dp[i] counts the readings of the first i digits. The empty prefix has exactly one reading, reading nothing, which is the base case that makes the sums work.
dp[1] = 1, just 1
1. 1
2. 1i
3. -
4. -
5. -
The first digit, 1, is a letter on its own, so one reading: A.
dp[2] = 1 + 1
1. 1
2. 1
3. 2i
4. -
5. -
The new digit 2 reads alone, extending each of dp[1]'s readings, and 12 reads as one letter, extending each of dp[0]'s: 1 + 1 = 2.
dp[3] = 2 + 1
1. 1
2. 1
3. 2
4. 3i
5. -
The new 2 reads alone, adding dp[2] = 2 readings, and 22 is a letter, adding dp[1] = 1: 3.
dp[4] = 3 + 2
1. 1
2. 1
3. 2
4. 3
5. 5i
The new 6 reads alone, adding dp[3] = 3, and 26 is a letter, adding dp[2] = 2: 5 readings.

Result5

The count is 5, and the run listed the readings as ABBF, ABZ, AVF, LBF and LZ. The last step is the recurrence at work: the final 6 can be read alone, after any of the 3 readings of 122, or as 26, after any of the 2 readings of 12.

Each entry reads only the two before it, so the count rolls into two variables, as Keeping Only the Entries the Recurrence Reads does for the stalls.

door_code.pypy

def readings(code: str) -> int:
    before_last, last = 1, 1
    for i in range(1, len(code)):
        current = 0
        if code[i] != "0":
            current += last
        if 10 <= int(code[i - 1 : i + 1]) <= 26:
            current += before_last
        before_last, last = last, current
    return last


print(f"1226: {readings('1226')} readings")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

1226: 5 readings

Lines 5 to 8 are the two terms of the recurrence. The time is O(n) and the space O(1). A plain recursion that tries both splits at every digit takes time that grows like the Fibonacci numbers, because a code of all 1s has fib(n + 1) readings and that recursion visits each of them.

← → move through sections and cards