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!