AoC-2024-20

import re
from datetime import datetime
from collections import defaultdict

st = datetime.now()

grid = [list(line.strip()) for line in open("input.txt")]
# grid = [list(line.strip()) for line in open("test.txt")]

SX = len(grid[0])
SY = len(grid)
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def get(x, y):
    if x < 0 or x >= SX or y < 0 or y >= SY:
        return " "
    return grid[y][x]

for y, l in enumerate(grid):
    for x, c in enumerate(l):
        if c == "S":
            start = (x, y)
        if c == "E":
            end = (x, y)

track = [start]

# find the track
nx, ny = start
while (nx, ny) != end:
    # print(nx, ny)
    for dx, dy in d:
        if get(nx + dx, ny + dy) in ('.', 'E') and not (nx + dx, ny + dy) in track:
            track.append((nx + dx, ny + dy))
            nx += dx
            ny += dy
            break

# print(f'Track length is {len(track)}')

answer = 0
SAVES = 100

for i in range(len(track)):
    for j in range(i+SAVES, len(track), 1):
        # xa, ya is always before xb, yb, and a jump between them will save
        # us at least SAVES steps
        xa, ya = track[i]
        xb, yb = track[j]
        d = abs(xa - xb) + abs(ya - yb)
        # we would be saving j-i-d steps,
        # so if our manhattan dist is at most 20, and we are saving (j-i-d) steps, then we have a valid path
        if d <= 20 and ((j-i-d) >= 100):
            answer += 1

print(answer)
print(f'Execution time: {datetime.now()-st}')