Advent of Code

Another day, another map. It seems like it’s a trend for this year’s puzzles. But right now the challenge in those maps are different enough that I don’t mind. Maps are nice.

Anyway: this time, the map is a maze, and the challenge is some good ol’ pathfinding.

# are walls, S is the starting position (we always start facing to the right), E the end position.

Part 1 - maze runner

In part 1, we need to find the best path through the maze, minimizing the number of turns that we make. One 90 degree turn costs 1000 point, one forward move costs 1 point.

The first thing to do, as usual, is to determine how we want to encode and store the data. A graph seems like a natural structure to use here: we don’t really care about the walls, we just need to know where we can go from each position, and the direction of a move to each neighbour.

I decided to keep with a namedtuple for storing positions, as in most grid-map puzzles so far. This time I put the possible directions in an Enum, rather than the lambda functions I used before, because we won’t really need to care about what those directions mean when solving the maze, we just need to know when we change direction. I also store the “backwards” relationships between directions so that I can easily ensure we don’t move backward in the maze (we could also just check that we don’t re-visit the same place twice in a given path, but this way made the code a little bit easier to read for me, and also I think slightly more efficient, not that I care too much about that!).

Then we have a Node class that stores positions, neighbours, and whether a node is a start or finish point.

Position = namedtuple("Position", ["row", "column"])

class Direction(enum.Enum):
    UP = enum.auto()
    LEFT = enum.auto()
    RIGHT = enum.auto()
    DOWN = enum.auto()

BACKWARDS = {
    Direction.UP: Direction.DOWN,
    Direction.DOWN: Direction.UP,
    Direction.LEFT: Direction.RIGHT,
    Direction.RIGHT: Direction.LEFT
}

class Node:
    def __init__(self, position: Position):
        self.position = position
        self.neighbours = {}
        self.is_start = False
        self.is_end = False

    def set_neighbour(self, direction: Direction, neighbour: Node):
        self.neighbours[direction] = neighbour
    
    def get_neighbours(self):
        return self.neighbours
    
    def __repr__(self):
        return f"Node({self.position})"
    
    def __str__(self):
        if self.is_start:
            return 'S'
        if self.is_end:
            return 'E'
        return '.'

def parse_input() -> tuple[dict[Position, Node], Node, Node]:
    # getpath is a helper function to get the input file
    data = load_as_str(getpath(16)) 

    nodes = {}
    start = None
    end = None
    for r, row in enumerate(data.split('\n')):
        if len(row) == 0:
            continue
        for c, cell in enumerate(row):
            if cell in ['.', 'E', 'S']:
                n = Node(Position(r, c))
                # add neighbours. Since we parse top-down left-right, we check top and left.
                if (ln := nodes.get(Position(r, c-1))) is not None:
                    n.set_neighbour(Direction.LEFT, ln)
                    ln.set_neighbour(Direction.RIGHT, n)
                if (tn := nodes.get(Position(r-1, c))) is not None:
                    n.set_neighbour(Direction.UP, tn)
                    tn.set_neighbour(Direction.DOWN, n)
                # check for start and finish
                if cell == 'E':
                    n.is_end = True
                    end = n
                if cell == 'S':
                    n.is_start = True
                    start = n
                nodes[Position(r, c)] = n

    # make sure we didn't screw up   
    assert start is not None
    assert end is not None

    return nodes, start, end

Now all we need to do is solve the maze. I decided to use a best-current-score approach to guarantee that I find the best score in the end. I store a list of currently explored paths with their associated “current cost”. I keep the list sorted by increasing cost with this insert_sorted method which slots a (cost, whatever) tuple into the list where it belongs:

def insert_sorted(l: list[tuple[int, Any]], v: tuple[int, Any]) -> list[tuple[int, Any]]:
    for i, (c, _) in enumerate(l):
        if v[0] < c:
            l.insert(i, v)
            return l
    l.append(v)
    return l

Each path is stored as a list of nodes with the direction from which they were added. At the start, we add the neighbours of the starting node, with a score of 1 if the neighour is on the right, 1001 otherwise (i.e. on the top as the start is on the bottom-left).

def solve_maze(start: Node, 
               end: Node, 
               nodes: dict[Position, Node], 
               start_dir: Direction = Direction.RIGHT):
    paths: list[tuple[int, list[tuple[Direction, Node]]]] = []
    
    for d, n in start.neighbours.items():
        if d == start_dir:
            insert_sorted(paths, (1, [(d, n)]))
        else:
            insert_sorted(paths, (1001, [(d, n)]))
    
    ...

    ...
    while len(paths) > 0:
        cur_cost, cur_path = paths.pop(0)
        cur_dir, cur_node = cur_path[-1]
        for direction, n in cur_node.get_neighbours().items():
            if direction != BACKWARDS[cur_dir]:
                new_cost = cur_cost+1 if direction == cur_dir else cur_cost+1001
                path = (new_cost, cur_path + [(direction, n)])
                paths = insert_sorted(paths, path)
    ...

This alone is very costly, as we will have multiple paths branching and re-converging being stored together for no reason, and we’ll keep updating paths which are clearly not useful because they are revisiting nodes that we already visited at lower costs. So we keep track of that as well.

Finally, we stop when we find the end. As we’re always on the “current best score” branch, the first time we find the end is always from the best path. The final method is:

def solve_maze(start: Node, 
               end: Node, 
               nodes: dict[Position, Node], 
               start_dir: Direction = Direction.RIGHT):
    paths: list[tuple[int, list[tuple[Direction, Node]]]] = []
    
    for d, n in start.neighbours.items():
        if d == start_dir:
            insert_sorted(paths, (1, [(d, n)]))
        else:
            insert_sorted(paths, (1001, [(d, n)]))

    # keep track of best score at visited -> if we revisit something which already has a 
    # better score -> stop that path!
    visited: dict[Position, int] = {}

    while len(paths) > 0:
        cur_cost, cur_path = paths.pop(0)
        cur_dir, cur_node = cur_path[-1]
        for direction, n in cur_node.get_neighbours().items():
            if direction != BACKWARDS[cur_dir]:
                new_cost = cur_cost+1 if direction == cur_dir else cur_cost+1001
                if n.position in visited and visited[n.position] < new_cost:
                    # abandon this path
                    continue
                visited[n.position] = new_cost
                path = (new_cost, cur_path + [(direction, n)])
                paths = insert_sorted(paths, path)
                if n.is_end:
                    return path
    
    return False

nodes, start, end = parse_input(False)
cost, _ = solve_maze(start, end, nodes)
print(f"Part 1 answer: {cost})

Part 2 - we want more paths

The twist in part 2 is that we actually need to keep track of all the best paths, not just the best one, as there are several tied together. The answer of part 2 is the number of nodes that are part of one of the best paths.

I initially hoped that I could get away with just putting a <= instead of < when I checked if a better path existed (so: if n.position in visited and visited[n.position] < new_cost:), and then keeping a list of best_paths, and having:

    best_paths = []
    ...
                if n.is_end:
                    best_paths.append(path)
                ...
    return best_paths

But that wasn’t enough, because sometimes you “revisit” a node that has a lower score but where the next node from the other path comes with a change of direction, whereas you are coming from the same direction. For instance, in this part of the sample:

Starting “up” costs 1001 points. If you first go up all the way, then turn right, you arrive at the ? with 1001+1+1+1+1001+1=2006 points. If you go right at the X, you will rejoin with 1001+1+1001+1+1001+1=3006 points. But in the first path, you then have to change direction to go up, so you’ll get to 3007, the same as in the second path where we’re already going up. This is very annoying to check… so I didn’t. I decided that it wouldn’t be too bad to keep a few too many paths around, as I could filter them at the end. So I changed my “visited” condition to: if n.position in visited and visited[n.position] < new_cost-1000:, to also keep paths that are “one turn of direction” away from being the best.

Then, at the end, we filter the candidates to only keep those with a cost equal to the minimum cost. The updated method is:

def solve_maze(start: Node, end: Node, nodes: dict[Position, Node], start_dir: Direction = Direction.RIGHT):
    paths: list[tuple[int, list[tuple[Direction, Node]]]] = []
    
    for d, n in start.neighbours.items():
        if d == start_dir:
            insert_sorted(paths, (1, [(d, n)]))
        else:
            insert_sorted(paths, (1001, [(d, n)]))

    # keep track of best score at visited -> if we revisit something which already has a 
    # better score -> stop that path!
    visited: dict[Position, int] = {}
    best_paths = []

    while len(paths) > 0:
        cur_cost, cur_path = paths.pop(0)
        cur_dir, cur_node = cur_path[-1]
        for direction, n in cur_node.get_neighbours().items():
            if direction != BACKWARDS[cur_dir]:
                new_cost = cur_cost+1 if direction == cur_dir else cur_cost+1001
                if n.position in visited and visited[n.position] < new_cost-1000:
                    # abandon this path
                    continue
                if n.position in visited:
                    visited[n.position] = min(new_cost, visited[n.position])
                else:
                    visited[n.position] = new_cost
                path = (new_cost, cur_path + [(direction, n)])
                paths = insert_sorted(paths, path)
                if n.is_end:
                    best_paths.append(path)
    min_cost = min(cost for cost, _ in best_paths)
    return [(cost, path) for cost, path in best_paths if cost == min_cost]

nodes, start, end = parse_input()
best_paths = solve_maze(start, end, nodes)
best_cost = best_paths[0][0]
print(f"Part 1 answer: {best_cost}")

all_nodes = set()
for _, path in best_paths:
    all_nodes = all_nodes.union(p[1] for p in path)
print(f"Part 2 answer: {len(all_nodes)+1}")

The +1 at the end accounting for the fact that we don’t put the starting node in the path. Off-by-one errors are always fun.