Project Euler – Problem 83 Solution

Yan Cui

I help clients go faster for less using serverless technologies.

The real-time data platform that empowers developers to build innovative products faster and more reliably than ever before.

The problem description is here, and click here to see all my other Euler solutions in F#.

This is a more difficult version of problem 82, and now you can move in all four directions!

As before, we start by loading the input data into a 2D array:

and initialize another matrix of the same size to hold the minimum sum leading to each cell:

What we have done differently this time though, is to choose initial defaults:

• for the top-left corner (0, 0) the minimum sum is itself
• for all other cells at (row, col) we’ll always traverse right and then down
• if row = 0, then this equates to only move right until we reach col
• if col = 0, then this equates to only move down until we reach row

e.g.

Next, as we did for the problem 82, we’ll add a couple of helper to help us traverse both matrices:

and we’ll find the new minimum sum to each cell by taking the minimum from the four directions:

Unlike before, we can’t isolate to optimizing one column at a time, and instead we’ll need to traverse the whole matrix. For better cache locality, we’ll traverse row first and recursively optimize the whole matrix until no more optimization is possible:

Finally, find the final value for the bottom-right corner of the sum matrix:

This solution runs in 73ms on my laptop.

The source code for this solution is here.