# 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.

### 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() {
.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

The full solution is available on GitHub.