Counting ways with modulo arithmetic

Counting DP adds up the number of ways to finish instead of keeping the best one, and the counts grow so fast that problems ask for them modulo a prime, usually 1,000,000,007. The table is the easy part. The care goes into three details: counting each way exactly once, keeping every intermediate value inside the integer type of the language, and choosing the base case of an empty rest, which counts as one way. The problem here is a classic of this kind, told in an original form: in how many ways can a run of digits be read as letters?

The problem: a pager that runs letters together

• 2611 has 4 readings: BFAA, BFK, ZAA and ZK, from 2-6-1-1, 2-6-11, 26-1-1 and 26-11.
• 1020 has 1, JT (10-20), because each 0 must be the second digit of its letter.
• 301 has none: neither 30 nor a letter that starts with 0 exists.
• Ten 1s have 89 readings.

The brute force, and why it fails

Read the first letter as one digit or as two, and count every way on from there:

import math


def readings_brute(digits):
    """Reads the first letter as one digit or as two, and every way on from there; counts the calls it makes."""
    calls = 0

    def read_from(i):
        nonlocal calls
        calls += 1
        if i == len(digits):
            return 1  # the whole message has been read: one reading
        found = 0
        if digits[i] != "0":
            found += read_from(i + 1)  # a letter of one digit, 1 to 9
            if i + 1 < len(digits) and 10 <= int(digits[i : i + 2]) <= 26:
                found += read_from(i + 2)  # a letter of two digits, 10 to 26
        return found

    return read_from(0), calls


for digits in ("2611", "1020", "301", "1111111111"):
    count, calls = readings_brute(digits)
    print(f"{digits}: {count} {'reading' if count == 1 else 'readings'} ({calls} calls)")

for n in (10, 20, 25):
    count, calls = readings_brute("1" * n)
    print(f"{n} ones: {count:,} readings, {calls:,} calls")

shorter, current = 0, 1  # exact counts for k - 1 and k ones, starting at k = 0: the empty message has one reading
for _ in range(100_000):
    shorter, current = current, shorter + current
print(f"100,000 ones: an exact count with {int(math.log10(current)) + 1:,} digits")

2611: 4 readings (10 calls)
1020: 1 reading (5 calls)
301: 0 readings (2 calls)
1111111111: 89 readings (232 calls)
10 ones: 89 readings, 232 calls
20 ones: 10,946 readings, 28,656 calls
25 ones: 121,393 readings, 317,810 calls
100,000 ones: an exact count with 20,899 digits

The counts are right and so is the cost: about 2.6 calls for every reading found, and the readings of a run of 1s grow by a factor of about 1.6 per digit, 121,393 for 25 ones. For 100,000 ones the exact count has 20,899 digits, so neither listing the readings nor counting them one call at a time can finish.

What to notice

• The readings of the rest depend only on where the rest starts. In the tree above, the rest 11 is reached twice and counted twice; a table would count it once.
• A 0 can only be the second digit of 10 or 20, so zeros decide which cuts exist at all.
• The counts grow like Fibonacci numbers, which is why the answer is asked modulo a prime, and why every language has to keep its intermediate values inside its integer types.

The table over positions, with zeros handled Pro: opens with a Pro, Premium or Ultimate pass