Project Euler Question 18 - finding the longest route through a triangle

Euler Question 18 involved finding the longest route down a triangle.

This was done by giving numbers to each of the nodes in the triangle, working out the routes in number terms and then working out how to generate the same pattern and then working out how to list up all the routes in a list of lists.

The data - values for each node in the triangle - was put in one long string that was parsed into a dictionary.

The list of routes was then processed to find out the longest route.

Problems were:

(1) formulating exactly how to find the routes - this needed some diagramming out to work out that simply numbering the nodes in the triangle and then tracing through the numbers produced a regular pattern that could easily be adapted.

(2) Not realising that a recursive call to a function was the easiest way to actually process the routes.  Initially I  tried mixing in the actual route generation with loops.

(3) Not really understanding that a list variable pointed to the list and hence trying to copy a route in the form of a list did not really work.  Instead I had to use extend to add to a nil list to copy.

(4) Also I then had to use append to extend the list with a new node number.



Here is some extend and append differences:


EXAMPLE 1:

append appends a single element. extend appends a list of elements.

Note that if you pass a list to append, it still adds one element:

>>> a = [1, 2, 3]
>>> a.append([4, 5, 6])
>>> a
[1, 2, 3, [4, 5, 6]]

EXAMPLE 2:

append adds an element to a list, extend concatenates the first list with another list. (Or another iterable, it doesn't have to be a list.)

>>> li = ['a', 'b', 'mpilgrim', 'z', 'example']
>>> li
['a', 'b', 'mpilgrim', 'z', 'example']
>>> li.append("new")               
>>> li
['a', 'b', 'mpilgrim', 'z', 'example', 'new']
>>> li.insert(2, "new")            
>>> li
['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new']
>>> li.extend(["two", "elements"]) 
>>> li
['a', 'b', 'new', 'mpilgrim', 'z', 'example', 'new', 'two', 'elements']

From Dive into Python .

Both from Stackoverflow extend vs append



'''
Created on 2012/11/03

@author: malcolm
'''

def generateRoutes(routesList,layer):
    
    #passes a list of routes and the layer in which it is (you need this to work out the offset).  Note you dont have to specify the type of argument passed
    
    newRoutes = []  #construct a list of new routes - i.e. double the number of the routes past
    
    for route in routesList:  
        madeRouteOne = []  
        madeRouteTwo = []
        lastNode = route[len(route)-1]  #Remember to use len(list)-1 for the index.
        increment = lastNode + layer 
        madeRouteOne.extend(route) #you cannot go madeRoute1 = route as this simply points madeRoute1 to route in memory
        madeRouteTwo.extend(route) #you have to use extend rather than append here - this is to get round the problems with copying
        madeRouteOne.append(increment) #you have to use append rather than extend here
        madeRouteTwo.append(increment + 1)
        newRoutes.append(madeRouteOne) #and use append here
        newRoutes.append(madeRouteTwo)
        
    return newRoutes

        
myRoutes = [[1]]  #start at the top of the triangle

for i in range(14):  #14 is the number of layers in the Euler problem.
    myRoutes = generateRoutes(myRoutes, i+1) #recursive - the return from the function call is used in the next function call
    
print(myRoutes)  #to check it worked OK
    
numberString = "759564174782183587102004824765190123750334880277730763679965042806167092414126568340807033414872334732371694295371446525439152975114701133287773177839681757917152381714914358502729486366046889536730731669874031046298272309709873933853600423"
numberDic = {}


#numberDic holds the integer value taken from numberString for each point in the triangle, starting from number 1 at the peak
for i in range (0,240,2):  #len(numberString) would be better than 240 here
    numberDic[i/2+1] = int(numberString[i:i+2]) #remember range will only go up to 238
    

highestTotal = 0
highestRoute = myRoutes[0]  
routeLength = len(myRoutes[0])  #to give a more general result

for route in myRoutes:
    total = 0
    for node in route:
        total += numberDic[node] 
    if total > highestTotal:
        highestTotal = total
        highestRoute = route
        
print(highestTotal)
for i in range(len(highestRoute)):
    print(numberDic[highestRoute[i]])  #highestRoute[i] goes through all the nodes in the highest route and then looks them up in the dictionary