2
\$\begingroup\$

Project Euler problem 82 asks:

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.

\$\endgroup\$
  • \$\begingroup\$ Here's a interesting read on #82 if you haven't seen it yet \$\endgroup\$ – megawac Jan 1 '14 at 23:30
  • \$\begingroup\$ @megawac This solution uses the same strategy described in the article, except that it's already more eloquent. \$\endgroup\$ – 200_success Jan 2 '14 at 9:26
3
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.