Project Euler 81: Find the minimal path sum from the top left to the bottom right by moving right and down.

Project Euler 81: Find the minimal path sum from the top left to the bottom right by moving right and down.

Written by on 28 January 2012

Topics: Project Euler

Already from the headline of problem 81 of Project Euler it sounds familiar, so lets jump right in to it

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

Find the minimal path sum, in matrix.txt (right click and ‘Save Link/Target As…’), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

This is one of the most classic examples of problems which can be solved using dynamic programming. We have already solved Problem 15 where we used a sort of dynamic programming approach to traverse a grid to find the number of paths through the grid. We also solved  problem 18 with dynamic programming to find the minimum path through a triangle.

Dynamic Programming

I know we have been through this before, but since we will be dealing with exact grid over the next couple of problems I would like to cover it again.

Dynamic programming can be used when we are able to make smaller problems which we can solve and the reuse the solution when we are solving the main problem.

In this case, if we are standing in a specific point, no matter how we got there we can calculate the minimum path from there and to the goal.  And since we can only go down and right we can disregard all the cells above and to the left when looking for the minimal solution – which is exactly why dynamic programming works. This is also known as optimal sub structure as I elaborate on in Problem 18.

Illustrating the solution

If we want to find the minimal solution for the path from a specific cell to the goal we can choose one of two paths down or right. Assuming we know the minimal path from both the cell below and from the cell to the right we can rather easy choose between the going right and going down.

So how do we find this solution? Well if you are on the bottom row next to the goal it is pretty easy to add the two since the minimum path is obviously to go to the right to get to the goal.

This can then be done for all the bottom row as well as the the right row. Now that we know the minimum paths from the black cells we can see that we can find the solution to the grey number since we know the minimum solution to both the cell to the right and below of that cell.

Since we know that the minimum path from the cell to the right is 1287 and the minimum path from the cell below is 368, going down from the grey cell would be the better choice since we want to minimize the solution. So that minimum path from the grey cell is 121 + min(1287,368) = 489.

This can be continued for all cells working us up to the top left cell  in which case we will now the cost of the minimum path through the matrix.

Implementing the solution

Now that we have the general idea we can implement the solution rather easily in C# as

int[,] grid = readInput(filename);
int gridSize = grid.GetLength(0);

//calculate the solution for bottom and right
for (int i = gridSize - 2; i >= 0; i--) {
    grid[gridSize - 1, i] += grid[gridSize - 1, i+1];
    grid[i,gridSize - 1] += grid[i+1, gridSize - 1];
}

for (int i = gridSize - 2; i >= 0; i--) {
    for (int j = gridSize - 2; j >= 0; j--) {
        grid[i, j] += Math.Min(grid[i + 1, j], grid[i, j + 1]);
    }
}

which runs in

In the 80x80 grid the min path is 427337
Solution took 3,2962 ms

So we can find the minimal solution in 3ms even though there is a total of paths through the matrix.

Wrapping up

This is the classical example of dynamic programming. You should get the idea from the description as well as the previously solve problems.

As always you can find the source code here including the method for reading the input file and a method for print the array to check the current state.

14 Comments For This Post I'd Love to Hear Yours!

  1. Jack says:

    Why are you publishing the answers to project Euler questions ?

  2. Kristian says:

    Hi Jack

    I do it for the same reason I do search for solutions my self after finding a solution. To figure out if I have missed something in making a smart solution. And if that is the case I would like at least a pointer to the field of mathematics or computer science needed to solve the problem.

    So my hope is that people who are interested in this kind of problems learn something new and get even more interested in finding the “right” solution instead of just “a” solution.

    I guess I could avoid posting the actual answer, but I am unsure whether that is what you refer to.

    /Kristian

  3. Yair says:

    Hi Kristian,

    Nice blog :)

    I think I understand the solution (well, didn’t look at the code but read the above briefly). I have a few questions.
    basically you suggest to start from right bottom and “climb” up to left top, correct?

    another question:
    what if the numbers were as so:

    422 10
    980 956
    37 331
    the right solution is to go up to 956 and not left to 37
    even if the sum (37+331) is less than (956+331).
    and by your explanation above I couldn’t understand how it solves the problem.

    thanks in advance,
    Yair.

  4. Kristian says:

    It is not completely correct. I suggest starting from the bottom and make a new grid. The entry in each cell is the minimum value to get from that place in the original grid and to the bottom corner.

    In your case It would require several steps. The first one looking like

    – –
    – –
    – 331

    That is trivial. The next step we can calculate the bottom left and the right in the middle since they can only move in one direction. This gives us a grid looking like

    – –
    – 1287
    368 331

    Now we can calculate the upper right corner and the middle left. The upper right only have one possible way so that value will be 1287+10 = 1297. The middle left can go either down or right, so we will choose the smallest one which is down. So the value to go from that spot to the bottom right is 368+980 = 1348 giving us
    – 1297
    1348 1287
    368 331

    Now we can calculate the upper left where we can choose to go down or right. Since the sum to the right is the smallest that is the way to go giving us a result of 1297+422 = 1719.

    I hope this clarifies things.

  5. Yair says:

    Thank you!
    most helpful, And it does clarify my questions.

    thanks again.

  6. Kristian says:

    Great, glad I could make some sense to it. And I completely forgot to say thanks for the compliment.

  7. Sam says:

    Hi, I tried this program the same way your explanation describes it, or at least I think I did. But when my code runs I get the value of 563261. My method is similar to that of number 18. It went from bottom right to top. I’m having a hard time understanding why this does not work. If you emailed me I could send you my code if you like.

    Thanks!

  8. Kristian says:

    Why don’t you post the code here, or on pastebin for that matter. That way everyone can chip in and help you out.

  9. Bjarki Ágúst says:

    Hello Sam.

    I think there is something you’re misunderstanding. You seem to be greedily picking the minimum path, instead of using dynamic programming. What that means is that on each step you go to the next possible square in the grid that has the minimum value. This is not optimal, and will usually not result in the correct answer. If you add the following to your FindBestPath method:

    // ...
    int n = 0;
    while (Column > 0 || Row > 0)
    {
        Console.WriteLine((++n) + ". " + Row + ", " + Column);
        if (Column == 0)
        {
    // ...
    

    then you can see that your program only visits 158 squares, while an optimal algorithm always needs to visit all the 80*80 squares (otherwise, how would it know that there is not another path that is better?).

    I suggest you study the above post better, and try to fix your solution. Let us know if you aren’t able to fix it.

  10. Khaur says:

    You probably already know this, but if you look at the algorithm closely, you don’t even need to store the whole new grid, only the previous line. And if you start from the top left, you can read the values as you go.

    Doing so takes your algorithm from quadratic to linear space complexity, which doesn’t matter here since the problem is small, but it is crucial in live, big-scale applications.

  11. Kristian says:

    I hadn’t thought of that really. But yes you are absolutely right.

  12. Ritesh says:

    Hey Kristian ,
    Can you explain why the greedy algorithm doesn’t work in the problem, as in the code of Sam ?

  13. Kristian says:

    Bjarki explains it as a such. But to elaborate a bit more. Sam takes the minimum value of the step immidiatly down or to the right. However, this does not necessarily the path that leads to the minimum solution.

    To make an exagerated example take the example

    1 1 8
    2 9 9
    2 2 2

    If you stand in the upper left corner and take the minimum value of the right or down you will move along the upper and right most barrier and get a total sum of 21. However the minimum is at the left and lower boundary which would give us a total of 9.

    I hope this explains it.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.