Project Euler # 81 Minimum path sum ** code produces the right result for a case and the wrong result for another

Question

Code gets correct output on a case and a wrong output on another.

6 seriously painful hours of trying to modify/debug/find anything wrong with the code and seriously, I'm going crazy!!!!!!!!!!!!!!

I tried the following:

1. recursion bottom to top

2. recursion top to bottom

3. replaced recursion with regular loops

4. I completely erased the code and started it from scratch for most probably more than 20 times so far

5. I even searched about the problem and I found a solution very similar to my approach, I ran it, it gave me the correct result however my code keeps producing magic outputs.

6. Please explain why the f** this code is not working!!!

7. I even tried to accumulate the total in the function parameters and still the same problem.

problem statement: In the 5 by 5 matrix below: (check link)

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.

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. Here's the link: https://projecteuler.net/problem=81

correct output is 427337 and the code gives 563261 and sometimes 490000 + something(I really can't remember) Please help me fix this code, instead of showing me any other approaches to the problem. ****** NOTE: the code produces the right output (2427 like the problem states) for the 5 * 5 matrix (you'll find it at the bottom of my code under the name 'test'

def get_matrix(filename):
    """Return a list of lists containing n * n matrix."""
    with open(filename) as matrix:
        return [[int(number) for number in row.split(',')] for row in matrix]


def minimize_matrix(matrix, row, column):
    """Return minimum path sum in matrix from top left to bottom right."""
    if row == 0 and column == 0:
        return matrix[row][column]
    if row and column:
        minimum = min(matrix[row - 1][column], matrix[row][column - 1])
        if minimum == matrix[row - 1][column]:
            return matrix[row][column] + minimize_matrix(matrix, row - 1, column)
        if minimum == matrix[row][column - 1]:
            return matrix[row][column] + minimize_matrix(matrix, row, column - 1)
    if not row and column:
        return matrix[row][column] + minimize_matrix(matrix, row, column - 1)
    if not column and row:
        return matrix[row][column] + minimize_matrix(matrix, row - 1, column)


if __name__ == '__main__':
    mt = get_matrix('p081_matrix.txt')
    ln = len(mt) - 1
    test = [[131, 673, 234, 103, 18],
           [201, 96, 342, 965, 150],
           [630, 803, 746, 422, 111],
           [537, 699, 497, 121, 956],
           [805, 732, 524, 37, 331]]
    print(minimize_matrix(mt, 79, 79))

Answer 1

As @Ben mentions, you have implemented a greedy algorithm to solve this problem, and a greedy algorithm won't always work. Consider the matrix:

[[ 1, 99, 99, 99,  1],
 [ 1,  2,  1,  3,  1],
 [ 1,  3,  1,  3,  1],
 [ 1,  3,  1,  2,  1],
 [ 1, 99, 99, 99,  1]]

If you start from the top-left, or from the bottom right, you will follow the 1's until you reach the first corner. At this point, you're stuck passing through the 99's, because those are the only legal moves you have left. As such, this greedy algorithm returns the "minimum path sum" value of 303, which is clearly wrong.

If add a counter to count the number of times minimize_matrix() is called, you'll see it is called 9 times for the 5x5 matrix, and 159 times for the 80x80 matrix. It is clearly not examining all paths through the matrices.

---

Let's fix your code. The problem lies here:

if row and column:
    minimum = min(matrix[row - 1][column], matrix[row][column - 1])
    if minimum == matrix[row - 1][column]:
        return matrix[row][column] + minimize_matrix(matrix, row - 1, column)
    if minimum == matrix[row][column - 1]:
        return matrix[row][column] + minimize_matrix(matrix, row, column - 1)

As you walk though the matrix, when you arrive at a cell where there exists both a move "up" and "left", you look to see which one is to a smaller cell value, and proceed to move that direction.

What you want is to "try" a step "up", and see how expensive that path is, and then also "try" a step to the "left", and see how expensive that path was. Once the cost of both directions is known, return the cheapest.

if row and column:
    up = matrix[row][column] + minimize_matrix(matrix, row - 1, column)
    left = matrix[row][column] + minimize_matrix(matrix, row, column - 1)
    return min(up, left)

With this change, we get the correct minimum path sum of 11 for the above matrix, and the correct minimum path sum of 2427 for your 5x5 test matrix.

---

The elephant in the room. In each case, the minimize_matrix() call is executed 251 times. Why so many?

minimize_matrix() is called for the bottom-right cell exactly once. The only way to call the mimimize_matrix() on the cell above it is from the bottom-right corner. Similarly, the only way to call minimize_matrix() on the cell to the left of it is also from the bottom-right cell. Similarly for all the cells on the right edge and the bottom edge:

[[   ,   ,   ,   ,  1],
 [   ,   ,   ,   ,  1],
 [   ,   ,   ,   ,  1],
 [   ,   ,   ,   ,  1],
 [  1,  1,  1,  1,  1]]

The cell one up & left of the bottom-right cell can be called from cell below it, and the cell to the right of it, so it can be called twice. The cell above it can be called twice from this cell, and once from the cell to the right of it, so it can be called 3 times; 4 times for the one above it, and 5 for the one above that. Same for the cells to the left:

[[   ,   ,   ,  5,  1],
 [   ,   ,   ,  4,  1],
 [   ,   ,   ,  3,  1],
 [  5,  4,  3,  2,  1],
 [  1,  1,  1,  1,  1]]

The mimimize_matrix(matrix, 2, 2) will be call from (2,3) & (3,2), which were each called 3 times, so it will be called 6 times.

[[   ,   ,   ,  5,  1],
 [   ,   ,   ,  4,  1],
 [   ,   ,  6,  3,  1],
 [  5,  4,  3,  2,  1],
 [  1,  1,  1,  1,  1]]

If we continue our counting ...

[[ 70, 35, 15,  5,  1],
 [ 35, 20, 10,  4,  1],
 [ 15, 10,  6,  3,  1],
 [  5,  4,  3,  2,  1],
 [  1,  1,  1,  1,  1]]

... and if we add up all of the counts, we get 251.

Any guesses as to the number of calls to minimize_matrix() when given a 80x80 matrix?

92_045_125_813_734_238_026_462_263_037_378_063_990_076_729_139

There is a reason we've been asking you to a) not use greedy methods, and b) not use brute force methods. You've done this problem before:

• Project Euler #67
• Project Euler #18

... but those were triangles and you were going for the maximum sum. Only only differences is now you have a square and you need the minimum, but the approach is exactly the same.

Answer 2

It looks like you are trying a greedy solution, where at each step you move in the direction that decreases the most. This won’t always give correct solution, as sometimes you should take the worse immediate step which leads to a better path later on.

For instance, given

[[1, 10, 1, 1],
 [5, 10, 1, 1],
 [5, 10, 1, 1],
 [5,  5, 5, 1]]

the greedy algorithm will follow the 5s, but it’s better in the long run to first take a 10 and then follow the 1s.

I think you’re also starting from the bottom right and going to top left, correct? (Of course a correct solution will lead to the same answer.) In this case, it looks like for the test 5 by 5 matrix a greedy solution works if you start from bottom right. However, if you start from top left and go to bottom right the greedy solution will not work and the test case would have been more helpful..