medicine for rudolph

approach

this one is unfinished. the replacements are parsed into a dict and their left-hand sides are loaded into a trie, which reports every position of the molecule where a rule can apply. part1 does one round of replacements and counts the distinct results in a set, but its call is commented out.

part 2 is where it stops. the code reverses the rules and runs a breadth-first search from the molecule back towards e, and there are several experiments around it for splitting the molecule on Rn/Ar and reducing the pieces separately, but none of them is wired up to print an answer. the file reads a local file instead of stdin, and sol2.py only has the parsing.

the trick

index the rule patterns in a trie so every match in the molecule is found in one scan.

def step(g, t, q, s):
    for _ in range(len(q)):
        n = q.popleft()
        for i, p in t.report_matches(n):
            for pp in g[p]:
                nn = n[:i] + pp + n[i + len(p):]
                if nn not in s:
                    s.add(nn)
                    q.append(nn)
    return n