day24.py

from util import get_data
import itertools
from collections import defaultdict

def sum_pos((a,b),(c,d)):
  return (a+c, b+d)

dirmap = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
dirs = set(dirmap.values())

orig_data = get_data(24)

data = orig_data

grid = defaultdict(bool)

for i in xrange(len(data)):
  for j in xrange(len(data[i])):
    grid[(i, j)] = data[i][j] == '#'

def step(g):
  new_g = defaultdict(bool)
  keys = g.keys()
  for p in keys:
    c = sum(g[sum_pos(p, d)] for d in dirs)
    if g[p]:
      new_g[p] = (c == 1)
    else:
      new_g[p] = 1 <= c <= 2
  return new_g

def bdv(g):
  r = 0
  for i in xrange(len(data)):
    for j in xrange(len(data[i])):
      if grid[(i, j)]:
        r += 2 ** (i * len(data[i]) + j)
  return r

seen_hashes = set()
while True:
  b = bdv(grid)
  if b in seen_hashes:
    print "a", b
    break
  else:
    seen_hashes.add(b)
  grid = step(grid)

grids = [defaultdict(bool), defaultdict(bool)]
grid = grids[0]
for i in xrange(len(data)):
  for j in xrange(len(data[i])):
    grid[(i, j)] = (data[i][j] == '#')

assert grid[(2, 2)] == False

for s in xrange(200):
  grids = [defaultdict(bool)] + grids
  grids.append(defaultdict(bool))
  new_grids = []
  for i in xrange(len(grids) - 1):
    pg = grids[i - 1] if i > 0 else defaultdict(bool)
    og = grids[i]
    ng = grids[i + 1]
    res = defaultdict(bool)
    for p in itertools.product(range(5), range(5)):
      i, j = p
      if i == j == 2:
        continue

      cnt = sum(og[sum_pos(p, d)] for d in dirs)
      if p == (2, 1):
        cnt += sum(ng[(r, 0)] for r in xrange(5))
      elif p == (2, 3):
        cnt += sum(ng[(r, 4)] for r in xrange(5))
      elif p == (1, 2):
        cnt += sum(ng[(0, c)] for c in xrange(5))
      elif p == (3, 2):
        cnt += sum(ng[(4, c)] for c in xrange(5))

      if i == 0:
        cnt += int(pg[(1, 2)])
      elif i == 4:
        cnt += int(pg[(3, 2)])

      if j == 0:
        cnt += int(pg[(2, 1)])
      elif j == 4:
        cnt += int(pg[(2, 3)])

      if og[p]:
        res[p] = (cnt == 1)
      else:
        res[p] = 1 <= cnt <= 2

    new_grids.append(res)

  new_grids.append(defaultdict(bool))
  assert len(new_grids) == len(grids)
  grids = new_grids

print "b", sum(sum(d.values()) for d in grids)