proj euler 18 first attemp

18.py

# Proj Euler #18... NOT CORRECT!
########################################################
### Kind of just started calculating from largest 
### number in bottom line going all the way up. 
###	Not really correct. Need to think about this more.
###########################################################

#import sys
#import time

tri = '''75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 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 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''
	
splits = tri.split('\n')

tri_list = []
for line in splits:
	nums = []
	line = line.split(' ')
	for num in line:
		numint = int(num)
		nums.append(numint)
	tri_list.append(nums)
		
tri_list.reverse() #note: reverses in place
for line in tri_list:
	print line

###################################################################
def mk_path(pos):
	path_reverse = []

	i = 0
	for line in tri_list:
	
		# find largest element
		largest = 0
		position = 0
		
		### HOW TO DEAL WITH DUPLICATES??
		if(i == 0):
			line_sort = sorted(line, reverse=True)
			largest = line_sort[pos]

			ii = 0
			dups = 0
			for x in line:
				if x == largest:
					position = ii
					dups += 1
				ii += 1
			if dups > 1:
				print "duplicate in bottom rung"

		else:
			last_position = path_reverse[-1] # get last tuple
			last_position = int(last_position[1]) # get position from tuple
			
			try: ### Hmm how to test if out of range?
				if line[last_position - 1] >= line[last_position] and last_position != 0: #dont want neg
					largest = line[last_position - 1]
					position = last_position - 1
				else:
					largest = line[last_position]
					position = last_position
			except:
				if len(line) != 1: # not tip of pyramid
					#print "getting next at:", last_position - 1
					largest = line[last_position - 1]
					position = last_position - 1
				else:
					#tip of pyramid
					largest = line[0]
					position = 0
		
		# add to the path listing
		for x in line:
			if x == largest:
				path_reverse.append((largest, position))
				break
				
		#print path_reverse
		i += 1
		
	return path_reverse
#################################################################3

def try_sums():
	ln = len(tri_list[0])
	for x in range (0, ln - 1):
		path_reverse = mk_path(x)
		sum = 0
		for tupl in path_reverse:
			print tupl[0]
			sum += tupl[0]
		print "total sum:", sum
			

try_sums()

'''

path_reverse = mk_path(0)
		
print "values, bottom up:"
sum = 0
for tupl in path_reverse:
	print tupl[0]
	sum += tupl[0]
	
print "total sum:", sum

'''








#for cpp array style
'''
sys.stdout.write("{")
for line in tri_list:
	i = 0
	sys.stdout.write("{")
	for x in line:
		i += 1
		sys.stdout.write(x)
		if i != len(line):
			sys.stdout.write(',')
	sys.stdout.write("},")
sys.stdout.write("}")
'''