Solving the sliding pyramid problem in Python3

Question

A simple set of functions which solves the sliding pyramid problem. In summary, the task is to find the path from top to bottom of a triangular grid of numbers that has the smallest sum. The program uses the file input.txt as input.

from time import time

def build_tree():
    with open("input.txt", "r") as file:
        lines = file.readlines()
    list_tree = []
    for line in lines[1:]:
        list_tree.append([int(n) for n in line.strip().split(" ")])

    return list_tree

def min_sum(tree):
    doug = list(reversed(tree))
    above = doug[0]
    for row in doug[1:]:
        below = row
        for index, n in enumerate(below):
            below[index] += min(above[index],above[index+1])
        above = below

    return above[0]

if __name__ == "__main__":
    a = time()
    tree = build_tree()
    print(min_sum(tree), time() - a)

These samples are simple, but I appreciate any feedback.

Answer 1

My main critiques are:

• doug is a baffling variable name.
• You shouldn't have to store the entire file in memory, nor should you have to invert the triangle. Doing so hurts scalability. You should be able to process each line as you read it.

Instead of your build_tree() implementation, I recommend using a generator function to parse the input, such that you only need to store one line at a time.

min_sum() could be made more elegant without relying so much on indexes.

def triangle_rows(filename):
    with open(filename) as f:
        int(next(f))    # Skip first line, which specifies the number of rows
        for line in f:
            yield [int(entry) for entry in line.split()]

def min_sum(triangle):
    row = next(triangle)
    for row_below in triangle:
        row = [min(l, r) for l, r in zip(
            [a + b for a, b in zip(row + [row[-1]], row_below)],
            [a + b for a, b in zip([row[0]] + row, row_below)]
        )]
    return min(*row)

if __name__ == '__main__':
    print(min_sum(triangle_rows('input.txt')))

Answer 2

The build_tree() function can make use of a list comprehension and avoid creating an extra list created by readlines() in memory:

def build_tree():
    with open("input.txt") as file:
        next(file)  # skip first line

        return [int(n) for line in file for n in line.strip().split(" ")]

Note the use of next() to skip the first line.

Answer 3

I feel lazy to run your program, but here are few suggestions:

• Perfectionism: Your program works with the assumption that the input file has valid data, it fails otherwise. So you have a door for improvements around here.
• I noticed you leave a blank line before each return statement. PEP8 does not mention that, AFAIK.
• Leave space between each , and the next element of a parenthesized expression. For example in min_sum(), you could write below[index] += min(above[index], above[index+1]) instead of below[index] += min(above[index],above[index+1]).
• Do not leave space between an operator and its operands, in a parenthesized expression. In your main, for example, write print(min_sum(tree), time()-a) instead of print(min_sum(tree), time() - a)