49 lines
1.3 KiB
Python
49 lines
1.3 KiB
Python
|
#!/usr/bin/env python3
|
||
|
|
import fileinput
|
||
|
|
from timeit import timeit
|
||
|
|
from collections import Counter, defaultdict
|
||
|
|
|
||
|
|
lines = [str(line) for line in fileinput.input()]
|
||
|
|
|
||
|
|
|
||
|
|
def main():
|
||
|
|
template = [ord(c) for c in lines[0].strip()]
|
||
|
|
rules = defaultdict(dict)
|
||
|
|
for l in lines[2:]:
|
||
|
|
rules[ord(l[0])][ord(l[1])] = ord(l[6])
|
||
|
|
|
||
|
|
polymer_counter = Counter(template)
|
||
|
|
|
||
|
|
counter = defaultdict(lambda: defaultdict(int))
|
||
|
|
for i in range(len(template) - 1):
|
||
|
|
counter[template[i]][template[i + 1]] += 1
|
||
|
|
|
||
|
|
def step():
|
||
|
|
nonlocal counter
|
||
|
|
|
||
|
|
new_counter = defaultdict(lambda: defaultdict(int))
|
||
|
|
for a, subcounter in counter.items():
|
||
|
|
for c, count in subcounter.items():
|
||
|
|
b = rules[a][c]
|
||
|
|
new_counter[a][b] += count
|
||
|
|
new_counter[b][c] += count
|
||
|
|
polymer_counter[b] += count
|
||
|
|
counter = new_counter
|
||
|
|
|
||
|
|
def run(iterations):
|
||
|
|
for _ in range(iterations):
|
||
|
|
step()
|
||
|
|
|
||
|
|
counts = polymer_counter.most_common()
|
||
|
|
return counts[0][1] - counts[-1][1]
|
||
|
|
|
||
|
|
part1 = run(10)
|
||
|
|
part2 = run(30) # 30 because it inherits the state from part 1
|
||
|
|
|
||
|
|
return part1, part2
|
||
|
|
|
||
|
|
|
||
|
|
if __name__ == "__main__":
|
||
|
|
print(main())
|
||
|
|
print(f"{timeit(main, number=2000) / 2:.3f} ms")
|