Project Euler — Problem 83 Solution

The prob­lem descrip­tion is here, and click here to see all my oth­er Euler solu­tions in F#.

 

This is a more dif­fi­cult ver­sion of prob­lem 82, and now you can move in all four direc­tions!

As before, we start by load­ing the input data into a 2D array:

Prob83_01

and ini­tial­ize anoth­er matrix of the same size to hold the min­i­mum sum lead­ing to each cell:

Prob83_02v2

What we have done dif­fer­ent­ly this time though, is to choose ini­tial defaults:

  • for the top-left cor­ner (0, 0) the min­i­mum sum is itself
  • for all oth­er cells at (row, col) we’ll always tra­verse 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 prob­lem 82, we’ll add a cou­ple of helper to help us tra­verse both matri­ces:

Prob83_04

and we’ll find the new min­i­mum sum to each cell by tak­ing the min­i­mum from the four direc­tions:

Prob83_05

Unlike before, we can’t iso­late to opti­miz­ing one col­umn at a time, and instead we’ll need to tra­verse the whole matrix. For bet­ter cache local­i­ty, we’ll tra­verse row first and recur­sive­ly opti­mize the whole matrix until no more opti­miza­tion is pos­si­ble:

Prob83_06

Final­ly, find the final val­ue for the bot­tom-right cor­ner of the sum matrix:

Prob83_07

This solu­tion runs in 73ms on my lap­top.

 

The source code for this solu­tion is here.