I woke up early today, opened the day’s puzzle and saw that we’re back to the lava production facility. I knew that meant path finding and those have usually been my Achilles’ heel as recursion is a challenging one for me.
Then I continued reading and found out that we met a a reindeer wearing a hard hat which reminded me of the fantastic story about zoo animals in hats by Rhod Gilbert in Would I Lie To You and I immediately got on a better mood.
Read input
Today’s input is another grid of numbers
89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732Each number represents a height in a topological map. Every 0 is a trailhead and every 9 is a peak.
from collections import namedtuple
Coordinate = namedtuple("Coordinate", ["x", "y"])
def create_grid(inputs):
grid = {}
trailheads = []
for y, row in enumerate(inputs):
for x, cell in enumerate(row):
cell = int(cell)
coordinate = Coordinate(x, y)
grid[coordinate] = cell
if cell == 0:
trailheads.append(coordinate)
return grid, trailheadsAs we construct the grid, we also keep track of all the trailheads because those are the starting points of hiking paths that we need to find.
Part 1
In the first part, we need to find out how many peaks we can reach from each trailhead. To reach a peak, we can only move in cardinal directions (up, down, left, right) and only to another location if it’s exactly one higher than where we currently are.
First, we need a way to get all the neighbouring coordinates so let’s build a helper function. The named tuples really shine here, don’t you think? It’s easy to read on a glance what’s happening.
def get_neighbours(coordinate):
return [
Coordinate(coordinate.x - 1, coordinate.y),
Coordinate(coordinate.x + 1, coordinate.y),
Coordinate(coordinate.x, coordinate.y - 1),
Coordinate(coordinate.x, coordinate.y + 1),
]To find all the paths, we use recursive depth-first search:
def find_paths_to_peak(height, position, grid):
if height == 9:
return [position]
paths = []
for neighbour in get_neighbours(position):
neighbouring_height = grid.get(neighbour)
if neighbouring_height == height + 1:
paths += find_paths_to_peak(neighbouring_height, neighbour, grid)
return pathsOur base case is if we’ve reached the peak in which case we return the current position (wrapped into a list since our recursive function always returns a list).
If we’re not at the peak, we go through every possible neighbour and if it’s 1 higher than where we currently are, we find all paths from there to the peaks.
We then end up with a list of peak positions.
def part_1():
inputs = read_input(10, str)
grid, trailheads = create_grid(inputs)
score = 0
for trailhead in trailheads:
paths = find_paths_to_peak(0, trailhead, grid)
score += len(set(paths))
print(f"Part 1: {score}")To calculate the score, we go through every trailhead and find all the paths for every trailhead. Since we can reach the same peak position through multiple paths, we remove duplicates by converting the list to a set and get its length.
Part 2
In the second part, a trailhead’s rating is how many unique paths there are to peaks.
As a stroke of luck, we already calculate that in the first part. This time, we don’t remove the duplicates and we’re done.
def part_2():
inputs = read_input(10, str)
grid, trailheads = create_grid(inputs)
rating = 0
for trailhead in trailheads:
rating += len(find_paths_to_peak(0, trailhead, grid))
print(f"Part 2: {rating}")I actually first accidentally solved the second part, then realised I need to remove duplicates. When the second part rolled in, I already had the solution ready.
I could have combined the two parts into a single function and only calculate the hikes once. But I like to keep my solutions consistent day to day for easier reading and I don’t care about the overall run time so here we go.
I was done by 8am today, including refactoring and write-up (puzzles open at 7am) so that was quite a change from the usual.