By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
3
7 4
2 4 6
8 5 9 3That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
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 23NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)
https://projecteuler.net/problem=18
Whenever talk of “routes” or “paths” pops up, we should be thinking about graph theory. Graphs – a collection of nodes and edges – show up in many situations. They make great models of real-world situations such as roads, social networks, climate — the list is endless. Here, a graph is just what the problem needs.
The triangle of numbers can be transformed into a graph. Numbers’ positions within the triangle would become nodes. A node is connected to the two nodes below it. The number values themselves become weights of these edges. The question then becomes that of finding a path through this graph.
Finding efficient paths through a graph is a question that often comes up in graph theory. If we wanted to drive to New York from Boston, we surely wouldn’t take a detour through Chicago, would we? Sometimes, finding the best path isn’t so easy. Graph theory offers us powerful tools to deal with shortest or longest paths. That tool is Dijkstra’s algorithm.
But wait…isn’t the problem asking for the “longest” or “heaviest” path? Yes, but there’s a trick if the graph is directed and acyclic. Negate all of the numbers! The biggest number ends up being the smallest number. The problem is now finding the “shortest” or “lightest” path through the triangle graph.
Before playing around with Dijkstra, we need a graph to work with. How will the triangle be transformed into a graph? Let’s consider another triangle.
1 and 2 are added to members of the first row to get the numbers underneath them. 2 and 3 are added to members of the second row to get numbers underneath them. 3 and 4 are added to members of the third row to get numbers underneath them. A pattern emerges! In general, a number n on row r has the numbers n+r and n+r+1 below it. How can r be expressed in terms of n?
The key is triangular numbers. They show up on the right side of the triangle. We know that a triangular number T_n can be found by \sum_{i=1}^{n}i, which is n(n+1)/2 (thanks Gauss!). The integral inverse of this function maps a number to its resident row’s number! After applying the quadratic formula and double checking, we now know that
r=\Bigg\lceil{\frac{\sqrt{8n+1}-1}{2}}\Bigg\rceil \tag{1}Of course, this is a bit overkill for graph construction (one can just do it recursively), but I think this formula can be useful in future problems. Anyway, let’s ingest the file and toss the numbers in a list.
# Ingest and flatten
numbers = []
with open('triangle.txt') as f:
for line in f:
for number in line.split():
numbers.append(int(number))
Now, let’s use networkx to build the graph as pictured above. Weights won’t be added yet, just nodes.
# Create graph G = nx.DiGraph() for i in range(1, len(numbers) + 1): G.add_node(i)
Connections are “located” using n \to n+r and n \to n+r+1. r is defined in Equation 1. Connections are weighted using numbers from the file.
# Make connections (n -> n + r and n -> n + r + 1) r = lambda n: math.ceil((math.sqrt(8*n + 1) - 1) / 2) for i in range(1, len(numbers) - len(last_row) + 1): # Don't attempt to connect the last row G.add_edge(i, i + r(i), weight = numbers[i - 1]) G.add_edge(i, i + r(i) + 1, weight = numbers[i - 1])
A destination node (-1) is added so that the bottom row can connect to it.
# Connect the bottom row to a destination node G.add_node(-1) for i in range(len(numbers) - len(last_row) + 1, len(numbers) + 1): G.add_edge(i, -1, weight = numbers[i - 1])
Finally, use networkx‘s implementation of the longest path to find the path from node 1 to node -1.
# Find the longest path and its associated path weight path = nx.dag_longest_path(G, weight = 'weight') path_weight = nx.path_weight(G, path, weight = 'weight') print(path) print(path_weight)
Letting it loose on the 15-row triangle:
λ py p18solution.py [1, 3, 6, 9, 13, 19, 25, 32, 41, 51, 62, 74, 87, 100, 115, -1] 1074
It also takes care of the 100-row triangle from Problem 67 with ease.
λ py p18solution.py [1, 2, 4, 8, 13, 19, 26, 33, 42, 51, 62, 73, 86, 100, 115, 131, 148, 166, 184, 203, 224, 245, 267, 2 91, 315, 341, 367, 395, 424, 453, 483, 515, 548, 582, 617, 653, 690, 728, 767, 806, 846, 888, 931, 9 74, 1019, 1065, 1112, 1160, 1209, 1258, 1308, 1359, 1412, 1465, 1520, 1576, 1632, 1689, 1747, 1806, 1867, 1928, 1990, 2054, 2119, 2185, 2252, 2320, 2388, 2458, 2528, 2599, 2671, 2744, 2818, 2893, 2970 , 3047, 3125, 3205, 3286, 3367, 3449, 3532, 3616, 3701, 3788, 3875, 3963, 4052, 4143, 4234, 4327, 44 21, 4515, 4611, 4708, 4806, 4904, 5004, -1] 7273