The jukebox slip

The jukebox in the corner holds twenty-six tracks. A regular writes a request as a run of track numbers, and last night somebody put a wet glass on the slip.

The problem

Tracks are numbered 1 to 26. A request list is a sequence of track numbers written left to right — the barman feeds them in that order. The numbers were separated by strokes, and the wet glass took every stroke off the paper. What is left is one unbroken run of digits.

Given that run, count how many request lists could have produced it. A list is any sequence of numbers, each between 1 and 26 inclusive, whose digits written end to end give exactly the run on the slip. Two lists are different if they split the digits differently, even when they name the same tracks in a different grouping.

There is no track 0, and nobody writes a leading zero, so a number on the slip is either a single digit 1 to 9 or a two-digit number from 10 to 26.

Input. slip — a string of digits.

Output. The number of request lists that produce the slip. Zero if none does.

Example.

slip = "1214"   ->  5

The five lists are 1·2·1·4, 12·1·4, 1·21·4, 1·2·14 and 12·14.

A second example, where a zero has nowhere else to go:

slip = "1026"   ->  2
slip = "306"    ->  0

In the first, the 0 must join the 1 as track 10, leaving 2·6 or 26. In the second, 30 is over 26 and a lone 0 is not a track, so the slip is unreadable.

Constraints.

• 1 <= len(slip) <= 80
• Every character of slip is a digit 0 to 9
• The answer fits in a 64-bit integer

Hints

Approach

Brute force

Choose independently, at each of the n - 1 gaps between digits, whether a stroke was there; then check every piece is a number from 1 to 26. That is 2^(n-1) splittings — 10^24 at the 80 digits the constraint allows.

The insight

The number of readings of a prefix depends only on the two prefixes just behind it, because the final request eats one digit or two and nothing longer.

Write ways[i] for the number of readings of the first i digits. A reading of ways[i] ends with a one-digit request, in which case the digits before it form any reading counted by ways[i - 1], or with a two-digit request, leaving any reading counted by ways[i - 2]. The two cases are disjoint — they differ in where the last stroke sits — so the counts add rather than overlap. That disjointness is what makes this a sum and not an inclusion-exclusion.

Algorithm

1. Set ways[0] = 1: the empty slip has exactly one reading, the empty list.
2. Set ways[1] = 1 if the first digit is not 0, else 0.
3. For each later position i: start at 0; add ways[i - 1] if digit i is not 0; add ways[i - 2] if the two digits ending at i read 10 to 26.
4. Keep only the last two values as you go; return the final one.

Complexity

Time O(n) — one comparison and two additions per digit. Space O(1); two integers, because the recurrence reaches back exactly two positions.

Solution

"""The jukebox slip — count the readings of a digit run into track numbers 1 to 26."""


def solve(slip):
    # two_back: readings of the prefix ending two digits ago.
    # one_back: readings of the prefix ending one digit ago.
    # The empty prefix has exactly one reading, so two_back starts at 1.
    two_back, one_back = 1, 0 if slip[0] == "0" else 1
    for i in range(1, len(slip)):
        here = 0
        if slip[i] != "0":
            here += one_back                       # last request is one digit
        if 10 <= int(slip[i - 1:i + 1]) <= 26:
            here += two_back                       # last request is two digits
        two_back, one_back = one_back, here
    return one_back

TESTS = [
    (("1214",), 5),
    (("1026",), 2),
    (("306",), 0),
    (("26",), 2),
    (("0",), 0),
    (("100",), 0),
    (("2626",), 4),
    (("7",), 1),
]

Pitfalls

• Counting a lone 0 as a track. On "306" a solution that treats 0 as a single-digit request returns 1 instead of 0. Zero must attach to a 1 or a 2 in front of it or the slip has no reading at all.
• Starting ways[0] at 0. Then a two-digit first request has nothing to build on and "26" returns 1 instead of 2. The empty prefix has one reading, not none.
• Checking only the upper end of a pair. "02" is 2, which is under 26, but it is not a legal two-digit request. Without the >= 10 test, "1026" returns 3 instead of 2.

Variants

• The blurred count card — the same recurrence when some characters are unreadable and stand for any digit 1 to 9.
• Linear DP — where the base cases for counting recurrences come from.