Project Euler 18: Maximum Path Sum I

Maximum Path Sum I

Warning: Please only read this post, when you are absolutely sure, that you don’t want to take part in the challenge that is Project Euler. My posts will spoil the solution for you. I’m posting my solutions to show one possible way on how to solve the problems in case you want to compare your solutions with mine or are stuck and gave up on solving the problem.

So this Project Euler Problem asks you to find the largest sum that can be produced by adding up numbers through a chain with the adjacent numbers following in the row below in a triangle. The triangle we are supposed to solve for this problem looks like this:

There is a hint in the problem description mentioning, that this number triangle (with edge lengths of 15) only has 16384 possible routes from top to bottom. This number is small enough to be quickly solved by simply calculating and comparing each paths sum, but later on in Project Euler Problem 67 we get a triangle with side lengths of a hundred, giving it 2⁹⁹ possible paths, with is far too large to be calculated in a timely fashion anytime soon. So we are already going to try to solve Problem 18 in a smart way, to make our lives easier, when we arrive at Problem 67.

The Algorithm

There is a easy way to find the maximum path. We know, that the maximum path has to go through the very top value 75, since every possible path starts there. It would also mean that the maximum path subtracting the 75 would be the maximum path up to the second row, since the maximum path can only go through these two possible numbers in the second row to reach the 75. The true maximum path in the second row would therefore be the maximum between the maximum path that leads to 95 (the first value in the second row) and the maximum path that leads to 64 (the second value in the second row). These assumptions can be continued on until you reach the last row of the triangle. Our algorithm is going to take advantage of this knowledge.

Our algorithm would start in the second to last row of the triangle and replace each number with its maximum sum of itself and the bottom left value of the last row and of itself and the bottom right value of the last row (the sketch at the top of this post may help understanding this step). The calculated values now represent the maximum paths that lead to this value when starting from the last row.

We are going to repeat this step until we reach the top of our triangle and as the sketch shows, you’ll have the maximum of the complete triangle replace the top value. And by following the path of the maximum adjacent numbers from the top to the bottom of the triangle you also can backtrack the path that yields the maximum path.

Code

The code is similar to the previous problems that involved info from the Project Euler website. So I first parse the html page to save the number triangle as a list of lists. I then have a for loop starting at depth-2, the index of the second last line of the number triangle, and the third parameter -1 in range signifies to decrease i by minus one after each loop.

The built-in max function returns the highest value in the list given as parameter. We use this to compare the bottom-left and bottom-right value for their size. The bigger sum is then added to the above value. The result of this problem is then saved in the top number triangle value.

"""Find maximum total from top to 
   bottom in the given triangle"""

import urllib.request

req = urllib.request.Request("https://projecteuler.net/problem=18")
response = urllib.request.urlopen(req)
the_page = response.read()
the_page_string = the_page.decode("utf-8")
counter = the_page_string.find("75<br />")

triangle = []
row = []

while(counter < len(the_page_string)):
	# add number to list
	row.append(int(the_page_string[counter:counter+2]))
	counter += 2

	if(the_page_string[counter] == " "):
		counter += 1
	elif(the_page_string[counter:counter+6] == "<br />"):
		counter += 8 # +2 for n
		triangle.append(row)
		row = []
	elif(the_page_string[counter:counter+4] == "</p>"):
		triangle.append(row)
		break



"""Start at second last row and replace by max of the two sums by either
adding to the bottom left or the bottom right."""

depth = len(triangle)
for i in range(depth-2,-1,-1):
	for j in range(0,len(triangle[i])):
		triangle[i][j] += max([triangle[i+1][j], triangle[i+1][j+1]])

print("Result: " + str(triangle[0][0]))

The computation needs about 0.452 seconds of processing time on my laptop, which is sufficient and should probably scale well enough for Problem 67 sometime later.

Problem 18 involved some work to come up with a clever algorithm to solve this problem. It was hard to do specific research on the topic, since its hard to classify this problem to a certain mathematical field. Writing the code didn’t offer too many troubles.

Hope it was a fun read, don’t be hesitant to send me suggestions on improving the algorithms via email at ratherreadblog@gmail.com or by leaving a comment at the post. You can also subscribe to my mailing list here if you always want to stay up-to-date with my newest posts and changes on the website.

 

The post Project Euler 18: Maximum Path Sum I appeared first on Rather Read.