Starting from the top of the number’s triangle and moving to adjacent numbers on the row below, find the maximum total from top to bottom of the given triangles.
Storing the triangle - We will accept the triangle text input, and will convert it into a list of rows, where a row is the list of elements.
Algorithm - For each row, we will calculate an array res_array
from top to bottom. This array will consist of the sums of the numbers of the best path from the top to the respective elements in that row.
First, paste the triangle in the input box to run the code.
# Coded By: Armaan Nougai #Brute Force # Project Euler 18 and 67 with open('__ed_input.txt','r') as FILE: Data = FILE.readlines() arr = [list(map(int,(j.split()))) for j in Data] result_arr = arr[0] for row in arr[1:]: new_result_arr = [] for x,value in enumerate(row): if x==0: # 1st element of row new_result_arr += [value+result_arr[0]] elif x==len(row)-1: # last element of row new_result_arr += [value + result_arr[-1]] else: # mid-elements of row new_result_arr += [value+max(result_arr[x],result_arr[x-1])] result_arr = new_result_arr print(max(result_arr))
Enter the input below to be saved in file __ed_input.txt
We’ll store the triangle in a list of rows, where a row is a list of elements.
Algorithm -
Let the figure below be the triangle
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
We will start from the second to last row, and create a res_array
, as follows:
For 18: we have two options, 20 and 04, and we will choose the larger one, i.e. 20. So res_array[0]
= 18+20= 38
For 35: we’ll choose max(04,82) = 82. res_array[1]
= 35+82=117
For 87: we’ll choose max(82,47) = 82. res_array[2]
=87+82=169
For 10: we’ll choose max(47,65) = 65. res_array[3]
=10+65=75.
And now, we will replace the last two rows of the triangle with res_array
.
Then, we will again go through the second to last row and create res_array
.
res_array[0]
=17+117=134
res_array[1]
=47+169=216
res_array[2]
=82+169=251
Again, we will replace the last two rows of the triangle with res_array
.
res_array
has only one element in it.# Coded By: Armaan Nougai # Project Euler 18 and 67 with open('__ed_input.txt','r') as FILE: Data = FILE.readlines() arr = [list(map(int,(j.split()))) for j in Data] result_arr = [0]*(len(arr[-1])+1) for row in arr[::-1]: result_arr = list([value + max(result_arr[x],result_arr[x+1]) for x,value in enumerate(row)]) print(result_arr[0])
Enter the input below to be saved in file __ed_input.txt
RELATED TAGS
CONTRIBUTOR
View all Courses