Dynamic Programming With Projecteuler

I have been working on ProjectEuler problems on and off over the past few years. For those of you who don’t know, ProjectEuler is a great resource for learning a new programming language or sharpening your math/computer science skills (check them out here if you are interested). This site contains a whole bunch of math and computational questions that are ideally solved using small computer programs. It is constantly being updated with new questions of varying difficulty to keep things interesting.

ProjectEuler is really helpful in understanding how to think creatively with your problem solving. Most problems can be solved many different ways and can drastically change the amount of time that it takes to arrive at a solution. All of these problems abide by ProjectEuler’s one minute rule. If your solution program is taking longer that a few minutes you may want to rethink your algorithm. An inefficient solution could take longer than your lifetime to finish computing. Most of us have better things to do than wait for slow programs to finish.

One problem in particular that took me a maddeningly long amount if time to finish was problem 67 (if you solve this one you also get problem 18 for free, same problem, smaller triangle). If you want to take a stab at this question please do so before reading onwards as I’ll go over my solution below.

Spoilers ahead!

This problem turned out to be a great example of a dynamic programming problem which I had no clue about before attempting to solve it. Dynamic programming is a way of solving a problem by breaking it down into smaller sub problems. You then solve those, feeding the sub problem solutions back into the problem until you arrive at the final solution. This method essentially morphs your problem into the answer that you are searching for.

Problem 67 is stated as follows (sorry for the small screen shot, click on it to enlarge. Here is a link to the problem):

As you can see we will have to find a non-brute force way to solve the problem. There are many other posts out there on how to solve this problem by starting at the bottom of the triangle and working your way to the top. I must admit, this is a real elegant way to solve it and would have saved me a few early headaches, it probably even makes a little more intuitive sense to solve the problem that way. You can check out some of those posts here and here if you are interested. I decided to solve the problem going from the top of the triangle downwards. After solving it I didn’t see very many posts on using this approach so I decided to write one myself.

Here is the basic gist of the algorithm that I used to solve this problem.

First read the triangle into an array. Then, starting at the top of the triangle, you must sum your way down until you are left with the last row of the triangle which will contain the answer we are after. The key to this problem is how you sum as you move down the triangle.

If we break this problem down into a very small triangle we can see the answer is quite simple:

We can easily determine the maximum total because there are only two choices. Here you would just add 4 to 8 and 4 to 12 checking to see which sum is greater than the other. We can extrapolate this idea to any size triangle. Since I am using an array to solve this we must consider a few logical conditions as we travel through the triangular array.

We will first start at the second row of the triangle and loop through each element in the array going left to right and checking the following conditions.

If we are at the first element in the current row, we will add that to the first element of the previous row and set that sum as the new value for the current position we are at.

Similarly, if we are at the last element in the current row, we will add the last element from the previous row and set that sum as the new value for the current position we are at.

Now for the trickiest part, when we are in the middle of the triangle we will have to choose between summing two integers in the previous row. Here we will just sum both, and choose the largest sum to replace the current element.

Once we get to the final row of the triangle we can just choose the largest number from that last array. I like to think this top down approach is a little more flexible of a solution because we could just as easily get the third biggest sum possible by choosing the third biggest number form that array. That wouldn’t be possible if you decided to start from the bottom of the triangle and work your way to the top.

Here is how I implemented the code in python:

triangle = []

for num in triFile:
    triangle.append([ int(x) for x in num.strip().split() ])

for i in range(1,len(triangle)):
    for j in range(len(triangle[i])):
        if j == 0:
            triangle[i][j] = triangle[i][j] + triangle[i-1][j]
        elif j == len(triangle[i-1]):
            triangle[i][j] = triangle[i][j] + triangle[i-1][j-1]
        else:
            triangle[i][j] = max(triangle[i][j] + triangle[i-1][j],triangle[i][j] + triangle[i-1][j-1])

print max(triangle[len(triangle)-1])

These types of problems are great, they have many ways that they can be solved, and are quite gratifying once you come up with a satisfying solution. If any of you have any questions or suggestions for improvement don’t hesitate to leave a comment below.