Filling the grid

A crossword setter has a six-cell slot with two crossing letters fixed and four cells blank. The question is not which entries exist, but whether any fits.

The problem

A setter keeps a word list — the entries they are willing to put in a grid — and adds to it as the puzzle grows. When a slot has some cells settled by crossing entries and the rest blank, the setter asks whether the list holds anything that fits.

A slot is written as a pattern: a lowercase letter where the cell is fixed, a dot where it is blank. A dot stands for exactly one letter, so an entry fits only if it is exactly as long as the pattern and agrees at every fixed cell.

Input. moves — a stream of (move, text) pairs. ("file", entry) adds an entry, lowercase letters. ("fits", pattern) asks whether any entry filed so far matches that pattern, lowercase letters and dots.

Output. A list of booleans, one per fits move, in the order asked.

Example.

moves = [("file", "dagger"), ("file", "danger"), ("file", "ledger"),
         ("fits", "danger"), ("fits", "dodger"), ("fits", "d..ger"),
         ("fits", "..dger"), ("fits", "dagge")]
->  [True, False, True, True, False]

d..ger fits dagger and ..dger fits ledger. dagge is a five-cell slot, and nothing five letters long has been filed.

A second example, where the first branch a dot takes is the wrong one:

moves = [("file", "batten"), ("file", "bitten"), ("file", "bit"),
         ("fits", "bat"), ("fits", "b.t"), ("fits", "b.tten"), ("fits", "bitte")]
->  [False, True, True, False]

b.t sends the dot down the a branch and lands on bat — a real prefix of batten, never filed. The search has to climb back and try i, where bit is.

Constraints.

• 1 <= len(moves) <= 2 * 10^4
• 1 <= len(text) <= 20
• entries are lowercase a-z; patterns are lowercase a-z and .
• total characters filed at most 3 * 10^5

Hints

Approach

Brute force

Keep the entries in a list and walk the pattern against every entry, letter by letter. With 10⁴ entries of 20 letters and 10⁴ queries that is 2 · 10⁹ comparisons, and every query pays again for entries that fail on cell one.

The insight

Entries that share a prefix should be walked once rather than once each, and inside a prefix tree a blank cell costs a branch over the children that exist, not over all 26 letters.

Every distinct prefix is a single node, so a fixed cell is one lookup however many entries lie below it. The precondition the fan-out needs is that matching is positional and left to right: the pattern's j-th character is decided by the j-th letter of the entry alone, so a choice at depth j cannot invalidate one made above it. That is what makes it safe to recurse into a child and, on failure, return to the parent unchanged.

Algorithm

1. Keep a trie: one node per distinct prefix, one child per letter, an end marker on nodes where a filed entry stops.
2. file: walk the entry, creating missing children, then set the marker.
3. fits: walk from the root, stepping to the child named by each fixed letter and reporting no match when that child is missing.
4. On a dot, recurse on the rest of the pattern once per child; a match if any child succeeds.
5. When the pattern runs out, match only if the node carries the marker.

Complexity

Time O(L) per dotless query, L the pattern length, and O(26^d · L) with d dots — bounded by the node count, so no query costs more than one sweep of the tree. Space O(S) for S filed characters, plus L stack frames.

Solution

"""Filling the grid — a prefix tree searched with a dot that fans out over the children."""

# Entries are lowercase letters only, so "#" can never be a real edge and is
# safe as the marker for "a filed entry ends at this node".
END = "#"


def file_entry(root, entry):
    """Add one entry, creating a node for each prefix that does not exist yet."""
    node = root
    for ch in entry:
        node = node.setdefault(ch, {})
    node[END] = True


def fits(node, pattern, i):
    """True when some path down from `node` spells pattern[i:] and stops there."""
    for j in range(i, len(pattern)):
        if pattern[j] == ".":
            # A blank cell matches any single filed letter, so each child is a
            # separate search and a dead branch must leave the others untouched.
            return any(
                fits(child, pattern, j + 1)
                for edge, child in node.items()
                if edge != END
            )
        node = node.get(pattern[j])
        if node is None:
            return False
    return END in node          # reaching a node is not the same as fitting it


def solve(moves):
    root = {}
    answers = []
    for move, text in moves:
        if move == "file":
            file_entry(root, text)
        else:                    # ("fits", pattern), answered against the list so far
            answers.append(fits(root, text, 0))
    return answers

TESTS = [
    # Dots land on either side of a fixed letter; a five-cell slot has nothing to fit.
    (
        (
            [
                ("file", "dagger"), ("file", "danger"), ("file", "ledger"),
                ("fits", "danger"), ("fits", "dodger"), ("fits", "d..ger"),
                ("fits", "..dger"), ("fits", "dagge"),
            ],
        ),
        [True, False, True, True, False],
    ),
    # "b.t" tries the a-branch first, reaches "bat" — a prefix of "batten" that was
    # never filed — and has to come back up and try the i-branch.
    (
        (
            [
                ("file", "batten"), ("file", "bitten"), ("file", "bit"),
                ("fits", "bat"), ("fits", "b.t"), ("fits", "b.tten"), ("fits", "bitte"),
            ],
        ),
        [False, True, True, False],
    ),
    # Nothing filed yet: every slot, blank or not, fits nothing.
    (([("fits", "a"), ("fits", "."), ("fits", "....")],), [False, False, False]),
    # A filed entry that is a prefix of another filed entry stays findable, and a
    # dot past the end of every path fits nothing.
    (
        (
            [
                ("file", "arc"), ("file", "arch"),
                ("fits", "arc"), ("fits", "arc."), ("fits", "a.c"),
                ("fits", "ar.."), ("fits", "arch."),
            ],
        ),
        [True, True, True, True, False],
    ),
    # Filing the same entry twice changes nothing; length still has to match.
    (
        (
            [
                ("file", "zip"), ("file", "zip"),
                ("fits", "zip"), ("fits", "..."), ("fits", "...."),
            ],
        ),
        [True, True, False],
    ),
    # Single-cell slot.
    (([("file", "q"), ("fits", "q"), ("fits", "."), ("fits", "qq")],), [True, True, False]),
]

Pitfalls

• Treating "the walk reached a node" as a match. The node for bat exists because batten was filed. Without the end-marker test, fits("bat") answers True and a non-word goes into the grid.
• Returning from the first dot branch that fails. b.t must try i after a dead-ends; a search that returns False out of the first child answers False even though bit is filed.
• Letting the end marker into the fan-out. The marker sits in the same dict as the child letters, so a dot that loops over every key recurses into the marker's value and raises an AttributeError.

Variants

• The shade chart — the same tree walked from many starting positions, to split a name into other names.
• The dispatch console — no wildcards, but each node carries a ranked shortlist so a keystroke is one step.