Project Euler problem 67

I've used Project Euler a number of times in the past as a learning platform; whether it's to keep some skills sharp or to learn something new. A few months ago, I revisited some old problems when I was learning the basics of Rust.

Problem 67 is simple as its core; in a pyramid of numbers, find the maximum path sum of numbers from the top to the bottom. The example pyramid is:

      3
    7   4
  2   4   6
8   5   9   3

The earlier problem (problem 18) is a much simpler version of the problem, where the input is small and allows for very naive recursive solution:

fn max_sum_recursion_dumb(v: &Vec<Vec<u32>>, i: usize, j: usize) -> u32 {
    if i >= v.len() {
        return 0;
    }

    let left = max_sum_recursion_dumb(&v, i+1, j);
    let right = max_sum_recursion_dumb(&v, i+1, j+1);

    v[i][j] + left.max(right)
}

The basic idea is that to get the total sum of the current node, get the total sum of the left child node and the total sum of the right child node, and return the sum that is larger, with the current node's value added to it.

The function can be called easily, assuming the pyramid is represented as a two-dimensional vector and we start at the top (zero indexes):

println!("{}", max_sum_recursion_dumb(&input_data, 0, 0));

The problem with this approach is there is a ton of re-computation happening, which only gets worse as the input gets larger (as in problem 67).

If sticking with this solution, the technique to get around recomputing for the same input over and over again is to memoize (or cache) results of previous calls. This results in a top-down dynamic programming solution:

fn max_sum_recursion(v: &Vec<Vec<u32>>,
                     i: usize,
                     j: usize,
                     mut cache: &mut HashMap<(usize, usize), u32>) -> u32 {

    if i >= v.len() {
        return 0;
    }

    if let Some(rv) = cache.get(&(i,j)) {
        return *rv;
    }

    let left = max_sum_recursion(&v, i+1, j, &mut cache);
    let right = max_sum_recursion(&v, i+1, j+1, &mut cache);

    let rv = v[i][j] + left.max(right);
    cache.insert((i,j), rv);
    return rv;
}

This can then be called with an extra parameter for the cache:

let mut cache = HashMap::new();
println!("{}", max_sum_recursion(&input_data, 0, 0, &mut cache));

But to be honest, although the solution worked well, I don't like the look of the code at all. In the original Perl version of this solution that I'd written years ago, I just used the Memoize module, so the code remained very much like the first function, but with an extra line outside of the function to enable memoization.

But in this Rust version of the function, I have to pass around mutable references, which I don't want to do unless absolutely necessary, and I didn't feel like it was absolutely necessary.

Looking at the core of how the function finds the maximum sum - once you unravel the recursion - it actually starts at the bottom of the pyramid, compares pairs of numbers for the larger number, adds it to the parent number on the row above, and repeats, until we get to the top. So what if, instead of starting at the top, the code just started from the bottom and bubbled up to the top?

Using the example in the problem description, the pyramid starts like:

      3
    7   4
  2   4   6
8   5   9   3

Then we take the bottom row (8, 5, 9, 3), get the largest number of each pair, and add it to the number of the parent node in the row above. So, after this step, we end up with the following pyramid:

      3
    7   4
  10  13  15
8   5   9   3

And then we repeat for the row above:

      3
    20  19
  10  13  15
8   5   9   3

And then once more for the top row:

      23
    20  19
  10  13  15
8   5   9   3

Finally, the top of the pyramid contains the maximum path sum, 23.

fn max_sum_norecursion(v: &Vec<Vec<u32>>) -> u32 {
    let mut sums = v[v.len() - 1].clone();

    for i in (1 .. v.len()).rev() {
        for j in 1 .. v[i].len() {
            let max = sums[j].max(sums[j-1]);
            sums[j-1] = max + v[i-1][j-1];
        }
        sums.pop();
    }

    sums[0]
}

This bottom-up dynamic programming approach has resulted in - I think - better looking Rust code, without the need for recursion, and without the need to hand around a mutable reference for caching.

It was fun to come back and solve this problem in a different way, even if the original reason I even revisited it was just to learn some basic Rust.