from collections import defaultdict

State = set[tuple[int, int]]

def step(state: State) -> State:
    def next_cell_state(x: int, y: int) -> bool:
        neighbors = sum((x + dx, y + dy) in state for dx in (-1, 0, 1) for dy in (-1, 0, 1) if (dx, dy) != (0, 0))
        if (x, y) in state:
            return neighbors == 2 or neighbors == 3
        else:
            return neighbors == 3
    next_state: State = set()
    for x in range(100):
        for y in range(100):
            if next_cell_state(x, y):
                next_state.add((x, y))
    return next_state

def part1(state: State) -> int:
    for i in range(100):
        state = step(state)
    return len(state)

def part2(state: State) -> int:
    for i in range(100):
        state = step(state)
        state |= {(0, 0), (0, 99), (99, 0), (99, 99)}
    return len(state)

if __name__ == '__main__':
    with open('input') as f:
        state: State = set()
        for y, line in enumerate(f):
            for x, c in enumerate(line.strip()):
                if c == '#':
                    state.add((x, y))
    print(part1(state))
    print(part2(state))