Day 16

• Puzzle for the day
• Full code for my solution

I woke up today’s Reindeer Olympics optimistic - probably quite like Sweden felt at the end of the first period of the Floorball finals yesterday leading 3-0 against Finland. But just like Finland upset Sweden in the end (🎉), so did this puzzle to me.

I’ve been solving a ton of these grid path finding puzzles through the past 10 years of Advent of Code puzzles and I have started to feel quite confident.

So when I saw a maze like this

###############
#.......#....E#
#.#.###.#.###.#
#.....#.#...#.#
#.###.#####.#.#
#.#.#.......#.#
#.#.#####.###.#
#...........#.#
###.#.#####.#.#
#...#.....#.#.#
#.#.#.###.#.#.#
#.....#...#.#.#
#.###.#.#.#.#.#
#S..#.....#...#
###############

I thought to myself: piece of cake.

Read input

Before we go into navigating the maze, let’s parse it in.

data = read_input(16, str)
grid = create_grid(data, predicate=lambda x: x != ".")
 
start = [key for key, value in grid.items() if value == "S"][0]
del grid[start]
 
target = [key for key, value in grid.items() if value == "E"][0]
del grid[target]

Thanks to my utility library, all we have to do is tell it which cells we want to skip (. means empty space in today’s grid) and then extract the start and end positions.

I also defined three type aliases:

Grid = dict[Coordinate, str]
Direction = Literal["U", "D", "R", "L"]
State = Tuple[Coordinate, Direction]

Part 1

In the first part, our goal is to find the cheapest path from Start to End. The scoring is as follows:

• 1 point for every movement
• +1000 points if we also need to turn

We start at position S facing right (R).

I decided to use A* search algorithm that is one that I kind of understand and can follow (although I still don’t quite understand it deeply enough that I’d be able to modify it). I’m going to explain it as I understand it but it’s possible there are misunderstandings so don’t take everything as full truth.

To implement A* algorithm, we need a couple of helpers:

First, we need a heuristic function. It’s basically an estimate of how much it costs for us to reach the end from our current location. Since we don’t know where the walls are as we move through the grid, we use a Manhattan distance to calculate how much would it cost to get there if every move would just cost 1:

def distance_to_target(start: Coordinate, target: Coordinate) -> int:
    return abs(start.x - target.x) + abs(start.y - target.y)

Next thing we need when moving along the grid is to be able to get all the possible next positions:

def get_valid_neighbours(
    current: Coordinate, grid: Grid, path: List[State]
) -> List[Coordinate]:
    neighbours = [
        Coordinate(current.x, current.y - 1),
        Coordinate(current.x, current.y + 1),
        Coordinate(current.x - 1, current.y),
        Coordinate(current.x + 1, current.y),
    ]
 
    path = [coord for coord, _ in path]
 
    return [
        neighbour
        for neighbour in neighbours
        if grid.get(neighbour) != "#" and neighbour not in path
    ]

I calculate all cardinal neighbours and then take away all walls and positions where we’ve been before.

Then, we need a way to find the cheapest option from a set:

def smallest_f_score(
    f_score: dict[State, int],
    open_set: set[State],
) -> State:
    first = open_set.pop()
    
    smallest = f_score[first]
    smallest_pos = first[0]
    smallest_direction = first[1]
    
    for pos, direction in open_set:
        if (score := f_score[pos, direction]) < smallest:
            smallest_pos = pos
            smallest_direction = direction
            smallest = score
 
    open_set.add(first)
    return smallest_pos, smallest_direction

It finds the smallest (position, direction) pair of the positions in open_set based on their f_score values. f_score is where we keep track of the estimated costs from point A to the target.

We also need to get the next direction based on where we want to go so we can account for the turns:

def get_next_direction(
    current: Coordinate, neighbour: Coordinate, direction: Direction
) -> Direction:
    nexts: dict[Tuple[int, int], Direction] = {
        (0, 1): "U",
        (0, -1): "D",
        (1, 0): "L",
        (-1, 0): "R",
    }
    return nexts[(current.x - neighbour.x, current.y - neighbour.y)]

This function before refactoring was 50 lines longer… I took such an overcomplicated route in the beginning. When I got to the right solution for the entire part 1, I came back to refactor and realised that the new direction did not depend at all on what our starting direction was. Silly me.

I also have this factory function that I learned years ago and have been copy-pasting through different Advent of Codes with me:

def constant_factory(x: int) -> Callable[[int], int]:
    return lambda: x

It’s a function that returns a function that returns the original value.

We use it later to create a defaultdict that defaults to a specific number instead of 0 which is the default when using int.

Let’s talk about the actual A* implementation. The variable names I’ve picked up from the Wikipedia article for A* to help me follow along.

The path finding function gets four arguments: start and target are the positions we start from and end to. grid is our map and direction is our starting direction.

def find_shortest_path(
    start: Coordinate,
    target: Coordinate,
    grid: Grid,
    direction: Direction
) -> Tuple[List[State], int] | None:

We keep track of all the places where we haven’t been yet as a set of tuples of (position, direction). Originally, I did not keep track of the directions which worked with examples (and with some of the other people’s actual inputs) but then found a nasty bug with my actual input. More of that later.

open_set = set()
open_set.add((start, direction))

We keep track of the best path so far as a dictionary:

came_from: dict[State, State] = {}

g_score keeps track of how much it cost to get to a specific position and we define it as a default dictionary where a missing position gets a value of infinity to make sure any real score is always lower than it.

g_score: dict[State, int] = defaultdict(constant_factory(math.inf))
g_score[(start, direction)] = 0

f_score keeps track of the estimated cost to reach the goal:

f_score: dict[State, int] = defaultdict(constant_factory(math.inf))
f_score[(start, direction)] = distance_to_target(start, target)

As long as we have some positions we haven’t visited and we haven’t reached the goal yet, we execute this loop:

while open_set:
	current, direction = smallest_f_score(f_score, open_set)
	if current == target:
		score = g_score[(current, direction)]
		return (
			reconstruct_path(came_from, (current, direction))
			+ [(current, direction)],
			score,
		)
	open_set.remove((current, direction))
 
	path = reconstruct_path(came_from, (current, direction))
	for neighbour in get_valid_neighbours(current, grid, path):
		next_direction = get_next_direction(current, neighbour, direction)
		tentative_g_score = g_score[(current, direction)] + 1
		if next_direction != direction:
			tentative_g_score += 1000
 
		if tentative_g_score < g_score[(neighbour, next_direction)]:
			came_from[(neighbour, next_direction)] = (current, direction)
			g_score[(neighbour, next_direction)] = tentative_g_score
			f_score[(neighbour, next_direction)] = (
				tentative_g_score + distance_to_target(neighbour, target)
			)
			open_set.add((neighbour, next_direction))
 
return None

First, we find the cheapest position we have left. This ensures we’re always exploring all the paths until they become more expensive than the furthest we’ve already been to.

If we reach the goal, we return the path from start to end and the final score.

If we don’t reach the goal, we remove the current position as we’ve now visited it. Then we check for each possible neighbour.

We get the new direction and calculate a possible g_score. It starts as 1 and increases by 1000 if we have to turn.

We then check if the new possible score is lower than our previous best for this position+direction pair. If it’s not, we stop following this path and check rest of the neighbours.

If it is, we update our path, we update the g_score and f_score for the new position and we add it to the open_set to navigate to later.

Eventually, this will find us the cheapest route or return None if no path to target exists.

def part_1():
    data = read_input(16, str)
    grid = create_grid(data, predicate=lambda x: x != ".")
 
    start = [key for key, value in grid.items() if value == "S"][0]
    del grid[start]
 
    target = [key for key, value in grid.items() if value == "E"][0]
    del grid[target]
 
    path, score = find_shortest_path(start, target, grid, "R")
    print(f'Part 1: {score}')

The elusive bug

I mentioned earlier that I ran into a bug when running with my actual input. My score was 12 points higher than the real one so my path took an small extra long route somewhere.

I wasn’t delighted. I knew that debugging this one was gonna be a pain, for two reasons:

1. The search is so large: a 140x140 grid with so many possible paths
2. Debugging graph algorithms that branch out and then come back and branch again is so hard because it’s hard to print out the paths. Especially with A* where we stop following one path, go back and then eventually we return to the previous unfinished path.

What I ended up doing is I printed out my full grid with path and spent an hour or so staring at it, trying to find a spot where I can manually find a cheaper route. Thanks to the help from others (running their correct solution with my input), I knew the score was only 12 off which helped a lot because I knew I was looking for a really short detour.

I also knew that all I needed to really calculate from other possible routes was the amount of turns. If there were more turns than in the calculated path, I knew it could never be 12 points cheaper.

I finally did find one case. To be able to manually debug it, I had to simplify it to a smaller size. I eventually ended up with this:

####################
####.##########.#.##
##oooooooooooooo#..#
##o#.##.#######o####
#.o#.##.....#..o#..#
##o#.######.#.#o#.##
##o...#--------oooE#
##o####|#####.###.##
#.o-----..#.#.#...##
##o####.#.#.#.#.####
#So#################
####################

The path marked with o is what my algorithm gave me and one marked with - and | was what I found to be cheaper.

It happened because I was keeping track of only (x, y) positions instead of a state of ((x,y), direction) combo. So when the top path reached the intersection (the left-most o next to E), it had a cost around 3000 because it had turned three times before that intersection. It would then have a cost around 4000 because it has to turn the next time.

The path from bottom costs around 4000 when it reaches the intersection but then continues without an extra turn so it eventually became a few steps cheaper.

Thanks for the help from our lovely Koodiklinikka Advent of Code community who helped me figure out how to avoid this by keeping track of the proper state.

Once I knew that, it still took me a good hour or so to adjust the code to the new one. At one point, my score jumped to ~230 000 and at one point I managed to end up in a loop.

Eventually, all the pieces fell into their spots and I got the correct result and a star.

Part 2

In part 2, we need to find all the shortest paths instead of just one.

As I used the A* which specifically finds one shortest path and my understanding of the algorithm is not very deep, I had no clue how to change it to find all of the paths.

One thing I considered was taking the path from Part 1 and changing each step into a wall one at a time and see if I can reach the goal for each of these iterations. But then I realised that whenever I had found a new path, I’d have to do it again, this time blocking one step in each path and that sounded like a complexity nightmare.

Day 16 marks the first 1 star day. The first part took me out hard and after a bit of tinkering on the second part, I decided I’ll rather not spend all my waking hours today on Advent of Code.