day_15.py

#!/usr/bin/python3
from collections import defaultdict

with open("input.txt", "r", encoding="utf8") as file:
    data = [[int(char) for char in line.strip()] for line in file.readlines()]

S = 5

W, H = len(data), len(data[0])

directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]

distance = [[None] * H * S for _ in range(W * S)]
queue = defaultdict(list)
queue_start = 0

current_x, current_y = 0, 0

while True:
    for dx, dy in directions:
        x = current_x + dx
        y = current_y + dy

        if x in [-1, W * S] or y in [-1, H * S]:
            continue

        weight = 1 + (data[x % W][y % H] + (x // W) + (y // H) + 8) % 9
        new_distance = queue_start + weight

        if distance[x][y] is None or new_distance < distance[x][y]:
            queue[new_distance].append((x, y))
            distance[x][y] = new_distance

    limit = queue_start + 10
    while queue_start < limit:
        if queue[queue_start]:
            current_x, current_y = queue[queue_start].pop()
            break

        queue_start += 1
    else:
        break

print(distance[W - 1][H - 1])
print(distance[W * S - 1][H * S - 1])