Project Euler 18/67: Maximum Path Sum

Question

The complete problem definition can be summarized as "find the largest sum of for paths from the top to the bottom of a triangle of integers". I decided to read the triangle in from a file which can be found here.

My solution

#!/usr/bin/python
"""chicks' answer to Euler Project problem #18"""

import sys
import string
import re
import pprint

# read command line
argcount = len(sys.argv)
if argcount <= 1:
    raise ValueError("missing filename on command line")
triangle_filename = sys.argv[1]
print str(argcount) + " arguments: " + triangle_filename

# read file
with open(triangle_filename, "r") as triangle_file:
    lines = triangle_file.readlines()
    print str(len(lines)) + " lines read"

triangle = []
for y in lines:
    y = string.strip(y)
    fields = re.split(r'\s+', y)
    int_fields = []
    for f in fields:
        int_fields.append(int(f))
    triangle.insert(0, int_fields)
    c = len(fields)

pretty = pprint.PrettyPrinter(indent=4)
#pretty.pprint(triangle)

rows = len(triangle) - 1
for z in range(0, rows):
    row = triangle[z]
    pretty.pprint(row)

    entries = len(row) - 1
    for y in range(0, entries):
        a = row[y]
        b = row[y + 1]
        #print "comparing " + str(a) + " and " + str(b)
        adder = 0
        if a >= b:
            adder = a
        else:
            adder = b

        triangle[z + 1][y] += adder


answer = str(triangle[rows][0])
print "ANSWER:" + answer

Desired Focus

I left performance out because I'm more interested in having pythonicly correct and maintainable code than squeezing out a few ms. I have run this through pylint and fixed everything it suggested. I am still a beginner at python so I'm presuming there are more pythonic ways to do some of this.

Answer 1

High-level comments:

• There are several print statements left in this file which look like they were in for debugging purposes. Maybe useful to you, but means nothing to me when I’m running the file. These should be commented out, or (since you’re using source control) removed entirely.

• There are no comments in this file. That makes it quite hard to follow what’s going on – even if this is a simple problem that you understand well, that won’t be the case when you come to re-read this in six months.

  Explain why the code is written this way, and how the program structures relate back to the original problem. It makes it much easier to review and improve.

• Everything runs at the top-level. You should break some of this down into functions – it will make the code easier to reuse and follow.

A few smaller suggestions:

• On line 24, you’re using regexes to split a line on whitespace, but Python already has a string method split() that does this for you.

  You can rewrite these few lines as:

  for line in lines:
      fields = line.strip().split()
  

  Notice that I’m also calling the strip() method directly on line, and I’ve renamed the loop variable to make it clearer what I’m doing.

• On lines 25–7, a common antipattern:

  int_fields = []
  for f in fields:
      int_fields.append(int(f))
  

  It’s cleaner and more Pythonic to do this with a list comprehension:

  int_fields = [int(f) for f in fields]
  

  Note also that you store the value of len(fields) in a variable here – but then never actually use it.

• In lines 35-6, you have a common Python antipattern:

  for z in range(0, rows):
      row = triangle[z]
  

  It’s always better to iterate over the items directly, i.e. for row in triangle. In this case you’re actually using z further down, so you should use enumerate():

  for idx, row in enumerate(triangle):
      # do stuff with idx and row
  

• On lines 40–50, there are several problems:

  • You don’t need to initialise the variable adder to 0.

  • You can get its value in a single line:

    adder = max(a, b)
    

  • The names a and b are not very meaningful, and are only used once. It would be cleaner to write this as:

    triangle[z+1][y] += max(row[y], row[y+1])
    

    You should also rename y and z to be more meaningful.

• You’re calling range(0, x) in several places. Since it defaults to a start of 0, you can drop the first argument to reduce visual noise: range(x).

Answer 2

Organization

Putting a lot of code top-level is going to blow up in more complex programs, I suggest dividing your code in functions, pieces of code that only do one thing, like:

def get_filename_from_command_line():
   ...

def read_triangle_from_filename(filename):
   ...

def largest_sum_in_trangle(triangle):
   ...

And then calling them as needed in a high level main function. This also removes the need for comments like # read command line or # read file as the function name will tell that.

Unused code

c = len(fields)

But c is never used.

List comprehension

You do:

int_fields = []
    for f in fields:
        int_fields.append(int(f))

But it is so much more readable to write:

int_fields = [int(field) for field in fields]

max

You write:

adder = 0
if a >= b:
    adder = a
else:
    adder = b

While you could save 4 lines and make the code easier to understand by doing:

adder = max(a, b)

Weird iter name

for y in lines:

Why y? i is not the best but at least standard, anyhow I suggest a descriptive name like line

Avoid mutating when it is sensible to do so

The lines (where y should be named line):

y = string.strip(y)
fields = re.split(r'\s+', y)

Should become:

fields = re.split(r'\s+', string.strip(line))

Because there is no benefit in modifying a variable just to use it modified the line after, simplify and modify it just the line after.

Conciseness

Nobody likes golfed code, but wasting lines also makes the code less readable, the whole:

    a = row[y]
    b = row[y + 1]
    #print "comparing " + str(a) + " and " + str(b)
    adder = 0
    if a >= b:
        adder = a
    else:
        adder = b

    triangle[z + 1][y] += adder

Can be re-written while maintaining the same functionality as:

triangle[z + 1][y] += max(row[y], row[y + 1])

That I find not only shorter, but also much easier to read and understand.

Answer 3

Storing the rows of triangle in bottom-to-top order is unnatural, and accomplishing it through repeated use of triangle.insert(0, …), rather than reversing the entire list at the end, is inefficient.

There is entirely too much code to read in triangle. By taking advantage of fileinput and list comprehensions, the code would be simpler, and you could eliminate an error case. (If no filename is given, read from standard input.) you don't need to strip() or use a regular expression; split() just does the right thing. I also don't see the point of the variable c. The first three stanzas could just be:

import fileinput
triangle = [map(int, line.split() for line in fileinput.input())]
print '{0} lines read'.format(len(triangle))

For the inner loop of the calculation, use the max() function:

triangle[z + 1][y] = max(row[y], row[y + 1])