monster messages

approach

the rules become a grammar: a dictionary from each rule number to either a literal character or a list of alternatives, each a sequence of rule numbers. a brute-force gen that expands every string a rule can produce is still in the file, kept to verify the real solution.

the real matcher is dfs, which takes a list of strings and returns every possible leftover after matching a rule against their start. a literal strips one matching character; a sequence feeds the leftovers of each part into the next; alternatives collect the results of each option. a message matches rule 0 when one of its leftovers is the empty string. part 2 replaces rules 8 and 11 with recursive versions, and since dfs already tracks every possible leftover rather than committing to one match, the same function handles the loops unchanged.

the trick

match by returning every possible remainder instead of a yes/no, so ambiguous and recursive rules need no special handling.

def dfs(g, n, targs):
    if n not in g:
        return [t[1:] for t in targs if t and t[0] == n]
    res = []
    for p in g[n]: # try the same targs!!
        x = targs
        for nn in p: # consume if matches and sequence!!
            x = dfs(g, nn, x)
            if not x:
                break
        else:
            res.extend(x)
    return res