Problem:

For a given pyramid find out the largest possible sum of numbers while travelling down from the top.

========================================================================

EXAMPLE 1:

1

2 3

4 5 6

The possible routes going down on this pyramid would be

1+2+4

1+2+5

1+3+5

1+3+6

ANS: 10

========================================================================

EXAMPLE 2:

1

2 3

4 5 6

7 8 9 1

The possible routes going down on this pyramid would be

1+2+4+7

1+2+4+8

1+2+5+8

1+2+5+9

1+3+5+8

1+3+5+9

1+3+6+9

1+3+6+1

ANS: 19

Solution in Python:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def findMaxHeight(items,pyramidHeight):
'''
This def returns the greatest path.
Logic:  From second last line for each element find if its left or right child is greatest.
Replace that element with sum of that element and the greatest child.
In the end we'll have replace the pyramid with sum of greatest element.
The only remaining element at  is the answer
'''

i = pyramidHeight - 2
while i >= 0:
j = 0
while j <= i:
greaterPath = items[i+1][j] if items[i+1][j] > items[i+1][j+1] else items[i+1][j+1]
items[i][j] = items[i][j] + greaterPath
j = j + 1
i = i - 1

return items

items = []
pyramidHeight = 0
i = 0
firstLine = True
for line in open(fileName):
line = line.splitlines()
if firstLine:
firstLine = False
pyramidHeight = int(line)
continue
#create 2d list
items.append([])
#splits each line by "," and converts it to int and generates another list
items[i] = [int(x) for x in line.split(",")]
i = i + 1

if pyramidHeight != i:
print "Houston, We've Got a Problem\nPyramid height specified in file doesn't match"
assert False

return items,pyramidHeight

print "Greatest path for pyramid 1 is %s" % findMaxHeight(*readDataFromFile("pyramid1.txt"))
print "Greatest path for pyramid 2 is %s" % findMaxHeight(*readDataFromFile("pyramid2.txt"))