Pages

Monday, June 6, 2011

Maximal sum in a triangle (Project Euler problem 67)

The problem description is here. For a given triangle you have to find the path with the maximum path. Given an input triangle :
3
7 4
2 4 6
9 5 9 3



We can compute the maximum sum path using 2 approaches:

Solution 1 : bottom-up. Build maximum path from bottom.  From the next-to-last row, up to the first, add the maximum corresponding sub-triangle. So the initial triangle becomes iteratively:


3
7    4
11 13 15
9    5    9  3


3
20 19
11 13 15
9    5    9  3


23
20 19
11 13 15
9    5    9  3

So the maximum sum is 23, and the maximum path 
3
7 4
4 6
9 5 9 3

Solution 2: same result is obtained with a top-down approach. Starting from the second row, compute the maximum-sum path to every element. So the initial triangle becomes iteratively:
3
10  7
2 4 6
9 5 9 3

3
10  7
12 14 13
9 5 9 3

3
10  7
12 14 13
21 19 23 16

We get same result for the maximum sum.

Simple python Implementation for the bottom-up solution:
def get_numbers():
    #lines = open("tri_small.txt", "r")    
    lines = open("tri.txt", "r")    
    
    listOfRows = []
    
    for line in lines:
        currRow = [int(x) for x in line.split()]
        listOfRows.append(currRow)
    
    return listOfRows
    
def solve():
    row_list = get_numbers()
    length = len(row_list)
    
    for i in xrange(length-2, -1, -1) :
        len_row = len(row_list[i])                   
        for j in range(0, len_row) :
            row_list[i][j] += max(row_list[i+1][j], row_list[i+1][j+1])
        
    print row_list[0]
    return 0

No comments:

Post a Comment