Dig site tiles

Each name could be searched for separately, and a catalogue of three thousand then means three thousand walks over the same tiles. One walk is enough if the names are stored so they can be read together.

The problem

A dig site is mapped as a rectangular grid of stone tiles, each carved with one lowercase letter. A name is traced by starting on any tile and stepping to a tile sharing an edge — up, down, left or right, never diagonally — so the letters spell the name in order. No tile may be used twice within one name, but each name starts fresh, so two names may reuse the same tiles.

Report which catalogue names can be traced, each once, in catalogue order.

Input. tiles — a list of equal-length strings, the rows of the grid. catalogue — a list of distinct lowercase names.

Output. The traceable names, in catalogue order.

Example.

tiles = ["urne",        catalogue = ["urn", "vase", "axe",
         "avas",                     "spear", "amber", "urns"]
         "xeep",
         "trae"]
  ->  ["urn", "vase", "axe", "spear"]

vase runs v(1,1) → a(1,2) → s(1,3) → e(0,3), turning a corner. amber dies at its second letter; urns gets three tiles in before the s it needs turns out to be nowhere adjacent.

A second example, on the no-reuse rule:

tiles = ["po",         catalogue = ["opal", "pal", "loop", "lap"]
         "al"]
  ->  ["opal", "pal", "lap"]

loop fails: after l → o the second o would have to be the tile just used.

Constraints.

• 1 <= rows, cols <= 12
• 1 <= len(catalogue) <= 3000
• 1 <= len(name) <= 10, lowercase letters only, names distinct.

Hints

Approach

Brute force

Run a fresh trace for each name from every tile. The first step has four neighbours and each later step three, so one name costs O(rows · cols · 4 · 3^(len − 1)) — roughly 10¹¹ steps for a 12 × 12 grid and 3000 names of length 10, with ala re-walked once per name starting with it.

The insight

Put the whole catalogue in one prefix tree and walk the grid once, carrying a tree node beside the tile — the shared prefixes are traced a single time, and a tile whose letter has no child kills every name below it at once.

The reversal is the point: instead of asking "can this name be traced", the search asks "what does this path spell", and the tree answers for all 3000 names in one lookup. It works because the nodes are exactly the distinct prefixes of the catalogue, so a path that has left the tree is one no name extends.

The reuse rule still needs the usual undo. Mark the tile before recursing and restore it after: the ban lasts for one path only.

Algorithm

1. Insert every name into a prefix tree, storing the finished name on its last node.
2. For each tile, call trace(r, c, root).
3. In trace: stop unless (r, c) is on the grid and its letter is a child of the node; otherwise descend to that child.
4. If the child stores a name, record it and clear it so it cannot be recorded twice.
5. Mark the tile used, trace the four neighbours, restore the tile.
6. Return the recorded names in catalogue order.

Complexity

Time O(rows · cols · 4 · 3^(L−1)) for the walk, where L is the longest name, plus O(total catalogue letters) to build the tree. Space O(total catalogue letters) for the tree, plus O(L) recursion depth.

Solution

"""Dig site tiles — grid backtracking against one prefix tree of the whole catalogue."""

END = "$"


def build_tree(catalogue):
    """Nodes are the distinct prefixes; a node carries END only if a name stops there."""
    root = {}
    for name in catalogue:
        node = root
        for letter in name:
            node = node.setdefault(letter, {})
        node[END] = name
    return root


def solve(tiles, catalogue):
    if not tiles or not catalogue:
        return []
    rows, cols = len(tiles), len(tiles[0])
    grid = [list(row) for row in tiles]
    root = build_tree(catalogue)
    found = set()

    def trace(r, c, node):
        # invariant: node is the prefix tree node for the letters already stepped
        # on, and every tile on that path is marked "#", so it cannot be reused.
        if r < 0 or c < 0 or r >= rows or c >= cols:
            return
        letter = grid[r][c]
        child = node.get(letter)
        if child is None:
            return
        if END in child:
            found.add(child.pop(END))   # drop it so one name is reported once
        grid[r][c] = "#"
        trace(r + 1, c, child)
        trace(r - 1, c, child)
        trace(r, c + 1, child)
        trace(r, c - 1, child)
        grid[r][c] = letter             # the ban lasts for this path only

    for r in range(rows):
        for c in range(cols):
            trace(r, c, root)

    return [name for name in catalogue if name in found]

TESTS = [
    ((["urne", "avas", "xeep", "trae"],
      ["urn", "vase", "axe", "spear", "amber", "urns"]),
     ["urn", "vase", "axe", "spear"]),
    ((["po", "al"], ["opal", "pal", "loop", "lap"]), ["opal", "pal", "lap"]),
    ((["a"], ["a", "aa", "ab"]), ["a"]),
    ((["aa", "aa"], ["aa", "aaa", "aaaa", "aaaaa"]), ["aa", "aaa", "aaaa"]),
    ((["ab", "cd"], []), []),
    ((["stone", "hlate", "aoxrd", "rdbnk"], ["shard", "stone", "north", "tax"]),
     ["shard", "stone", "tax"]),
]

Pitfalls

• Not restoring the tile after the recursion returns. It stays marked for the rest of the walk, so names that legitimately cross it vanish: the first example loses spear.
• Recording a name and continuing to search for it. A name is found once per distinct path — spear comes back twice above, and a 2 × 2 grid of a tiles returns aa eight times. Clear the stored name, or collect into a set.
• Returning names in the order they were found. That order depends on which tile the walk started from: the first example yields urn, axe, vase, spear. Filter the catalogue instead.

Variants

• Greenhouse rotation — grid backtracking again, where the branch dies on a constraint set rather than on a missing tree child.
• Drill roster — the same choose/recurse/undo frame at its smallest.