# Dynamic Programming with Project Euler problem 67

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()


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.

• 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. – M. Guev Jul 31 '17 at 2:43
• 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. – J_H Jul 31 '17 at 23:17
• The question is tagged python-2.7, so xrange() is still appropriate. – 200_success Sep 6 '17 at 7:19
• 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. – 200_success Sep 6 '17 at 7:22
• I agree with 200_success - thank you for the criticism. Duly noted in the answer (see EDIT). – J_H Sep 6 '17 at 22:00