Advent of Code Day 16 Part 1

from collections import deque


with open("day16input.txt") as f:
    grid = f.read().splitlines()


def race(maze: list[str]) -> int:
    rows = len(maze)
    cols = len(maze[0])

    # find start and end points
    start = (-1, -1)
    end = (-1, -1)
    for row in range(rows):
        for col in range(cols):
            if maze[row][col] == 'S':
                # store start position and starting direction (east)
                start = (row, col, 0, 1)
            elif maze[row][col] == 'E':
                end = (row, col)

    directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
    queue = deque([start])
    # keep track of the score for each node and the directions used to get to it
    node_score = {start: 0}

    # recursive BFS, pop from start of list for current node, append all valid nodes at end of list
    while queue:
        y, x, dy, dx = queue.popleft()
        curr_score = node_score[(y, x, dy, dx)]
        # if we're at the finish, we can stop looking for new nodes
        if maze[y][x] != 'E':
            for dy2, dx2 in directions:
                # we don't want to go back to where we came from
                if (dy2, dx2) == (-dy, -dx):
                    continue
                if maze[y+dy2][x+dx2] != '#':
                    # if direction doesn't equal current node's direction, we turn
                    if (dy2, dx2) != (dy, dx):
                        new_score = curr_score + 1001
                    else:
                        new_score = curr_score + 1
                    # update score and append to queue if we visit the node for the first time
                    # also do this if our new score would be lower for that node and direction
                    if ((y+dy2, x+dx2, dy2, dx2) not in node_score or
                            ((y+dy2, x+dx2, dy2, dx2) in node_score and
                             node_score[(y+dy2, x+dx2, dy2, dx2)] > new_score)):
                        node_score[(y+dy2, x+dx2, dy2, dx2)] = new_score
                        queue.append((y+dy2, x+dx2, dy2, dx2))

    return min([node_score[x] for x in node_score if (x[0], x[1]) == end])


print(race(grid))