AoC Day 23

import sys

content = sys.stdin.read().rstrip()

grid = [list(line) for line in content.split('\n')]
r, c = len(grid), len(grid[0])


def is_valid(cr):
    return 0 <= cr[0] < r and 0 <= cr[1] < c


def adj(x, y):
    normal = [(x + dx, y + dy) for dx in range(-1, 2) for dy in range(-1, 2)
              if dx != 0 or dy != 0]
    return [(x, y) for (x, y) in normal if is_valid((x, y))]


norths = [[-1, 0], [-1, -1], [-1, 1]]
souths = [[1, 0], [1, -1], [1, 1]]
wests = [[0, -1], [-1, -1], [1, -1]]
easts = [[0, 1], [-1, 1], [1, 1]]

dir_dirs = [('N', norths), ('S', souths), ('W', wests), ('E', easts)]


def pad(n):
    global grid, r, c
    for i in range(r):
        grid[i] = ['.'] * n + grid[i] + ['.'] * n
    for _ in range(n):
        grid.insert(0, ['.'] * (c + 2 * n))
    for _ in range(n):
        grid.append(['.'] * (c + 2 * n))
    r += 2 * n
    c += 2 * n


def round():
    global dir_dirs, grid

    # first half
    dirs = [[None] * c for _ in range(r)]
    proposed = [[0 for _ in range(c)] for _ in range(r)]
    for i in range(r):
        for j in range(c):
            if grid[i][j] != '#':
                continue
            if sum(map(lambda cr: grid[cr[0]][cr[1]] == '#', adj(i, j))) == 0:
                continue

            # four directions
            for _dir, _dirs in dir_dirs:
                shifted_dirs = [(i + dx, j + dy) for (dx, dy) in _dirs]
                if all(map(is_valid, shifted_dirs)) and all(
                        [grid[x][y] == '.' for (x, y) in shifted_dirs]):
                    if dirs[i][j] is None:
                        dirs[i][j] = _dir
                        proposed[i + _dirs[0][0]][j + _dirs[0][1]] += 1
                        break

    # second half
    mp = {'N': (-1, 0), 'S': (1, 0), 'W': (0, -1), 'E': (0, 1)}
    new_grid = [[grid[i][j] for j in range(c)] for i in range(r)]
    for i in range(r):
        for j in range(c):
            if dirs[i][j] is None:
                continue
            dx, dy = mp[dirs[i][j]]
            nx, ny = i + dx, j + dy
            if proposed[nx][ny] > 1:
                continue
            new_grid[i][j], new_grid[nx][ny] = new_grid[nx][ny], new_grid[i][j]

    grid = [[new_grid[i][j] for j in range(c)] for i in range(r)]
    dir_dirs = dir_dirs[1:] + dir_dirs[:1]


def print_grid():
    for i in range(r):
        for j in range(c):
            print(grid[i][j], end='')
        print()
    print()


T = 0
while True:
    T += 1
    pad(1)

    prev_grid = [[grid[i][j] for j in range(c)] for i in range(r)]
    round()
    if all(grid[i][j] == prev_grid[i][j] for i in range(r) for j in range(c)):
        print(f"FOUND {T}")
        break
"""
print_grid()

pos = [(x, y) for x in range(r) for y in range(c) if grid[x][y] == '#']

xs, ys = [x for (x, y) in pos], [y for (x, y) in pos]
minx, maxx = min(xs), max(xs)
miny, maxy = min(ys), max(ys)
area = (maxx - minx + 1) * (maxy - miny + 1)

empty = [(x, y) for x in range(minx, maxx + 1) \
    for y in range(miny, maxy + 1) if grid[x][y] == '.']
print(len(empty))
"""

Output

10:13 Downloads time pypy3 test.py < in2
FOUND XXX

________________________________________________________
Executed in  104.81 secs    fish           external
   usr time   92.38 secs    0.25 millis   92.37 secs
   sys time    8.96 secs    1.16 millis    8.95 secs