extended polymerization

approach

instead of building the polymer string (which doubles in length every step), the solution counts adjacent pairs. each step, every pair AB with a rule AB -> C turns into AC and CB, carrying its count along. 40 steps then cost the same as 10.

to get letter counts back, it counts the first letter of every pair and adds the very last letter of the template, which is never the first letter of a pair. the answer is the most common count minus the least common.

the trick

track pair counts, not the string: the size of the problem stays fixed however many steps you run.

for _ in range(steps):
    nc = Counter()
    for pp in c:
        if pp in rules:
            res = rules[pp]
            nc[pp[0] + res] += c[pp]
            nc[res + pp[1]] += c[pp]
    c = nc