Finding the Maximum Route in a given input
Question: I have this as a homework and i need to do it in python.

    
    
    Problem:
    The Maximum Route is defined as the maximum total by traversing from the tip of the triangle to its base. Here the maximum route is (3+7+4+9) 23.
    
    3
    7 4
    2 4 6
    8 5 9 3
    
    Now, given a certain triangle, my task is to find the Maximum Route for it. 
    

Not sure how to do it....


Answer: We can solve this problem using backtracking. To do that for each element of
the triangle in any given row, we have to determine the maximum of sum of the
current element and the three connected neighbors in the next row, or

>
>     if elem = triangle[row][col] and the next row is triangle[row+1]
>  
>     then backtrack_elem = max([elem + i for i in connected_neighbors of col
> in row])
>  

First try to find a way to determine `connected_neighbors of col in row`

for an elem in position (row,col), connected neighbor in row = next would be
`[next[col-1],next[col],next[col+1]]` provided `col - 1 >=0` and `col+1 <
len(next)`. Here is am sample implementation

    
    
    >>> def neigh(n,sz):
        return [i for i in (n-1,n,n+1) if 0<=i<sz]
    

This will return the index of the connected neighbors.

now we can write `backtrack_elem = max([elem + i for i in connected_neighbors
of col in row])` as

    
    
    triangle[row][i] = max([elem + next[n] for n in neigh(i,len(next))])
    

and if we iterate the triangle rowwise and curr is any given row then and i is
the ith col index of the row then we can write

    
    
    curr[i]=max(next[n]+e for n in neigh(i,len(next)))
    

now we have to iterate the triangle reading the current and the next row
together. This can be done as

    
    
    for (curr,next) in zip(triangle[-2::-1],triangle[::-1]):
    

and then we use enumerate to generate a tuple of index and the elem itself

    
    
    for (i,e) in enumerate(curr):
    

Clubbing then together we have

    
    
    >>> for (curr,next) in zip(triangle[-2::-1],triangle[::-1]):
        for (i,e) in enumerate(curr):
            curr[i]=max(next[n]+e for n in neigh(i,len(next)))
    

But the above operation is destructive and we have to create a copy of the
original triangle and work on it

    
    
    route = triangle # This will not work, because in python copy is done by reference
    route = triangle[:] #This will also not work, because triangle is a list of list
                        #and individual list would be copied with reference
    

So we have to use the `deepcopy` module

    
    
    import copy
    route = copy.deepcopy(triangle) #This will work
    

and rewrite out traverse as

    
    
    >>> for (curr,next) in zip(route[-2::-1],route[::-1]):
        for (i,e) in enumerate(curr):
            curr[i]=max(next[n]+e for n in neigh(i,len(next)))
    

We end up with another triangle where every elem gives the highest route cost
possible. To get the actual route, we have to use the original triangle and
calculate backward

so for an elem at index `[row,col]`, the highest route cost is
route[row][col]. If it follows the max route, then the next elem should be a
connected neighbor and the route cost should be route[row][col] -
orig[row][col]. If we iterate row wise we can write as

    
    
    i=[x for x in neigh(next,i) if x == curr[i]-orig[i]][0]
    orig[i]
    

and we should loop downwards starting from the peak element. Thus we have

    
    
    >>> for (curr,next,orig) in zip(route,route[1:],triangle):
        print orig[i],
        i=[x for x in neigh(i,len(next)) if next[x] == curr[i]-orig[i]][0]
    

Lets take a bit complex example, as yours is too trivial to solve

    
    
    >>> triangle=[
              [3],
              [7, 4],
              [2, 4, 6],
              [8, 5, 9, 3],
              [15,10,2, 7, 8]
             ]
    
    >>> route=copy.deepcopy(triangle) # Create a Copy
    

Generating the Route

    
    
    >>> for (curr,next) in zip(route[-2::-1],route[::-1]):
        for (i,e) in enumerate(curr):
            curr[i]=max(next[n]+e for n in neigh(i,len(next)))
    
    
    >>> route
    [[37], [34, 31], [25, 27, 26], [23, 20, 19, 11], [15, 10, 2, 7, 8]]
    

and finally we calculate the route

    
    
    >>> def enroute(triangle):
        route=copy.deepcopy(triangle) # Create a Copy
        # Generating the Route
        for (curr,next) in zip(route[-2::-1],route[::-1]): #Read the curr and next row
            for (i,e) in enumerate(curr):
                #Backtrack calculation
                curr[i]=max(next[n]+e for n in neigh(i,len(next)))
        path=[] #Start with the peak elem
        for (curr,next,orig) in zip(route,route[1:],triangle): #Read the curr, next and orig row
            path.append(orig[i])
            i=[x for x in neigh(i,len(next)) if next[x] == curr[i]-orig[i]][0]
        path.append(triangle[-1][i]) #Don't forget the last row which
        return (route[0],path)
    

To Test our triangle we have

    
    
    >>> enroute(triangle)
    ([37], [3, 7, 4, 8, 15])
    

* * *

Reading a comment by jamylak, I realized this problem is similar to Euler 18
but the difference is the representation. The problem in Euler 18 considers a
pyramid where as the problem in this question is of a right angle triangle. As
you can read my reply to his comment I explained the reason why the results
would be different. Nevertheless, this problem can be easily ported to work
with Euler 18. Here is the port

    
    
    >>> def enroute(triangle,neigh=lambda n,sz:[i for i in (n-1,n,n+1) if 0<=i<sz]):
        route=copy.deepcopy(triangle) # Create a Copy
        # Generating the Route
        for (curr,next) in zip(route[-2::-1],route[::-1]): #Read the curr and next row
            for (i,e) in enumerate(curr):
                #Backtrack calculation
                curr[i]=max(next[n]+e for n in neigh(i,len(next)))
        path=[] #Start with the peak elem
        for (curr,next,orig) in zip(route,route[1:],triangle): #Read the curr, next and orig row
            path.append(orig[i])
            i=[x for x in neigh(i,len(next)) if next[x] == curr[i]-orig[i]][0]
        path.append(triangle[-1][i]) #Don't forget the last row which
        return (route[0],path)
    
    >>> enroute(t1) # For Right angle triangle
    ([1116], [75, 64, 82, 87, 82, 75, 77, 65, 41, 72, 71, 70, 91, 66, 98])
    >>> enroute(t1,neigh=lambda n,sz:[i for i in (n,n+1) if i<sz]) # For a Pyramid
    ([1074], [75, 64, 82, 87, 82, 75, 73, 28, 83, 32, 91, 78, 58, 73, 93])
    >>>
    

