aoc/2023/21_steps.py

#!/usr/bin/env python3
import sys
from collections import deque

def bfs(grid):
    h = len(grid)
    w = len(grid[0])
    start = next((x, y) for y in range(h) for x in range(w) if grid[y][x] == 'S')
    visited = {start: 0}
    work = deque([(start, 0)])
    while work:
        (x, y), steps = work.popleft()
        for nb in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
            nx, ny = nb
            if 0 <= nx < w and 0 <= ny < h:
                if grid[ny][nx] != '#' and nb not in visited:
                    visited[nb] = steps + 1
                    work.append((nb, steps + 1))
    return list(visited.values())

def reachable_in_26501365_steps(min_dists):
    # https://github.com/villuna/aoc23/wiki/A-Geometric-solution-to-advent-of-code-2023,-day-21
    n = (26501365 - 131 // 2) // 131  # w = h = 131
    even = odd = even_corners = odd_corners = 0
    for dist in min_dists:
        is_odd = dist % 2
        even += 1 - is_odd
        odd += is_odd
        if dist > 65:
            even_corners += 1 - is_odd
            odd_corners += is_odd
    whole_squares = (n + 1) ** 2 * odd + n * n * even
    corners = (n + 1) * odd_corners + n * even_corners
    return whole_squares - corners

min_dists = bfs([line.rstrip() for line in sys.stdin])
print(sum(dist <= 64 and dist % 2 == 0 for dist in min_dists))
print(reachable_in_26501365_steps(min_dists))