Project Euler — Problem 82 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 81, but still, as you can’t move left so we can still opti­mize one col­umn at a time.

First, let’s read the input file into a 2D array:

Prob82_01

and ini­tial­ize anoth­er matrix with the same size to store the min­i­mum sum to each of the cells:

Prob82_02

In order to avoid mis­cal­cu­la­tions due to unini­tial­ized cells (i.e. if we had ini­tial­ized them with 0), I’ve ini­tial­ized the cells by assum­ing that we have moved right all the way, hence this line:

    else matrix.[row, 0..col] |> Array.sum

which adds up all the cells to the left of, and includ­ing, the (row, col) cell.

Next, we’ll add a cou­ple of helper func­tions to work out the new min­i­mum sum to the cell at (row, col) if we had moved up, down, or right:

Prob82_03

We can now use these func­tions to opti­mize the columns one at a time.

The tricky thing here is that we might need a few pass­es to con­verge onto the true min­i­mum sum path to each of the cells. For exam­ple, in order to work out the min­i­mum sum at (row, col) we need to know the min­i­mum sum at (row-1, col) and (row+1, col). But to work out the min­i­mum sum at (row-1, col) we need to know the min­i­mum sum at (row, col)!

So, instead, we’ll recur­sive­ly try to opti­mize each cell in the col­umn until it can’t be opti­mized any­more:

Prob82_04

At the end of the snip­pet above, we opti­mized the columns one at a time from left to right. (I could have equal­ly includ­ed this as part of the recur­sive func­tion, but it would intro­duce anoth­er lev­el of nest­ing which is why I opt­ed against it)

And final­ly, look for the min­i­mum sum on the right-most col­umn in the sum matrix to answer the ques­tion:

Prob82_05

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

 

The source code for this solu­tion is here.