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']
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
