Dynamic Programming with Project Euler problem 67

Question

I am a beginner with python and programming in general. I started teaching myself about 2 months ago.

I've been working my way through Project Euler and a few similar sites to build my chops, and because I find it fun/rewarding. Below is my first attempt at some simple dynamic programming to come up with the solution to problem 67.

I would appreciate any criticism or advice. One thing in particular that I struggle with is readability (naming variables, comments, etc.). Also, I am largely ignorant when it comes to convention/best practices, so guidance here would be helpful.

pyr = []
with open('problem_67.txt') as f:
 for line in f:
 pyr.append(map(int, line.split()))
f.closed
def best_path(li):
 """Find the max total from top to bottom in a triangular array."""
 saver = {}
 n = len(li)
 # Set values for all points to 0
 for y in xrange(2, n+1):
 for x in xrange(len(li[n-y])):
 saver[(n-y, x)] = 0
 # Establish the max values for the bottom row
 for x in xrange(len(li[n-2])):
 a, b, c = li[n-2][x], li[n-1][x], li[n-1][x+1]
 saver[(n-2, x)] += max(a+b, a+c)
 # Add the highest dict of the two lower options for each other row
 for y in xrange(3, n+1):
 for x in xrange(len(li[n-y])):
 a, b, c = li[n-y][x], saver[(n-(y-1), x)], saver[(n-(y-1), x+1)]
 saver[(n-y, x)] += a + max(b, c)
 return saver[0, 0]
def main():
 print best_path(pyr)
if __name__ == "__main__":
 main()

Answer 1

I recommend running flake8 occasionally, and cleaning up what it complains about. And consider using python3 rather than python2.

If you really want to define a global with pyr = [], then at least name it PYR. Much better for main to call

 print(best_path(get_pyramid()))

and push the init code into a getter. Then you won't be polluting the global namespace with f. (And no need to retain the f.closed debugging statement, once you've convinced yourself that with closed it as advertised.)

EDIT: On reflection, I was viewing this in too mechanical a way. 200_success is correct, all caps is for manifest constants. The real trouble here is gratuitous globals. Scope things down appropriately without polluting the top-level namespace.

Naming the triangular pyramid pyr was a fine choice, better than the parameter name li.

Using xrange is a bit odd, nowadays. Just stick to python3, and range will be perfect.

A name like cost (or distance, or dist) would have been more natural than saver.

If you have your heart set on a triangular map of zeros, this would be more pythonic:

# Set costs for all points to 0
for y, row in enumerate(li):
 for x, val in enumerate(row):
 saver[(x, y)] = 0

But you're using it with +=, so better to instead define saver = collections.defaultdict(int), allowing increment to lazily populate the map.

This line is fairly clear:

 saver[(n-y, x)] += a + max(b, c)

The n-y could have been just y (in several expressions) if you had supplied a third optional argument of -1 for the range. And it seems likely you could move the max(a+b, a+c) expression into this loop, as well, perhaps by padding the bottom of the pyramid with a line of zeros.

Explicitly supplying a tuple as key is a good practice, one worth sticking to here:

return saver[0, 0]

This is a fine comment:

"""Find the max total from top to bottom in a triangular array."""

Writing lots of comments may not be necessary if your identifiers accurately tell the story. Consider renaming the function to best_path_cost, since it returns a scalar cost rather than a path through the pyramid.

This is a fine comment, though I would prefer "costs" over the vague "values":

# Set values for all points to 0

You might consider deleting it, and moving the code into a helper with a descriptive name like get_triangle_of_zeros(). Writing fewer comments leads to writing fewer comments that lie (or bit-rot). Functions typically should be defined with a docstring comment, as you supplied. If a function is very simple, it needs a descriptive name but perhaps no comment.

• M. Guev: Can you explain a bit more what you mean by: The n-y could have been just y (in several expressions) if you had supplied a third optional argument of -1 for the range? I realized that the n was redundant in a few of the expressions, but I feel like I'm missing something.
• J_H: Sure. You wrote, roughly, for y in range(3, n+1, 1): , and the positive increment seemed unnatural to me, since you really wanted to traverse in the opposite direction. I was suggesting something like range(n, 2, -1) so that y would refer to the desired row, rather than using n - y to find that row.
• 200_success: The question is tagged python-2.7, so xrange() is still appropriate.
• 200_success: All caps, by convention, would be used to name a constant. I don't recommend using all caps to name a list that will be appended to.
• J_H: I agree with 200_success - thank you for the criticism. Duly noted in the answer (see EDIT).