Skip to content

Instantly share code, notes, and snippets.

@abdulmuneer
Created October 10, 2012 19:02
Show Gist options
  • Save abdulmuneer/3867690 to your computer and use it in GitHub Desktop.
Save abdulmuneer/3867690 to your computer and use it in GitHub Desktop.
Program to findout the maximum weight of the tree
'''
@author: A_Muneer
'''
import sys
#file_name = 'tri.txt'
def get_tree(file_name):
with open(file_name) as myfile:
return [line.strip().split() for line in myfile if line.strip()]
def greater(params):
if len(params) == 1:
return int(params[0])
else:
a, b = [int(x) for x in params]
return a if a>b else b
def max_weight(tree, idx=0):
#print "Tree now is: \n", tree
try:
#tree[1] to check for single element row.
next_row, next_tree = tree [1], tree[1:]
except:
return greater(tree[0][idx:idx+2])#base of the tree
else:
row = tree[0]
weight = int(row[idx]) + greater([max_weight(next_tree, idx),
max_weight(next_tree, idx+1)])
return weight
def get_max_weight(file_name):
tree = get_tree(file_name)
return max_weight(tree)
if __name__ == '__main__':
file_name = sys.argv[1]
print get_max_weight(file_name)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment