7
\$\begingroup\$

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

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.

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

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.