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.