#!/usr/bin/env python
from collections import defaultdict

with open('day14.txt') as data:
    template = next(data).strip()
    next(data)
    rules = {}
    for line in data:
        k, v = line.strip().split(' -> ')
        rules[k] = v

def polymerize(steps=10):
    pairs = defaultdict(int)
    for i in range(len(template) - 1):
        pairs[template[i] + template[i+1]] += 1

    for i in range(steps):
        update = defaultdict(int)
        for k, v in pairs.items():
            update[k[0] + rules[k]] += v
            update[rules[k] + k[1]] += v
        pairs = update

    counts = defaultdict(int)
    for k, v in pairs.items():
        counts[k[0]] += v
    return max(counts.values()) - min(counts.values()) - 1

print(polymerize())
print(polymerize(40))