# Minimal path sums

Problems 81, 82, and 83 at Project Euler all ask us to find the minimal path sum through a matrix. I cobbled together bespoke solutions for problems 81 and 82, but I found problem 83 required a little more discipline. I decided to employ a priority queue to move through the matrix. When I was done, I realized I could use the same strategy for problems 81 and 82 with only slight changes.

Since problem 81 is the simplest, let's look at that first.

Rust has a priority queue in the standard library called BinaryHeap. If we use that and create an item for each entry in the matrix, we can put those in the priority queue.

``````use std::collections::BinaryHeap;

#[derive(Eq, PartialEq)]
struct Item {
cost: usize,
row: usize,
col: usize,
}
``````

However, the documentation says it's a max-heap. We want a min-heap. How do we get that? Elsewhere, the docs give an example of Dijkstra's shortest path algorithm. This shows exactly how to do that: we implement `Ord` and `PartialOrd` for our `Item`.

``````use std::cmp::Ordering;

impl Ord for Item {
fn cmp(&self, other: &Self) -> Ordering {
other
.cost
.cmp(&self.cost)
.then_with(|| self.row.cmp(&other.row))
.then_with(|| self.col.cmp(&other.col))
}
}

impl PartialOrd for Item {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
``````

Instead of `self.cost` compared with `other.cost`, we have `other.cost` compared with `self.cost`, switching the max-heap to a min-heap.

Now we can push the top left corner onto the queue and start looking for a path to the bottom right corner by pushing new items onto the queue.

``````fn find_minimal_path_sum(matrix: &[Vec<usize>]) -> Option<usize> {
let size = matrix.len();

let mut done = vec![vec![false; size]; size];

let mut heap = BinaryHeap::new();

// Start at top left corner.
heap.push(Item {
cost: matrix[0][0],
row: 0_usize,
col: 0_usize,
});

while let Some(Item { cost, row, col }) = heap.pop() {
if done[row][col] {
continue;
}
done[row][col] = true;

// Finish at bottom right corner.
if row == size - 1 && col == size - 1 {
return Some(cost);
}

// right
if col + 1 < size {
heap.push(Item {
cost: cost + matrix[row][col + 1],
row,
col: col + 1,
});
}

// down
if row + 1 < size {
heap.push(Item {
cost: cost + matrix[row + 1][col],
row: row + 1,
col,
});
}
}

None
}
``````

The `main` program only needs to read in the matrix and call that function.

``````fn main() {
let contents = std::fs::read_to_string("example.txt").expect("Cannot read file!");

let matrix = contents
.lines()
.map(|line| {
line.split(',')
.map(|n| n.parse::<usize>().unwrap())
.collect::<Vec<_>>()
})
.collect::<Vec<_>>();

dbg!(find_minimal_path_sum(&matrix));
}
``````

But wait, there's more! It turns out there's a Reverse in the standard library as well. This should save us from having to implement `Ord` and `PartialOrd` ourselves. But how does that work?

If we define our `Item` like so, then we can derive `Ord` and `PartialOrd`.

``````use std::cmp::Reverse;
use std::collections::BinaryHeap;

#[derive(Eq, Ord, PartialEq, PartialOrd)]
struct Item {
cost: Reverse<usize>,
row: usize,
col: usize,
}
``````

But now our `cost` isn't a `usize`, it's a `Reverse<usize>`. When we get to something like `cost + matrix[row + 1][col]` the compiler complains that we can't add a `usize` to a `Reverse<usize>`. How do we get our `usize` out of there?

``````  cost as usize     // No.

usize::from(cost) // No.

cost.unwrap()     // No.
``````

Looking more carefully at the docs, we see that `Reverse` is this `struct`:

``````pub struct Reverse<T>(pub T);
``````

With no label, the one and only field in our struct `cost` is named `cost.0`. Thus we can do the above with `cost.0 + matrix[row + 1][col]` and then re-Reverse it before adding it to the queue. The whole thing comes out like this.

``````use std::cmp::Reverse;
use std::collections::BinaryHeap;

#[derive(Eq, Ord, PartialEq, PartialOrd)]
struct Item {
cost: Reverse<usize>,
row: usize,
col: usize,
}

fn main() {
let contents = std::fs::read_to_string("example.txt").expect("Cannot read file!");

let matrix = contents
.lines()
.map(|line| {
line.split(',')
.map(|n| n.parse::<usize>().unwrap())
.collect::<Vec<_>>()
})
.collect::<Vec<_>>();

dbg!(find_minimal_path_sum(&matrix));
}

fn find_minimal_path_sum(matrix: &[Vec<usize>]) -> Option<usize> {
let size = matrix.len();

let mut done = vec![vec![false; size]; size];

let mut heap = BinaryHeap::new();

// Start at top left corner.
heap.push(Item {
cost: Reverse(matrix[0][0]),
row: 0_usize,
col: 0_usize,
});

while let Some(Item { cost, row, col }) = heap.pop() {
if done[row][col] {
continue;
}

done[row][col] = true;

// Finish at bottom right corner.
if row == size - 1 && col == size - 1 {
return Some(cost.0);
}

// right
if col + 1 < size {
heap.push(Item {
cost: Reverse(cost.0 + matrix[row][col + 1]),
row,
col: col + 1,
});
}

// down
if row + 1 < size {
heap.push(Item {
cost: Reverse(cost.0 + matrix[row + 1][col]),
row: row + 1,
col,
});
}
}

None
}
``````

That's a very satisfying solution! What's more, we can solve problem 83 just be adding left and up items to the queue.

``````        // left
if col > 0 {
heap.push(Item {
cost: Reverse(cost.0 + matrix[row][col - 1]),
row,
col: col - 1,
});
}

// up
if row > 0 {
heap.push(Item {
cost: Reverse(cost.0 + matrix[row - 1][col]),
row: row - 1,
col,
});
}
``````

To solve problem 82, we start anywhere in the first column

``````    // Start anywhere on the left side.
for i in 0..size {
heap.push(Item {
cost: Reverse(matrix[i][0]),
row: i,
col: 0,
});
}
``````

and stop anywhere in the last column

``````        // Finish anywhere on the right side.
if col == size - 1 {
return Some(cost.0);
}
``````

keeping only the down, right, and left directions. Keen!