Every shortest call-sign run

A coastal radio net answers only the signs on its allotment list, so a vessel changing sign has to step through signs that are already allotted.

The problem

A call sign is a string, and every sign in play is the same length. One change alters a single character, and the sign it produces must be allotted, because the net ignores anything else.

Report every shortest run from now to wanted: each run is the signs it passes through, now first and wanted last. Report nothing when wanted is not allotted or cannot be reached. now itself need not be allotted.

Input. now — the sign in use. wanted — the sign asked for. allotted — the signs the net answers.

Output. A list of runs, each a list of signs.

Example.

now = "MG21", wanted = "MB25",
allotted = ["MB21", "MG25", "MB25", "MB29", "ZG21"]
  ->  [["MG21", "MB21", "MB25"], ["MG21", "MG25", "MB25"]]

The ends disagree in two positions, so nothing is shorter than two changes, and either order of the two lands on an allotted sign.

A second example, where a longer run is dropped:

now = "MG21", wanted = "MB29",
allotted = ["MB21", "MB25", "MB29", "MG25"]
  ->  [["MG21", "MB21", "MB29"]]

MG21, MG25, MB25, MB29 is a valid run as well. It is one change longer, so it is not reported.

Constraints.

• 1 <= len(now) <= 8
• 1 <= len(allotted) <= 5000, every sign the length of now
• signs are capital letters and digits

Hints

Approach

Brute force

Walk every ordered sequence of allotted signs and keep the valid shortest ones. With 5,000 signs the sequences of five alone number 5,000^5, about 3.1 × 10^18.

The insight

Record every arrival at a sign on the layer it is first reached, not just the earliest, and the record becomes a small graph whose paths back from wanted are exactly the shortest runs.

A layered search meets a sign at its true distance, so anything arriving during that same layer is on a shortest run too and belongs in the record, while anything arriving later is longer. That is why a sign leaves the unseen set at the end of its layer, not the moment one route touches it.

Algorithm

1. Report nothing if wanted is not allotted; report now alone if it is already the sign wanted.
2. Bucket every allotted sign under each of its dotted patterns.
3. Hold the current layer, starting with now. Look up every pattern of its signs and record, for each unseen neighbour, which signs reached it.
4. Take that whole layer of arrivals out of the unseen set and repeat, until wanted arrives or nothing new does.
5. Walk back from wanted through the record: each way back is one run.

Complexity

Time O(S × L² + R) — each of the S signs is bucketed and expanded once, its L patterns costing a string of length L apiece, plus R for the signs printed. Space O(S × L²) — the buckets and the record.

Solution

"""Every shortest call-sign run — layer outward, then walk every path back."""


def blanked(sign):
    """The sign with one position dotted out, once per position."""
    return [sign[:i] + "." + sign[i + 1:] for i in range(len(sign))]


def solve(now, wanted, allotted):
    unseen = set(allotted)
    if wanted not in unseen:
        return []
    if now == wanted:
        return [[now]]

    buckets = {}
    for sign in unseen:
        for key in blanked(sign):
            buckets.setdefault(key, []).append(sign)

    unseen.discard(now)
    came_from = {now: []}
    layer = {now}
    reached = False
    while layer and not reached:
        arrivals = {}
        for sign in layer:
            for key in blanked(sign):
                for nxt in buckets.get(key, ()):
                    if nxt in unseen:
                        arrivals.setdefault(nxt, []).append(sign)
        # Invariant: a sign first reached in this layer cannot be reached in
        # fewer changes, so every arrival recorded here lies on a shortest run.
        unseen -= set(arrivals)
        came_from.update(arrivals)
        reached = wanted in arrivals
        layer = set(arrivals)

    if not reached:
        return []

    runs = []
    stack = [(wanted, [wanted])]
    while stack:                       # every path back through came_from is a run
        sign, tail = stack.pop()
        if sign == now:
            runs.append(tail)
            continue
        for prev in came_from[sign]:
            stack.append((prev, [prev] + tail))
    return sorted(runs)

TESTS = [
    (("MG21", "MB25", ["MB21", "MG25", "MB25", "MB29", "ZG21"]),
     [["MG21", "MB21", "MB25"], ["MG21", "MG25", "MB25"]]),
    (("MG21", "MB29", ["MB21", "MB25", "MB29", "MG25"]),
     [["MG21", "MB21", "MB29"]]),                       # the four-sign route is dropped
    (("MG21", "MB25", ["MB21", "MG25"]), []),           # the wanted sign is not allotted
    (("MG21", "ZZ99", ["ZZ99", "MB21"]), []),           # allotted but out of reach
    (("MG21", "MG21", ["MG21"]), [["MG21"]]),           # already on the wanted sign
    (("MG21", "MG25", ["MG25"]), [["MG21", "MG25"]]),
    (("A0", "B1", ["A1", "B0", "B1"]), [["A0", "A1", "B1"], ["A0", "B0", "B1"]]),
]

Pitfalls

• Recording one arrival per sign. MB21 and MG25 both reach MB25 on the same layer, so keeping only the first reports one run for the first example instead of two.
• Letting later arrivals into the record. A sign reached on a later layer is on a longer run: admit it and the second example gains the four-sign run.
• Expecting now to be on the allotment list. It is not, in either example. A search that starts by looking now up in the list finds nothing and reports no run at all.

Variants

• Recutting the master key — the same one-character steps, asked only how long the shortest run is.
• The transfer ticket — an equal-cost sweep over pairs rather than places.