BFS over states: word ladders and padlocks

A word ladder turns one word into another by changing one letter at a time, with every word along the way taken from a list, and asks for the fewest changes. It is a shortest-path problem on a graph that nobody draws: every word is a node, two words are joined when they differ in exactly one position, and a breadth-first search from the start word finds the answer. The same BFS over states solves padlocks, jugs, sliding tiles and board moves, whenever a position can be written down as a value and every move costs the same.

The problem: a ladder of four-letter words

The lesson’s list has 32 words, from lamp and lame to kind and zinc. Three examples:

1. From lamp to fire: 4 changes, through lame, fame and fare.
2. From lamp to kind: 6 changes, for example through lame, lime, line, fine and find.
3. From lamp to zinc: −1, because no word of the list differs from zinc in a single letter.

The brute force: every ladder, and every pair of words

The first idea is to walk every ladder that repeats no word, depth first, and keep the shortest. The run counts them on the lesson’s list and on two smaller lists inside it:

"""Every ladder from lamp to fire that repeats no word, found depth first: the count explodes as the list grows."""

WORDS = ["lamp", "lame", "lime", "limp", "line", "fine", "fire", "fare", "fame", "came", "cane", "lane", "mane",
         "mine", "mire", "wire", "wine", "wise", "rise", "rite", "fate", "gate", "game", "gale", "male", "mile",
         "mild", "wild", "wind", "kind", "find", "zinc"]


def one_change(a, b):
    return sum(x != y for x, y in zip(a, b)) == 1


def every_ladder(words, start, target):
    """(number of ladders, fewest changes, calls made): a depth-first walk over ladders without repeats."""
    nearby = {w: [v for v in words if one_change(w, v)] for w in set(words) | {start}}
    ladders, fewest, calls = 0, None, 0
    on_ladder = {start}

    def walk(word, changes):
        nonlocal ladders, fewest, calls
        calls += 1
        if word == target:
            ladders += 1
            fewest = changes if fewest is None else min(fewest, changes)
            return
        for nxt in nearby[word]:
            if nxt not in on_ladder:
                on_ladder.add(nxt)
                walk(nxt, changes + 1)
                on_ladder.discard(nxt)

    walk(start, 0)
    return ladders, fewest, calls


print("words in the list   ladders from lamp to fire   fewest changes   calls")
for size in (22, 27, 32):
    keep = WORDS if size == 32 else [w for w in WORDS if w not in (
        ("wise", "rise", "rite", "gate", "fate") + (("mane", "cane", "came", "game", "gale") if size == 22 else ()))]
    ladders, fewest, calls = every_ladder(keep, "lamp", "fire")
    print(f"{len(keep):>15} {ladders:>27,} {fewest:>16} {calls:>9,}")
n = 50_000
print(f"comparing every pair of {n:,} words to find the neighbours: {n * (n - 1) // 2:,} pairs")

words in the list   ladders from lamp to fire   fewest changes   calls
             22                         599                4     3,087
             27                      26,091                4   152,822
             32                     146,590                4   993,929
comparing every pair of 50,000 words to find the neighbours: 1,249,975,000 pairs

Five more words multiply the count: 599 ladders on 22 words, 26,091 on 27 and 146,590 on 32, almost a million calls for a list that fits on a postcard. Even a search that visits each word once has a second cost hidden in it: finding a word’s neighbours by comparing it with every other word costs 1,249,975,000 pair comparisons on 50,000 words.

What to notice

The graph does not have to exist before the search. Each word’s neighbours can be produced when the search needs them: change each of the L positions to each other letter and look the result up in a set, or file every word under the L patterns that blank one of its positions, such as l*mp, so that the words sharing a pattern are exactly the neighbours through that position. Then the search touches each word once, and the fewest changes is the BFS distance. Padlocks work the same way: each code is a node, and turning one wheel one step up or down gives its neighbours.

Neighbours on demand: three ways, counted Pro: opens with a Pro, Premium or Ultimate pass