1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

states = [[] for _ in tc + ("",)]
states[0] += [("s", (), ("e",), 0, 0)]
seen = [set() for _ in tc + ("",)]
best = inf
for i in range(len(tc) + 1):
    for (symbol, pre, after, origin, ts) in states[i]:
        if i == len(tc):
            if (symbol, pre, after, origin) == ("s", ("e",), (), 0): 
                best = min(ts, best) 
        v = (symbol, pre, after, origin, ts)
        if v in seen[i]: continue 
        seen[i] |= {v}
        if len(after) == 0:
            for (s1, p, a, o, ts2) in states[origin]:
                if a[:1] != (symbol,): continue
                states[i] += [(s1, p + (symbol,), a[1:], o, ts + ts2)]
            continue
        if i < len(tc) and after[0] == tc[i]:
            states[i + 1] += [(symbol, pre + (symbol,), after[1:], origin, ts)]
        for rp in replacements[after[0]]: 
            states[i] += [(after[0], (), rp, i, 1)]
print(best)