Python Implementation of Problem 67
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 67
Thinking from the bottom up got the answer
Problem:
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 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.
NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2^99 altogether! If you could check one trillion (10^12) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)
1"""
2Project Euler Problem 67
3
4Thinking from the bottom up got the answer
5
6Problem:
7
8By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top
9to bottom is 23.
10
113
127 4
132 4 6
148 5 9 3
15
16That is, 3 + 7 + 4 + 9 = 23.
17
18Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file
19containing a triangle with one-hundred rows.
20
21NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem,
22as there are 2^99 altogether! If you could check one trillion (10^12) routes every second it would take over twenty
23billion years to check them all. There is an efficient algorithm to solve it. ;o)
24"""
25from .lib.triangles import reduce_triangle
26from .lib.utils import get_data_file
27
28
29def main() -> int:
30 rows = []
31 for line in get_data_file("p0067_triangle.txt").splitlines():
32 rows.append([int(x) for x in line.split()])
33 return reduce_triangle(rows)