Reading the punch tape

A telephone exchange takes its night program from a paper tape punched with one long run of letters and no separators. Either the tape splits into commands the exchange knows, or the night shift runs by hand.

The problem

The tape is a single string of lowercase letters. The exchange holds a codebook: a list of command words it recognises. Reading the tape means cutting it into a sequence of codebook commands with nothing left over — no gap, no overlap and nothing hanging off either end.

A command may be punched any number of times on one tape, or not at all.

Report whether the tape is readable. Where the cuts fall does not matter.

Input. tape — a string of lowercase letters. codebook — a list of distinct lowercase command strings.

Output. True if the whole tape splits into codebook commands, False otherwise.

Example.

tape = "openlineholdline", codebook = ["open", "line", "hold"]  ->  True

The cuts fall as open | line | hold | line. line is punched twice, which the codebook allows.

Example, where reading greedily goes wrong, and one that genuinely fails:

tape = "holdholder", codebook = ["hold", "holder", "holdhold"]  ->  True
tape = "openhold",   codebook = ["open", "hol", "old"]          ->  False

The first tape starts with holdhold, the longest command that fits, and then er is left with nothing to cover it. Cutting the shorter hold first leaves holder, which is a command, so the tape reads. The second tape takes open and then stalls: hol leaves a bare d, and old cannot start where hold does.

Constraints.

• 1 <= len(tape) <= 300
• 1 <= len(codebook) <= 1000
• 1 <= len(command) <= 20
• lowercase letters only; the commands are distinct

Hints

Approach

Brute force

Try every command that matches at the current position and recurse on what is left. The same suffix is re-solved through every route that reaches it: on a 41-character tape of hold repeated with a stray letter at the end, over a codebook of hold, ho and ld, that is about a thousand distinct splits, each walking to the end before failing.

The insight

Whether the rest of the tape can be read depends only on how far along you are, not on which commands got you there.

That turns 2^n splits into n + 1 questions. Write reachable[i] for "the first i characters split cleanly": position i is reachable exactly when some command ends there and the position where that command starts is itself reachable. Because commands are at most 20 characters, only 20 candidate starts have to be tried per position. Overlapping subproblems plus a state that forgets the path is the whole precondition for the table.

Algorithm

1. Put the codebook into a set and record L, the longest command length.
2. Set reachable[0] = True and every other position False.
3. For each cut position from 1 to len(tape):
4. Try spans 1 to min(L, cut). If reachable[cut - span] holds and the slice of that span ending at cut is in the set, mark cut reachable and stop.
5. Return reachable[len(tape)].

Complexity

Time O(n · L) slice lookups, each hashing up to L characters, so around 120,000 character comparisons at the limits. Space O(n) for the flag array, plus the set holding the codebook.

Solution

"""Reading the punch tape — reachable cut positions, filled left to right."""


def solve(tape, codebook):
    """True when the tape splits end to end into codebook commands, reused freely."""
    commands = set(codebook)
    if not commands:
        return len(tape) == 0
    longest = max(len(command) for command in commands)

    # invariant: reachable[i] is True when tape[:i] is exactly some sequence of
    # commands. Position 0 is reachable by cutting nothing at all.
    reachable = [False] * (len(tape) + 1)
    reachable[0] = True
    for cut in range(1, len(tape) + 1):
        for span in range(1, min(longest, cut) + 1):
            if reachable[cut - span] and tape[cut - span:cut] in commands:
                reachable[cut] = True
                break
    return reachable[len(tape)]

TESTS = [
    (("holdholder", ["hold", "holder", "holdhold"]), True),
    (("openlineholdline", ["open", "line", "hold"]), True),
    (("openhold", ["open", "hol", "old"]), False),
    (("hold" * 10 + "x", ["hold", "ho", "ld"]), False),
    (("ringring", ["ring"]), True),
    (("z", ["ring"]), False),
]

Pitfalls

• Reading greedily. Longest-match-first answers False on "holdholder" with ["hold", "holder", "holdhold"], because it commits to holdhold and cannot back out. The tape reads.
• Recursing with no table. The shape is right and the cost is not: the hold-repeated tape re-derives the same dead-end suffix through every route that reaches it, and doubling the tape length doubles the work again.
• Marking a position reachable on a match alone. Checking only that the slice is a command asks whether the pieces appear anywhere rather than whether they line up, and returns True for "openhold" with ["open", "hol", "old"] on the strength of an old that starts mid-word.

Variants

• Stamping the key blanks — the same one-value-per-position collapse, used to count arrangements rather than to decide a yes or no.
• The knapsack family — the unbounded shape this is a case of: commands are items that may be reused, and the tape is the capacity that has to be filled exactly.