day13.py

from collections import Counter, defaultdict
import numpy as np


N = 45
K = 1350
#K = 10
goal = (31, 39) # (7, 4)
#goal = (7, 4)
G = np.zeros((N, N))  # [y][x]

for y in range(N):
    for x in range(N):
        z = x * x + 3 * x + 2 * x * y + y + y * y
        z += K
        z = Counter(bin(z)).get('1', 0)
        G[x][y] = 0 if z % 2 == 0 else 1

# print()
# for y in range(N):
#     for x in range(N):
#         print('#' if G[x][y] else '.', end='')
#     print()

visited = set()
n_steps = defaultdict(lambda: float('inf'))

def visit(p, n=0):
    visited.add(p)
    if n < n_steps[p]:
        n_steps[p] = n
    if p == goal:
        return
    # up
    if p[1] - 1 >= 0 and not G[p[0]][p[1] - 1] and ((p[0], p[1] - 1) not in visited or (p[0], p[1] - 1) == goal):
        visit((p[0], p[1] - 1), n_steps[p] + 1)
    # down
    if p[1] + 1 < N and not G[p[0]][p[1] + 1] and ((p[0], p[1] + 1) not in visited or (p[0], p[1] + 1) == goal):
        visit((p[0], p[1] + 1), n_steps[p] + 1)
    # left
    if p[0] - 1 >= 0 and not G[p[0] - 1][p[1]] and ((p[0] - 1, p[1]) not in visited or (p[0] - 1, p[1]) == goal):
        visit((p[0] - 1, p[1]), n_steps[p] + 1)
    # right
    if p[0] + 1 < N and not G[p[0] + 1][p[1]] and ((p[0] + 1, p[1]) not in visited or (p[0] + 1, p[1]) == goal):
        visit((p[0] + 1, p[1]), n_steps[p] + 1)

visit((1, 1))
#print(visited)

print(n_steps[goal])

# print()
# for y in range(N):
#     for x in range(N):
#         if (x, y) in visited:
#             print('O', end='')
#         else:
#             print('#' if G[x][y] else '.', end='')
#     print()