Project Euler #82 - path sum: three ways

Question

enter image description here

Here's my solution:

def main():    
    matrix = [
        [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]
    ]

    size = len(matrix)
    best = [matrix[row][0] for row in range(size)]

    for col in range(1, size):
        column = [matrix[row][col] for row in range(size)]
        tmp = column[:]

        for i in range(size):
            column[i] += best[i] # right

            for j in range(0, i): # up
                if sum([best[j]]+tmp[j:i+1]) < column[i]:
                    column[i] = sum([best[j]]+tmp[j:i+1])

            for k in range(i, size): # bottom
                if sum([best[k]] +tmp[i:k+1]) < column[i]:
                    column[i] = sum([best[k]] +tmp[i:k+1])

        best = column
        #print(best)

    return min(best)


if __name__ == "__main__":
    print(main())

Please advise how it can be improved.

@megawac This solution uses the same strategy described in the article, except that it's already more eloquent. — 200_success
– 200_success, Commented Jan 2, 2014 at 9:26

200_success · Accepted Answer · 2014-01-02 09:30:21Z

To solve the Project Euler challenge, you'll have to handle a large matrix from a file. Therefore, your function should accept the matrix as a parameter.

You used size to represent both the number of rows and the number of columns. I would use two variables to avoid hard-coding the assumption that the input is a square matrix.

Your dynamic programming algorithm is sound. I would use the min() function to avoid finding the minimum by iteration. Also, setting best all at once instead of mutating the elements of column avoids having to copy column into a temporary variable.

def euler82(matrix):
    nrows, ncols = len(matrix), len(matrix[0])
    best = [matrix[row][0] for row in range(nrows)]

    for col in range(1, ncols):
        column = [matrix[row][col] for row in range(nrows)]

        best = [
            # The cost of each cell, plus...
            column[row] +

            # the cost of the cheapest approach to it
            min([
                best[prev_row] + sum(column[prev_row:row:(1 if prev_row <= row else -1)])
                for prev_row in range(nrows)
            ])
            for row in range(nrows)
        ]

        #print(best)

    return min(best)

Stack Exchange Network

Project Euler #82 - path sum: three ways

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Project Euler #82 - path sum: three ways

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions