Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

project euler
maximum path sum i
communitycreator

How to solve Project Euler #18 - maximum path sum problem

Armaan Nougai

Maximum path sum

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.

18th Problem triangle
67th Problem triangle
widget

Brute force approach

  • 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.

widget
  • Note: The code below is for problems 18 and 67.

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

Better approach

  • 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
      
    1. 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.

    1. 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.

    1. We will repeat the steps above until the res_array has only one element in it.
widget
widget
widget
# 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

project euler
maximum path sum i
communitycreator
RELATED COURSES

View all Courses

Keep Exploring