Advent of code 2021: Day 15
This article is part of a series where I'll be diving head first into the Advent of code 2021. I'll be documenting the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that, I mean I can't look up any other implementations online.
In this article I'll be solving: Advent of code 2021: Day #15.
Part 1
I finally get out of the caves with my submarine, but I have to check which route would involve the least amount of risk getting out of the caves. We get a grid of points like such:
1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581
My submarine has to traverse from the top-left to the bottom-right, while taking the least amount of risk. This is when the actual Dijkstra algorithm comes in to play, instead of when I mentioned it earlier in Day 12. One of the ingredients for Dijkstra is a priority queue. In Rust I know that a lot of people use a BinaryHeap for this. The fun thing is that the documentation for BinaryHeap contains a Dijkstra implementation, so I simply used that one [1]. The code for part 1, went something like this:
use std::fs;
use std::cmp::Ordering;
use std::collections::BinaryHeap;
type Grid = Vec<Vec<Node>>;
#[derive(Debug, Clone)]
struct Node(usize, usize);
#[derive(Debug, Clone)]
struct Edge(usize, usize);
type Edges = Vec<Vec<Edge>>;
fn main() {
let display_string = fs::read_to_string("input")
.unwrap_or("".to_string());
let risk = risk_level(&display_string, 0, 9999);
println!("The risk level is: {:?}", risk);
}
fn to_grid(input: &str) -> Grid {
let mut grid: Grid = vec![];
let mut id = 0;
for line in input.split_terminator("\n") {
let mut points = vec![];
for cha in line.chars() {
let value = cha.to_digit(10).unwrap() as usize;
points.push(Node(id, value));
id += 1;
}
grid.push(points);
}
grid
}
fn to_graph(input: &str) -> Edges {
let grid = to_grid(input);
let size = grid.len();
let mut edges: Edges = vec![vec![]; size.pow(2)];
for y in 0..size {
for x in 0..size {
let current = &grid[y][x];
if let Some(row) = grid.get(y + 1) {
edges[current.0].push(Edge(
row[x].0,
(current.1 + row[x].1) as usize
));
}
if let Some(cell) = grid[y].get(x + 1) {
edges[current.0].push(Edge(
cell.0,
(current.1 + cell.1) as usize
));
}
}
}
edges
}
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
struct State {
cost: usize,
position: usize,
}
impl Ord for State {
fn cmp(&self, other: &Self) -> Ordering {
other.cost.cmp(&self.cost)
.then_with(|| self.position.cmp(&other.position))
}
}
impl PartialOrd for State {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
fn risk_level(input: &str, start: usize, goal: usize) -> Option<usize> {
let edges = to_graph(input);
let mut dist: Vec<_> = vec![usize::MAX; edges.len()];
let mut heap = BinaryHeap::new();
dist[start] = 0;
heap.push(State { cost: 0, position: start });
while let Some(State { cost, position }) = heap.pop() {
if position == goal { return Some(cost / 2); }
if cost > dist[position] { continue; }
for edge in &edges[position] {
let next = State { cost: cost + edge.1, position: edge.0 };
if next.cost < dist[next.position] {
heap.push(next);
dist[next.position] = next.cost;
}
}
}
None
}
For some stupid reason I had to divide the final cost by 2, and I didn’t know why exactly. It got me to the right answer, but it is actually wrong to do so. Which brings me to part 2:
Part 2
In part 2 I found out I never had to do the divide by 2, because I was costing my edges with “too much”. I should’ve just used the cost of the adjacent node. After executing that code, the answer to part 1 had an “off by one” error, which was caused by the fact that in my code I wasn’t taking into account that you should include edges from the left and top of the current node [2]. After those were included, the answer was resolved.
The only trick that was left for part 2 was increasing the graph to 5 times its original size and executing the same algorithm again. I’ve done it a bit more manual than I’ve seen others do it, but it works.
Sources
[1] Rust-lang struct.BinaryHeap
[2] Solution off by 7 but correct for Example input
The full solution is available on GitHub.
