#!/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