GO VOTE!
I’m publishing this problem out of sequence because I just recently solved it, and wanted to make sure it got out to everyone. It’s also closely related to the Day 10 solution I wrote about last week, so I felt it fit in.
Day 17 starts out as a shortest path problem through a weighted graph with a twist.
You need to navigate a crucible filled with lava through a city in such a way as to minimize the heat loss. You are given a map of the city with the amount of heat the crucible will lose at each point, like this:
2413432311323
3215453535623
3255245654254
3446585845452
4546657867536
1438598798454
4457876987766
3637877979653
4654967986887
4564679986453
1224686865563
2546548887735
4322674655533You start in the upper left corner, and need to get to the lower left with the lowest heat loss possible. At each block, you can go straight, or turn left or right, but not backwards. Easy enough, right?
Not so fast — the crucible you are pushing cannot travel for more than three blocks in a straight line. Once it’s gone three blocks in a straight line, it must turn left or right.
In other words, not a simple weighted search at all… And that’s just part 1…
Approach
I’ll be honest, I had no idea how to approach this at all initially. The straight line stuff gave me fits until I did some reading on Reddit. After looking at a few posts and some thoughts from others, I settled on a modification of Dijkstra’s path finding algorithm.
Djikstra’s Algorithm
Edsger Djikstra (pornounced "die-k-stra") was a Dutch computer scientist who, among other achievements, formulated a way to find the shortest path through a graph, map, or maze when every path between places has a different cost. He came up with it trying to figure out the best way to get from Rotterdam to Groningen — it turns out there are several, and finding the shortest was not trivial. The algorithm he developed, and which we still use today, is most accurately called a shortest path algorithm, but is better known by the eponymous Djikstra’s algorithm.
The algorithm is simple in structure — given a known start $s$ and a known end $e$, the shortest path is found by:
- Marking every node on the map as unvisited.
- Assign a known distance from every node to the starting node $s$. For $s$, the distance is $0$ — for every other node, it’s $\infty$.
- Find the unvisited node with the smallest distance from $s$. Call this $curr$.
- For each unvisited neighbor of $curr$, called $neighbor$:
a. Calculate and store the distance to it from $s$ by adding the distance from $s$ to $curr$ to the distance from $curr$ to $neighbor$.
b. Remove $curr$ from the unvisited nodes list. - When all the nodes have been visited, the distance from $s$ to $e$ will be stored in $e$.
In practice, you check for whether you are looking at $e$ when looking for $neighbors$, rather than figuring out all the distances in the map. You can store $curr$ as the previous node in $neighbor$ to get the actual shortest path. By starting at $e$ and following the previous nodes recorded, you have the shortest actual path between $s$ and $e$.
Part 1
For this problem, you don’t need to know the path to take, just the cost of getting there. Normally, a straight application of Djikstra would work, but there is always a complication with AoC.
The complication is that you can’t just take into account the cost of getting to any given block, because you are not free to travel to every neighbor node at any time. Remember that the crucible can only travel in one direction for a maximum of three blocks — after that, it has to turn. This has two implications when implementing Djikstra:
- You have to limit your selection of neighbors based on how far you’ve already traveled in a straight line.
- Depending on when you turn, there may be more than one way to get to any node with the same cost.
This last bit isn’t as obvious, but look at this part of the sample map:
241 >v1 v41
321 A: 3v1 B: v21
325 3>e >>eBoth paths start in the upper right, but the follow different courses. Path A moves to the right, then down, then right again. Path B moves down, then right. Both end at the same place, marked as e.
The cost of both paths A and B are the same as well, namely 13 (A costs 4+2+2+5, and B costs 3+3+2+5). Both also enter the lower right corner traveling right.
However, to continue from here, path B has to turn, since it has moved straight three blocks in a row already. In contrase, Acan continue to the right since it’s only moved straight two blocks in a row.
What this means is that, for this problem, the definition of "neighbor" in Djikstra is bigger that just any adjacent block. It encompasses:
- The location of the adjacent block, of course
- The direction we traveled to get there
- The number of straight moves we’ve taken
These data are enough to uniquely identify each neighbor node. Since this is basically additional state data, you create a struct State to track the three pieces of info given above.
#[derive(Copy, Clone, Eq, PartialEq, Hash)]
struct State {
loc: (isize, isize),
direction: (isize, isize),
moves: usize,
}You also create another struct QState, which will be used to track and select the closest unvisited node, based on the cost to get to that node
#[derive(Copy, Clone, Eq, PartialEq)]
struct QState {
cost: isize,
state: State,
}You can find the QState with the lowest cost by implementing the Ord trait properly:
impl Ord for QState {
fn cmp(&self, other: &Self) -> Ordering {
// Notice that we flip the ordering on costs
// In case of a tie we compare moves, then positions - this step is
// necessary to make implementations of `PartialEq`
// and `Ord` consistent.
other.cost.cmp(&self.cost)
.then_with(|| self.state.moves.cmp(&other.state.moves))
.then_with(|| self.state.loc.cmp(&other.state.loc))
}
}By swapping other and &self in the initial .cmp() call, you ensure lower values bubble up first.
After parsing the input, you create two new structures.
First, let mut visited: HashSet<State> = HashSet::new(); tracks all the visited nodes. Whenever you process any node, you check if it’s here first — if so, you can skip processing. After the node is processed, you add it to this set. This is also why State carries the Hash trait.
Next, let mut heap = BinaryHeap::new(); implements a priority queue for picking the closest unvisited node. You store the QState structs here. Using the Ord trait above and the properties of a heap, every pop() call removes the node with the lowest cost.
Now, you can start by populating the heap with your starting points. Start in the upper left corner, which means we can only go two directions: right or down. You push those two possibilities onto heap:
// Our first states from the start
heap.push(QState{cost: 0,
state: State { loc: (0, 0), direction: (1, 0), moves: 1 } });
heap.push(QState{cost: 0,
state: State { loc: (0, 0), direction: (0, 1), moves: 1 } });You start a loop, popping the lowest cost item from the heap. In case of a tie, the .then_with() clauses in the Ord trait help pick the one with the lowest number of moves, or the location closest to the start. At the top of the loop, you do some sanity checks as well for the end of the search, and whether this is the fourth move in a straight line:
while let Some(QState { cost, state }) = heap.pop() {
// Are we at the goal?
if state.loc == end { return cost; }
// Have we already come more than 3 straight steps to get here?
if state.moves > 3 { continue; }Now, you can start figuring out who the neighbors are. Start another loop to get all the directions you can move, calculate the neighbors and the costs to get to them, and push them onto the priority queue:
let directions: [(isize, isize); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];
for new_direction in directions {
// Get the new direction
let new_loc = (state.loc.0 + new_direction.0,
state.loc.1 + new_direction.1);
// Check that it's not out of bounds
if new_loc.0 < 0 ||
new_loc.1 < 0 ||
new_loc.0 >= city.len() as isize ||
new_loc.1 >= city.len() as isize {
continue;
}
let mut new_moves = state.moves + 1;
// If we're moving in a new direction, set moves=1
if state.direction != new_direction {
new_moves = 1;
}
// Build the new state
let new_state = State { loc: new_loc,
direction: new_direction,
moves: new_moves };
// Have we visited this node like this before?
if visited.contains(&new_state) {
continue;
}
visited.insert(new_state);
// Calculate the cost from here
let mut new_cost = cost +
<u32 as TryInto<isize>>::try_into(city[new_loc.0 as usize][new_loc.1 as usize]
.to_digit(10).expect("Not a number!")).expect("Not an isize!");
heap.push(QState { cost: new_cost, state: new_state });And running this comes up with…. the wrong answer.
Lamentations
I tried everything I could, but I couldn’t figure it out. For months, this problem sat unfinished.
So, I decided that maybe I wasn’t all that familiar with Djikstra’s algorithm as I thought, and decided to go back to basics. A fellow Redditor posted an in-depth tutorial on the shortest path algorithm, applying it to this problem specifically. They were using Python, and their code followed a different structure — for example, they used a simple dictionary instead of a priority queue to store the set of neighbors.
Using this tutorial, I rewrote my part 1 code. Twice. I looked at another Python solution and did some more Reddit reading. I grabbed another sample input file as well which continued to give the wrong answer. I debugged my code multiple times, but the solution eluded me.
For two days. I couldn’t find the problem.
Then I looked at the tutorial again, and one snippet finally caught my eye:
# Go straight if we can
if distance < 10:
move_and_add_state(cost=current_cost, x=x, y=y,
dx=dx, dy=dy, distance=distance+1)
# Turn left and right if we can
if distance >= 4:
move_and_add_state(cost=current_cost, x=x, y=y, dx=dy, dy=-dx, distance=1)
move_and_add_state(cost=current_cost, x=x, y=y, dx=-dy, dy=dx, distance=1)Can you see it? In this code, they only go three ways away from the current node — they have a special case for moving straight, then they check the left and right turns.
In my code, I check all four directions from the current node, with a special case for going straight. By checking all four directions, my code lets you go backwards as well. The problem is, that’s not allowed per the problem description above.
So, I added the following additional constraint to the directions loop to stop you from going backwards:
// Don't go backwards
if (state.direction.0 == 1 && new_direction.0 == -1) ||
(state.direction.0 == -1 && new_direction.0 == 1) ||
(state.direction.1 == 1 && new_direction.1 == -1) ||
(state.direction.1 == -1 && new_direction.1 == 1) {
continue;
}And lo and behold, this finally gave the right answer.
How long did that discovery take? Roughly 10 months, with two intense days at the end — I couldn’t solve this in December 2023. I found it and fixed it in late October 2024.
Part 2
The complication for part 2 was trivial compared to my problems with part one. With part 1 done, part two took about ten minutes.
For part 2, the elves have a super crucible that has to move at least four blocks in a straight line before it can turn. However, it can only go straight for ten blocks before it has to turn.
Given the solution for part 1, part 2 just adds some additional constraints on the number of moves allowed when finding the neighbors. In the main loop, you stop if you’ve gone straight for 10 blocks:
while let Some(QState { cost, state }) = heap.pop() {
// Are we at the goal?
if state.loc == end { return cost; }
// Have we already come more than 10 straight steps to get here?
if state.moves > 10 { continue; }And when figuring out the neighbors to consider, you check if you’re turning too soon:
for new_direction in directions {
// Make sure we're not turning until we've gone at least four moves
if state.moves < 4 && state.direction != new_direction {
continue;
}That’s it — the code is the same otherwise, and yields the correct result.
Summary
You can find my code here as always. I know it could be better, but I’m glad it’s finally done.
Figuring out part 1 took me two solid days when I started looking at it again in October. It had me questioning my worth as a coder, teacher, and human being.
Why? Well, I teach coding for a living. I write this blog to help support self-taught coders. I’ve written a curriculum on data structures and algorithms. What does is say when I can’t even solve a moderately complex problem using a well-known technique? It was humbling at the least.
One bright spot for me was that I didn’t give up on it. Sure, it took me longer than I think it should have, but finishing last is still better than not finishing at all…
It also got me energized to take on the other problems from last year’s contest that I didn’t solve back then. It’s good practice for the upcoming Advent of Code.