76 lines
1.7 KiB
Python
76 lines
1.7 KiB
Python
|
#!/usr/bin/env python
|
||
|
|
|
||
|
|
import re
|
||
|
|
|
||
|
|
RE_INIT=re.compile(r'^initial state: ([\#\.]+)$')
|
||
|
|
RE_RULE=re.compile(r'^([\#|\.]+) => ([\'#\.])$')
|
||
|
|
|
||
|
|
ITER = 50000000000
|
||
|
|
|
||
|
|
rules = dict()
|
||
|
|
start = None
|
||
|
|
|
||
|
|
def read_input():
|
||
|
|
with open('input.txt', 'r') as f:
|
||
|
|
for line in f:
|
||
|
|
yield line.strip()
|
||
|
|
|
||
|
|
def run_generation(pots, left_index = 0):
|
||
|
|
result = ""
|
||
|
|
if not pots.startswith('.....'):
|
||
|
|
pots = '....' + pots
|
||
|
|
left_index -= 4
|
||
|
|
if not pots.endswith('.....'):
|
||
|
|
pots = pots + '.....'
|
||
|
|
|
||
|
|
for pos in range(2, len(pots) -2):
|
||
|
|
r_key = pots[pos-2:pos+3]
|
||
|
|
if r_key not in rules:
|
||
|
|
rules[r_key] = '.'
|
||
|
|
result = result + rules[r_key]
|
||
|
|
|
||
|
|
return (result, left_index+2)
|
||
|
|
|
||
|
|
def analyze_sums(sums, last=10):
|
||
|
|
if len(sums) < last:
|
||
|
|
return None
|
||
|
|
diff = sums[-1] - sums[-2]
|
||
|
|
for i in range(1, last-1):
|
||
|
|
x1 = sums[i*-1]
|
||
|
|
x2 = sums[(i+1)*-1]
|
||
|
|
if diff != (x1 -x2):
|
||
|
|
return None
|
||
|
|
|
||
|
|
return diff
|
||
|
|
|
||
|
|
for line in read_input():
|
||
|
|
m = RE_INIT.match(line)
|
||
|
|
if m:
|
||
|
|
start = m.group(1)
|
||
|
|
continue
|
||
|
|
m = RE_RULE.match(line)
|
||
|
|
if m:
|
||
|
|
rules[m.group(1)] = m.group(2)
|
||
|
|
continue
|
||
|
|
if len(line) == 0:
|
||
|
|
continue
|
||
|
|
raise Execption('unparseable input')
|
||
|
|
|
||
|
|
pots = start
|
||
|
|
left_index = 0
|
||
|
|
g = 0
|
||
|
|
sums = []
|
||
|
|
sums.append((sum([k+left_index for k,v in enumerate(pots) if v == '#'])))
|
||
|
|
while g < ITER:
|
||
|
|
g += 1
|
||
|
|
(pots1, left_index1) = run_generation(pots, left_index)
|
||
|
|
if pots1 == pots:
|
||
|
|
break
|
||
|
|
(pots, left_index) = (pots1, left_index1)
|
||
|
|
print("(g:{})(s:{}): {}".format(g+1, left_index,pots))
|
||
|
|
sums.append((sum([k+left_index for k,v in enumerate(pots) if v == '#'])))
|
||
|
|
diff = analyze_sums(sums)
|
||
|
|
if diff:
|
||
|
|
print(sums[-1]+(diff * (ITER-g)))
|
||
|
|
break
|