Project Euler – Problem 83 Solution

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:

Prob83_01

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

Prob83_02v2

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.

Prob83_03

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

Prob83_04

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

Prob83_05

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:

Prob83_06

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

Prob83_07

This solution runs in 73ms on my laptop.

 

The source code for this solution is here.

1 Comment

  1. Pingback: F# Weekly #6, 2016 | Sergey Tihon's Blog

Leave a Reply

Your email address will not be published.