day10_part2.py

day10_part2.py

#!/usr/bin/env python3

from typing import Mapping


FROM_TO_MAPPING: Mapping[tuple[int, int], Mapping[str, tuple[int, int]]] = {
    (0, 2): {
        '-': (0, 2),
        'J': (-2, 0),
        '7': (2, 0),
    },
    (0, -2): {
        '-': (0, -2),
        'L': (-2, 0),
        'F': (2, 0),
    },
    (-2, 0): {
        '|': (-2, 0),
        '7': (0, -2),
        'F': (0, 2),
    },
    (2, 0): {
        '|': (2, 0),
        'J': (0, -2),
        'L': (0, 2),
    },
}


DIRECTIONS: tuple[tuple[int, int], ...] = (
    (-1, 0),
    (1, 0),
    (0, -1),
    (0, 1),
)


def find_starting_point(map: list[list[str]], n: int, m: int) -> tuple[tuple[int, int], set[tuple[int, int]]]:
    for i in range(n):
        for j in range(m):
            if map[i][j] == 'S':
                return (i, j)
             

def find_walls(x: int, y: int, dx: int, dy: int, map: list[list[str]]) -> set[tuple[int, int]]:
    walls = {(x, y), }
    while True:
        x += dx // 2
        y += dy // 2
        walls.add((x, y))
        x += dx // 2
        y += dy // 2
        walls.add((x, y))
        dirs = FROM_TO_MAPPING[(dx, dy)]
        try:
            (dx, dy) = dirs[map[x][y]]
        except KeyError:
            return walls


def walk_around(walls: set[tuple[int, int]], n: int, m: int, x: int, y: int) -> tuple[bool, set[tuple[int, int]]]:
    visited = {(x, y, )}
    inside_the_loop = True

    q = [(x, y, ), ]
    while q:
        x, y = q.pop()

        for dx, dy in DIRECTIONS:
            if x + dx < 0 or x + dx >= n or y + dy < 0 or y + dy >= m:
                inside_the_loop = False
                continue

            if (x + dx, y + dy) in visited or (x + dx, y + dy) in walls:
                continue

            visited.add((x + dx, y + dy))
            q.append((x + dx, y + dy))

    return (inside_the_loop, visited)


def build_map() -> list[list[str]]:
    with open("input.txt") as f:
        rows = []
        for line in f:
            row = ['*']
            for ch in line.strip():
                row.extend((ch, '*'))
            rows.append(row)

    template = ['*'] * len(rows[0])
    map = [template[:]]
    for row in rows:
        map.extend([row, template[:]])

    return map


map = build_map()
n = len(map)
m = len(map[0])

x, y = find_starting_point(map, n, m)
tiles = {(i, j) for i in range(n) for j in range(m)}
tiles.remove((x, y))

for (dx, dy), options in FROM_TO_MAPPING.items():
    if 0 <= x + dx < n and 0 <= y + dy < m and map[x + dx][y + dy] in options:
        walls = find_walls(x, y, dx, dy, map)
        break

tiles -= walls
ans = 0
while tiles:
    x, y = tiles.pop()

    inside_the_loop, visited_tiles = walk_around(walls, n, m, x, y)
    tiles -= visited_tiles

    if inside_the_loop:
        ans += sum(1 for x, y in visited_tiles if map[x][y] != '*')

print(ans)