Shortest path is a classic Computer Science problem. No wonder that it frequently appears in coding challenges like Advent of Code.

Problem description

We are given a map (2-dimensional array of strcitly positive integers), that indicates a risk level in a cavern we must go through.

The goal is to find the lowest total risk from the upper left corner to the bottom right corner.

Part 1

This is a shortest path problem. Two standard BFS algorithms are used in this kind of problem : Dijkstra and A*. The algorithm I used is a BFS algorithm too, but not exactly Dijkstra’s algorithm.

The same data structure trick as in day 9 and day 12 is used again for “border detection”.

The function I wrote take the risk map in argument, and returns a 2-dimensional array that indicates the total risk from the upper left border to any position on the cavern map. Its algorithm 2 steps :

A reference nodes set, called loop_positions in the code, is initialized, with the starting node.

In this puzzle, there is no required backtracking, as only the lowest total risk is asked.

pub fn lowest_total_risk(risk_map: &Array) -> Array {
    let mut total_risks = vec![vec![None; risk_map.len()]; risk_map.len()];

    total_risks[1][1] = Some(0);
    let mut loop_positions = HashSet::new();
    loop_positions.insert((1, 1));
    let mut changed = true;

    while changed {
        changed = false;
        let mut neighbours = HashSet::new();

        for pos in loop_positions {
            for dir in DIRS {
                let next_row = (pos.0 as isize + dir.0) as usize;
                let next_col = (pos.1 as isize + dir.1) as usize;
                if update_total_risk(&mut total_risks, risk_map, pos, (next_row, next_col)) {
                    neighbours.insert((next_row, next_col));
                    changed = true;
                }
            }
        }

        loop_positions = neighbours.clone();
    }

    total_risks
}

An helper function updates the neighbouring nodes total risk, and return true if this value has been changed.

pub fn update_total_risk(total_risks: &mut Array, risk_map: &Array, pos: (usize, usize), next_pos: (usize, usize)) -> bool {
    let total_risk = total_risks[pos.0][pos.1].unwrap();           

    match (risk_map[next_pos.0][next_pos.1], total_risks[next_pos.0][next_pos.1]) {
        (Some(v), Some(t)) => {
            if total_risk + v < t {
                total_risks[next_pos.0][next_pos.1] = Some(total_risk + v);
                return true;
            }
            false
        },
        (Some(v), None) => {
            total_risks[next_pos.0][next_pos.1] = Some(total_risk + v);
            true
        },
        (None, _) => { false }
    }
}

The main function simply calls the BFS algorithm function, and returns the value of the bottom right corner. Please note that this is NOT total_risk_map[risk_map.len()-1][risk_map.len()-1].unwrap() as a border (with None values) has been added during the input data parsing.

pub fn solve_part1(input: &Vec<String>) -> u64 {
    let risk_map = parse_risk_map(input);
    let total_risk_map = lowest_total_risk(&risk_map);
    total_risk_map[risk_map.len()-2][risk_map.len()-2].unwrap()
}

I spent a bit more than 2 hours to reach a correct solution. This is my longest time this year, for a part 1.

Part 2

In the second part, the grid is much larger (25 as many nodes), and the execution time is obviously much greater. The exact same function is used to compute the lowest total risk. The added code calculates the full map.

Two new functions are added. First, let’s calculate the eight tiles types forming the full map. Note that no “border control” is needed here, so the tiles size is exactly the same as the input data size.

pub fn repeat_risk_map(risk_map: &Array, inc: usize) -> Tile {
    let mut new_risk_map = Vec::new();

    for i in 1..risk_map.len()-1 {
        let mut new_risk_row = Vec::new();
        for j in 1..risk_map.len()-1 {
            let mut new_risk = risk_map[i][j].unwrap() + inc as u64;
            if new_risk > 9 {
                new_risk -= 9;
            }
            new_risk_row.push(new_risk);
        }
        new_risk_map.push(new_risk_row);
    }

    new_risk_map
}

Then, the tiles are put on the full map.

pub fn add_tile(risk_map: &mut Array, tiles: &Vec<Tile>, i: usize, j: usize) {
    let tile = &tiles[i + j];
    let base_row = i * (tile.len()) + 1;
    let base_col = j * (tile.len()) + 1;

    for row in 0..tile.len() {
        for col in 0..tile.len() {
            risk_map[base_row + row][base_col + col] = Some(tile[row][col]);
        }
    }
}

Finally, the shortest path function is called, exactly as in part 1, and the lowest total risk is returned.

pub fn solve_part2(input: &Vec<String>) -> u64 {
    let small_risk_map = parse_risk_map(input);
    let small_map_length = small_risk_map.len();
    let large_map_length = 5 * (small_map_length - 2) + 2;
    let mut large_risk_map = vec![vec![None; large_map_length]; large_map_length];
    let mut tiles = Vec::new();

    for i in 0..9 {
        tiles.push(repeat_risk_map(&small_risk_map, i));
    }
    for i in 0..5 {
        for j in 0..5 {
            add_tile(&mut large_risk_map, &tiles, i, j);
        }
    }

    let total_risk_map = lowest_total_risk(&large_risk_map);
    total_risk_map[large_risk_map.len()-2][large_risk_map.len()-2].unwrap()
}

The second part was easier than the first one, and I spent about 55 minutes. However, I lost precious minutes as I had not understood that risk levels can never be equal to zero.

Performances

Part 1 runs in 2 ms (for a 100 * 100 grid), and part 2 in about 250 ms (for a 500 * 500 grid).

In my BFS algorithm implementation, I used a HashSet to store the reference nodes. This is probably not the most efficient structure, and I probably should have used other collections supported in the standard library, like binary trees and binary heaps.