Recutting the master key

A locksmith is converting a lock from one bitting to another. Every bitting on the way must be one the building already uses, so the door keeps working.

The problem

A bitting is the depth of each cut on a key, written as digits: 3142 is a four-cut key. The pinning chart lists every bitting in use, all the same length.

One visit re-pins one position, so it changes one digit, and the bitting it produces must be on the chart — the lock has to open for somebody until the next visit.

Report how many bittings the shortest run from start to target passes through, counting both ends, or 0 if none exists.

Input. start — the bitting on the lock now. target — the bitting wanted. chart — the bittings in use, all the length of start.

Output. The number of bittings in the shortest run, or 0.

Example.

start = "3142", target = "3552",
chart = ["3142", "3152", "3552", "3557", "3542"]   ->  3

3142 becomes 3152, then 3552, deepening one cut each time. Both are on the chart, and the two ends disagree in two positions, so nothing shorter exists. 3557 is listed and never used.

A second example, where the wanted bitting is not in use:

start = "3142", target = "3555",
chart = ["3142", "3152", "3552", "3542"]   ->  0

No visit can produce 3555, because the chart does not list it.

A third example, with no line to walk:

start = "11", target = "33", chart = ["11", "22", "33"]   ->  0

Constraints.

• 1 <= len(start) <= 10, and every bitting has that length
• 0 <= len(chart) <= 5 * 10^3
• every bitting is digits 0 to 9
• start != target, and start need not be on the chart

Hints

Approach

Brute force

Compare every pair to build the graph: 5000 bittings of length 10 is 2.5 × 10⁷ pairs, each a ten-digit comparison, before any search starts.

The insight

Two bittings are one visit apart exactly when blanking the same position makes them equal, so file each bitting under its blanked patterns and read the neighbours off the file instead of comparing pairs.

3142 files under *142, 3*42, 31*2 and 314*. Anything sharing a key agrees everywhere else, so a bucket is exactly a neighbour set. Every visit costs one step, which is the precondition a breadth-first walk needs: the level a bitting is first reached on is its shortest run.

Algorithm

1. Return 0 if target is not on the chart.
2. Map each blanked pattern to the bittings matching it.
3. Queue start at level 1 and mark it seen.
4. Take a level whole. Look up each bitting's patterns; in each bucket return level + 1 on target, else queue anything new and mark it seen.
5. Return 0 once the queue drains.

Complexity

Time O(N · L²) — each of N bittings produces L patterns and building one pattern copies L digits. Space O(N · L²) — those same N · L keys are kept, each L digits long, alongside N · L references to the bittings.

Solution

"""Recutting the master key — level-by-level BFS over blanked-position buckets."""

from collections import defaultdict, deque


def pattern_index(chart):
    """Each blanked pattern to the bittings that match it."""
    index = defaultdict(list)
    for bitting in chart:
        for i in range(len(bitting)):
            index[bitting[:i] + "*" + bitting[i + 1:]].append(bitting)
    return index


def solve(start, target, chart):
    if target not in set(chart):
        return 0                         # no visit can produce an unlisted bitting

    index = pattern_index(chart)
    seen = {start}
    frontier = deque([start])
    level = 1

    while frontier:
        for _ in range(len(frontier)):   # invariant: one whole level is one visit
            bitting = frontier.popleft()
            for i in range(len(bitting)):
                blanked = bitting[:i] + "*" + bitting[i + 1:]
                for nxt in index.get(blanked, ()):
                    if nxt == target:
                        return level + 1
                    if nxt not in seen:
                        seen.add(nxt)    # marked on push, so it is queued once
                        frontier.append(nxt)
        level += 1

    return 0

TESTS = [
    (("3142", "3552", ["3142", "3152", "3552", "3557", "3542"]), 3),
    (("3142", "3555", ["3142", "3152", "3552", "3542"]), 0),
    (("11", "33", ["11", "22", "33"]), 0),     # every listed pair is two cuts apart
    (("3142", "3542", ["3142", "3152", "3552", "3542"]), 2),
    (("31", "32", ["32"]), 2),                 # one visit; start is not on the chart
    (("11", "33", ["13", "33"]), 3),           # start unlisted, two visits away
    (("3142", "3552", []), 0),                 # an empty chart
]

Pitfalls

• Counting visits rather than bittings. The first example is 3, the bittings passed through; the locksmith drives out twice.
• Not checking target against the chart. Treating it as reachable regardless answers 3 on the second example instead of 0.
• Marking a bitting seen when it is popped, not when it is queued. One reachable from several bittings in a level is queued several times and re-expanded.

Variants

• Merging the choir roster — the same grouping by a shared key, joined with union-find rather than walked in levels.
• BFS and DFS — the lesson behind counting levels rather than steps.