In Problem 82 of Project Euler we are continuing to look at the same problem we considered in Problem 81. The problem reads

NOTE: This problem is a more challenging version of Problem 81.

The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

131673234103182019634296515063080374642211153769949712195680573252437331

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 left column to the right column.

The big difference here is that we are now allowed to move up as well as down, and that means we can’t make as small sub problems as before. However, since we are not allowed to move left we can still slice the matrix into columns and solve smaller problems that way. So dynamic programming is still a viable solution.

We need to move from somewhere in the first column to somewhere in the last column. So let us calculate the cheapest way for each of the entries in the first column and then find the smallest of those.

## Solving for a column

The information we want to get for the column is the smallest value to get from each entry in that column to somewhere in the last column. When we are standing in the last column answering this is trivial. So assume that we now stand in the next to last column and let’s figure out how we solve that problem.

When we stand in one of the entries we have three options, we can go up, right or down. So the question is which of them will give us the shorter path and how do we break this? The thing we need to know here is that all numbers are positive. So if we find that the minimal path is to go up, the minimal path for the entry above cannot be to go down.

That means we can make two sweeps over the column. One sweep going down checking if the cheaper solution is to go up or right. For the first entry we only calculate the price for going to the right. For the second entry we can check if it is cheaper to go up to the first and then right, or go to the right directly. It is possible that it would be cheaper for the first entry to go down, but in that case it would not be beneficial to go up for the second entry. In case we want to go up we already know the solution for continuing to go up as that problem is already solved. This is the reason we can compare the right and the up paths.

The second sweep goes up checking if it would be cheaper to go down rather than the previously found solution. Since we start from below we can check if the already found solution of going up or right is more expensive of going down. This we do for each of the entries.

Now we have solved for a column, so for each entry we know the cheapest path from there to the right side. So now we can take the column to the left until we are at the first column

## Coding the solution

I am not sure I have come up with the best description of the solution, but I think that once you see the code you should be able to convince your self that it is a possible way to find a solution

int[,] grid = readInput(filename); int gridSize = grid.GetLength(0); int[] sol = new int[gridSize]; //initialise solution for (int i = 0; i < gridSize; i++) { sol[i] = grid[i, gridSize - 1]; } for (int i = gridSize - 2; i >= 0; i--) { // Traverse down sol[0] += grid[0, i]; for (int j = 1; j < gridSize; j++) { sol[j] = Math.Min(sol[j - 1] + grid[j, i], sol[j] + grid[j, i]); } //Traverse up for (int j = gridSize - 2; j >= 0; j--) { sol[j] = Math.Min(sol[j], sol[j+1] + grid[j,i]); } }

The solution can then be found with the command sol.Min(). A solution that gives us

In the 80x80 grid the min path is 260324 Solution took 3,0768 ms

Which is about the same execution time as the first solution.

## Wrapping it up

Another problem successfully solved with a rather clever algorithm compared to brute force, where I doubt it can be done at all. As usual you can find the source code for download if you like.

As I mentioned I am uncertain if my explanation is good enough, and in case it isn’t don’t hesitate to ask questions, or come with comments regarding it.

nice…but what would be the approach if we are allowed to move left also…

means left,right,up and down ??

In short: we need a shortest-path algorithm.

Little more detail:

We can turn the matrix into a graph, such that each cell is a vertex, and every cell has an edge to the cell above, below, to the left and to the right. Then this is a simple shortest-path problem which can easily be solved with an algorithm like Dijkstra’s algorithm or the A* search algorithm. We simply apply the algorithm to every cell in the first column against every cell in the last column, and take the minimum length of those. If we want more speed and can afford to use more memory, we could instead use an all-pairs shortest-path algorithm like the Floyd–Warshall algorithm, to avoid recomputation.

Hope that helps.

The question you ask Atul is more or less the problem stated in Problem 83

Hi,

I have one doubt regarding this code.

now suppose after this code i.e checking cheaper path is by moving right or by moving up and then right.

here bcoz sol[j+1] was min if we go up and then right // calculated previously

there could be test case where sol[j+1] + grid[j,i] is minimum …and if it is then we have added same value at grid[j,i] twice ….then dat would be wrong.??

could you please clarify my doubt.please let me knw if you didnt get my question

thanks in advance

If as you say sol[j+1] + grid[j,i] is the smaller of the two then that is assigned to sol[j], otherwise the value of sol[j] stays the same. So you will never add the value in the grid twice.

ok this means…for second sweep .i.e

sol[j] = Math.Min(sol[j], sol[j+1] + grid[j,i]);

sol[j] will be assigned to sol[j+1] + grid[j,i] only if previous sol[j+1] has min value….if it move right directly instead of moving up and then right reason being that grid does not contain -ve number.i guess my understanding is correct ??

In the first sweep you consider whether it is cheaper to

1. Move right

2. Move up

We can do that since we already know the cost for moving from both the cell above to the right edge and the cost of moving from the cell to the right and to the right egde.

In the second sweep you are comparing whether or not it is cheaper to

1. Move down

2. Perform the decision in the first sweep.

So if what you ask is what I think, then yes.

For given example( 5 x 5 matrix ) output expected = 994 but i am getting 694.

i have commented my modification in your code and this is what i meant in my previous comment.

here is the link :-

http://ideone.com/k9aOr#view_edit_box

check modification ….after /*CHANGES MADE */ in above link.

i have also removed -> using System.Numerics; as it was throwing some error.

Using my code or your code, I get the exact same solution of 694. I have also verified by hand that this is indeed the correct solution. So I am uncertain what the problem is.

The reason that you are not getting 994 is that the entry in row=2 column=3 is 42 and not 342 in your input.

thank you kristian very much for your replies.

i had one doubt as i asked you in above conversation . so both code are giving right output …so i guess my thinking was correct about the condition i had added.

thanks again

Hi Kristian ,

Here is my approach , in this code I am not finding min for sol[j] in 2 sweeps … i have managed to do it one sweep.hence reducing the time complexity of the algorithm.

here is my code.

http://ideone.com/oalLm#view_edit_box

please let me know if it fail for some test case.

Hi Atul

Thanks for posting an alternative solution, I haven’t tested it in detail but it is always fun to see other people approach.

I would like to challenge you regarding the smaller time complexity. If you use the typical Big-O notation or big Theta as we can use in this case you will get the following for a problem with m rows and n columns.

We need to sweep all columns twice which each consist of m entries. That gives us a complexity of 2nm. Using big O notation you usually disregard the constant part, so you end up with O(nm). Which will be the exact same complexity as you.

The reason for disregarding the constant is that in order to actually compare things we need to analyse the complexity of the for loop.

I consider the Math.min to be a comparison and an assignment. I have two loops and in each loop I make one comparison to see which is smaller and then assign that to a variable. That gives us two comparisons and two assignments.

In your one loop you have one comparison in line 39 which in the majority of the time will be false, that gives you another comparison in line 52. If that is true you have one comparison and one assignment due to the minA. If not you have up to three comparisons and one assignment due to minB.

So my question to you would be, which one of these are faster? That is difficult to tell. Which is also why you usually disregard the constants in complexity analysis.

/Kristian

Hi Kristian,

Sorry for my previous comment. yes time complexity i.e big O notation will remain same for both the code.

better term to use is code optimization rather then time complexity.

i have further optimized my code. In this code checking has been reduced.

http://ideone.com/oalLm#view_edit_box

Btw , thank you for your code and explanation .I read your solution first and then i tried to solve it with little different approach.

I am sure that I have the same idea with you, but can not get the right answer, can you help me figure out which place of my code is wrong?

I use c++

main idea of the code is as follows:

for(int j = M-2; j >= 0; –j)

{

for(int i = M-1; i >= 0; –i)

{

value1 = value2 = value3 = Max; //Max = 100000000000,which means that this three is init to be the greatest,

value1 = matrix[i][j] + matrix[i][j+1];//the same line

if(i-1>=0)//up if it is the first line ,they just can not go up, but they can go down anyway;

value2 = matrix[i][j] + matrix[i-1][j] + matrix[i-1][j+1];

if(i+1 < M)//down if it is the final line ,it can not go down at all.

value3 = matrix[i][j] + matrix[i+1][j] + matrix[i+1][j+1];

//find the smallest calue among the three

value1 = min(value1, value2);

value1 = min(value1, value3);

//then get it

matrix[i][j] = value1;

}

}

//find the minest of the first row

It seems that you check both up and down in the same sweep. I don’t believe you can do that.

You would need to make a sweep down and a sweep up for each row.

Nice solution! What if there was an additional requirement that the minimum path has exactly k steps, could this be incorporated in this solution without having to use a different approach?

Nope, this solution wouldn’t work in this case, you wont be able to split the problem into independent subproblems. So in case you want to do something like that I guess you need some sort of “real” pathfinding algorithm. You can probably get some inspiration from Problem 83.

Hm, okay :/ Because I’ve been tasked with finding an algorithm that runs in polynomial time for a variation of this problem:

Given an n x n matrix.

* I start in bottom left corner.

* I may go up/down/right.

* I need to end somewhere in the last column.

* I need to do it in exactly k steps (where n <= k <= n^2).

(and naturally, it should be the minimum cost path).

You could modify the algorithm to use at maximum k steps I believe. You could do that by keeping track of the number of moves used to move to the current place from the end and then calculate the minimum distance to the lower left corner. If that is larger than k, then the price should be infinite. It would require some book keeping, but could be done.

However, using exactly k steps seems to be a bit more of a problem. And I do believe in some cases you would find a solution which is a minimum path and then find two squares with low cost and jump up and down between them such that you end up with k steps. So at least in some cases this question would give some very odd paths.

Ah, sorry I forgot one of the requirements: No element may be visited twice. Only zero or one time.

First, love all your euler posts. I’ve been learning so much. I always try to solve the problem before checking this site so I came up with a bit of a different solution. I check both up and down in each sweep and it runs in about 80ms (on a pretty powerful machine). Just though I’d add my solution here.

https://github.com/smbell/euler/blob/master/p82.py

How will this code work if u have obstacles in the path?

Say the code is to be stopped if -1 is encountered?

Thanks for the excellent post. I was wondering of there were values like -infinity as the values i.e the element can not be traversed.

Hi Kristian,

Thanks for this nice solution… I was wondering if it would be possible to track back the route that is the minimum, and add the steps (cells) in an array, in order to display this route in the grid? Similar to the orange textcolor in the introduction of the problem.

I’ve translated your example to PHP by the way.