Project Euler #18 - how to brute force all possible paths in tree-like structure using Python?

Question

Am trying to learn Python the Atlantic way and am stuck on Project Euler #18.

All of the stuff I can find on the web (and there's a LOT more googling that happened beyond that) is some variation on 'well you COULD brute force it, but here's a more elegant solution'...

I get it, I totally do. There are really neat solutions out there, and I look forward to the day where the phrase 'acyclic graph' conjures up something more than a hazy, 1 megapixel resolution in my head. But I need to walk before I run here, see the state, and toy around with the brute force answer.

So, question: how do I generate (enumerate?) all valid paths for the triangle in Project Euler #18 and store them in an appropriate python data structure? (A list of lists is my initial inclination?). I don't want the answer - I want to know how to brute force all the paths and store them into a data structure.

Here's what I've got. I'm definitely looping over the data set wrong. The desired behavior would be to go 'depth first(?)' rather than just looping over each row ineffectually.. I read ch. 3 of Norvig's book but couldn't translate the psuedo-code. Tried reading over the AIMA python library for ch. 3 but it makes too many leaps.

triangle = [
    [75],
    [95, 64],
    [17, 47, 82],
    [18, 35, 87, 10],
    [20,  4, 82, 47, 65],
    [19,  1, 23, 75,  3, 34],
    [88,  2, 77, 73,  7, 63, 67],
    [99, 65,  4, 28,  6, 16, 70, 92],
    [41, 41, 26, 56, 83, 40, 80, 70, 33],
    [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
    [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
    [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
    [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
    [63, 66,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
    [04, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23],
]


def expand_node(r, c):
    return [[r+1,c+0],[r+1,c+1]]

all_paths = []
my_path = []

for i in xrange(0, len(triangle)):
    for j in xrange(0, len(triangle[i])):
        print 'row ', i, ' and col ', j, ' value is ', triangle[i][j]
        ??my_path = somehow chain these together???
        if my_path not in all_paths
            all_paths.append(my_path)

Answers that avoid external libraries (like itertools) preferred.

Answer 1

It's easier to use recursion here:

def all_paths(r, c):
    current = triangle[r][c]
    if r < len(triangle) - 1:
        below_paths = all_paths(r+1, c) + all_paths(r+1, c+1)
        return [[current] + path for path in below_paths]
    else:
        return [[current]]

Here, the idea is that all_paths(r, c) return all paths starting at row r, column c, which is usually obtained by recursively taking all paths from both nodes below it, and prepending the current element to all of them.

If we're at the last row, we just return the path consisting of a single element.

To get all paths starting from the top, call all_paths(0, 0).

This function can then easily be modified to return the sums of each path rather than the paths themselves, and with further modification it can return only the largest sum rather than all of them. The "proper way" to solve this problem is essentially just a memoized version of that.