from queue import deque
from itertools import product

lines = [line.strip() for line in open("23.input")]

elves = set()

for y, line in enumerate(lines):
    for x, c in enumerate(line):
        if c == "#":
            elves.add((x, y))

SURROUND = set(product([-1, 0, 1], repeat=2)) - set([(0, 0)])
DIRS = deque([(0, -1), (0, 1), (-1, 0), (1, 0)])

def add(a, b):
    return (a[0] + b[0], a[1] + b[1])

def show(elves):
    xs = [a[0] for a in elves]
    ys = [a[1] for a in elves]

    for y in range(min(ys), max(ys)+1):
        for x in range(min(xs), max(xs)+1):
            if (x, y) in elves:
                print("#", end="")
            else:
                print(".", end="")
        print("")
    print("-" * 20)
    print("Empty space:", (max(ys) + 1 - min(ys)) * (max(xs) + 1 - min(xs)) - len(elves))

for i in range(1000000):
    proposals = {}

    for elf in elves:
        for d in SURROUND:
            if add(elf, d) in elves:
                break
        else:
            proposals[elf] = [elf]
            continue
        for d in DIRS:
            zero_axis = 0 if d[0] == 0 else 1

            for dz in [-1, 0, 1]:
                xd = list(d)
                xd[zero_axis] = dz
                if add(elf, xd) in elves:
                    break
            else:
                prop = add(d, elf)

                total = proposals.get(prop, [])
                proposals[prop] = total + [elf]
                break
        else:
            proposals[elf] = [elf]
            continue

    new_elves = set()

    for pos, candidates in proposals.items():
        if len(candidates) > 1:
            for c in candidates:
                new_elves.add(c)
        else:
            new_elves.add(pos)


    if i == 9:
        print("Part 1:")
        show(new_elves)

    assert len(elves) == len(new_elves)

    if new_elves == elves:
        print("Part 2:", i + 1)
        break


    head = DIRS.popleft()
    DIRS.append(head)
    elves = new_elves