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:


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")

    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;



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) {
                    (current.1 + row[x].1) as usize

            if let Some(cell) = grid[y].get(x + 1) {
                    (current.1 + cell.1) as usize


#[derive(Copy, Clone, Debug, Eq, PartialEq)]
struct State {
    cost: usize,
    position: usize,

impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering {
            .then_with(|| self.position.cmp(&other.position))

impl PartialOrd for State {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {

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] {

                dist[next.position] = next.cost;


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.


[1] Rust-lang struct.BinaryHeap

[2] Solution off by 7 but correct for Example input

The full solution is available on GitHub.