4
\$\begingroup\$

I have implemented the maximum path sum of a triangle of integers (problem 18 in project euler) and I am wondering how I can improve my solution. My solution is below:

def problem18(triangle, height):
    return dp_triangle(triangle, height, 0, 0, dict())

def dp_triangle(triangle, height, row, col, maxs):
    if row == height - 1:
        return int(triangle[row][col])

    keyLeft = str(row + 1) + "," + str(col)
    keyRight = str(row + 1) + "," + str(col + 1)

    if keyLeft in maxs:
        maxLeft = maxs[keyLeft]
    else:
        maxLeft = dp_triangle(triangle, height, row + 1, col, maxs)
        maxs[keyLeft] = maxLeft

    if keyRight in maxs:
        maxRight = maxs[keyRight]
    else:
        maxRight = dp_triangle(triangle, height, row + 1, col + 1, maxs)
        maxs[keyRight] = maxRight

    return max(maxLeft, maxRight) + int(triangle[row][col])

To call this function I have the following:

def main(argv):
    with open(argv[1], 'r') as f:
        triangle = f.readlines()

    height = len(triangle)

    triangle = [x.strip().split() for x in triangle]

    print(problem18(triangle, height))

I just pass a text file with the triangle of numbers to the program. These numbers are separated by whitespace.

\$\endgroup\$
  • 1
    \$\begingroup\$ Do you have an example of how you call this function. It would mean reviews don't have to guess how to use your function and just improve the code. \$\endgroup\$ – Peilonrayz Feb 22 '17 at 15:36
  • \$\begingroup\$ Thanks for the input. I just added an input with a main() function showing how I call it. Please let me know if you need any more information. For reference, a sample data set can be found here: projecteuler.net/problem=18 \$\endgroup\$ – Robert Grossman Feb 22 '17 at 16:10
  • \$\begingroup\$ This problem is a classic example of dynamic programming. Try taking a look at Dreamshire \$\endgroup\$ – Tomáš Král Feb 26 '17 at 17:06
2
\$\begingroup\$

dp_triangle(triangle, height, row, col) depends on three things: dp_triangle(triangle, height, row + 1, col), dp_triangle(triangle, height, row + 1, col + 1), and triangle[row][col]. Therefore it's not necessary to cache more than one row at a time. With that insight you should be able to refactor it to not need dict() at all.

I actually prefer to solve this problem by going down rather than up. That is to say, I define my intermediate result as v(row, col) = max(v(row-1, col-1), v(row-1, col)) + triangle[row][col]. Then the double-array of triangle can be processed in order using a simple for loop, as opposed to in reverse using a slightly more complicated for loop.

\$\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.