Project Euler Problem 67

Introduction

Imagine this: you’re the Chief Commercial Officer at Hostile Takeover Bank (HTB). You want to grow the bank, and you’ve done some preliminary research that shows the level of interest per distinct geographic region. That information looks like this:

Now, Chick Hicks, the CEO of HTB has asked if you can go on a roadshow to promote the bank: you’ll start at HTB HQ and move progressively down the triangle, row by row, from geographic region to geographic region. In an ideal world, you would go to all 10 towns (numbers) represented in the triangle and give your roadshow. However, real-world constraints still apply, even at HTB: you can only visit one town in each row, and from there you may only travel to one of the two adjacent towns in the row below. 

Problem Statement

Now, the question on everyone’s mind: our market research has produced the triangle above –  what path should you take and which towns (numbers) in each row (geographic region) should you visit and do the roadshow in order to maximise the total number of people interested in your bank? This is actually a restatement of Project Euler Problem 67 --- but Chick Hicks wants an answer before the quarterly earnings call, and he doesn't care about algorithm theory-- he just wants the biggest possible market share. So let's get to it! 

Small Triangle: Brute-force approach

With a small triangle like the one above, we could actually brute-force it and try every single route until we get to the one with the maximum number of people interested. There are four rows, meaning three decisions (left or right at each step), giving 2³ = 8 possible paths. That would look like this (press the "play" button at the bottom of the animation to start -- it does not autoplay). 

So, our ideal route is indicated in green in the above which exposes us to the maximum number of people per row (which turns out to be 23). The brute-force approach was relatively straightforward for a triangle of only 4 rows/geographic regions -- but, HTB is an ambitious bank, and we plan to go to 100 geographic regions in our roadshow. In that set up, we have 99 rows with 2 decisions each, totalling 2⁹⁹ paths (6.39 e+29 = 63 octillion paths!) That's far too many paths individually explore, and would take over a billion years to search even if we had a supercomputer (according to the problem statement). We thus need some efficient method to compute the maximum number of people per geographic region.

Small Triangle: More Sophisticated Approach

Instead of searching for algorithms to fit the problem, I think it could be quite useful to sit with the problem for a bit, and consider what needs to be done. The solution ultimately ends up being quite intuitive and requires no advanced mathematical knowledge, and is probably the first thing anyone who tries to solve the problem would do (conceptually) so let’s see if we can derive it from first principles. 

Our method of attack could be to “trial” a method with the small triangle first introduced in Fig. 1, confirm it works by comparing to our brute-force solution, and then applying it to the big 100-row triangle and seeing if this is right (Project Euler has the solutions). So, let’s consider Fig. 1 again: our brute force approach showed that we only have 8 routes to follow, which were

1. 3 → 7 → 2 → 8 = 20

2. 3 → 7 → 2 → 5 = 17

3. 3 → 7 → 4 → 5 = 19

4. 3 → 7 → 4 → 9 = 23 <-- winning path

5. 3 → 4 → 4 → 5 = 16

6. 3 → 4 → 4 → 9 = 20

7. 3 → 4 → 6 → 9 = 22

8. 3 → 4 → 6 → 3 = 16

Notice that for the top 4 paths (in blue) the first 2 numbers are identical (3 → 7); and equally so for the bottom 4 paths in pink (3 → 4)? These represent the “left” branch of the triangle’s solutions, and the “right” branch, respectively. In our brute-force approach, we kept on computing these numbers for each path, but this seems wasteful; why not compute it once and store it, and then retrieve it again when we need it? Visually, that solution would look like this:

Great -- we've arrived at the same final answer, but this time, with much fewer operations. The brute-force approach has 2³ = 8 paths (a path here can be considered a transition from row r to row r+1), and each path consists of 3 addition operations (one for each row after the root node), thus 8 x 3 = 24 operations. The method visualised above in Animation 2 still has 8 paths (count them!), but each path now only has 2 addition operations, totalling 16 operations. Adding to this the initial 2 sums from the root node (row 1) to the second row (3 + 7 and 3 + 4), we count only 18 operations. This small saving isn't interesting by itself, but what is interesting is the pattern. Once we realise that partial solutions (path sums) can be reused, we can keep on applying the same trick to the rest of the triangle. 

Why stop at row 2, though?

We could in concept carry this procedure down all rows of the triangle: for every node we ask a small question: "what is the largest total that could have reached me". For nodes in the middle of the triangle there are two possible parents, so we compare those two cumulative totals and keep only the larger one. This all sounds quite complex, but is quite simple in principle, as the animation below shows: 

And again, using this method, we arrive at the correct answer. Rather than searching every possible route through the triangle, we've reduced the problem to a sequence of two-row computations. At each step, we consider one child node and ask a single question: which of its possible parent nodes gives the largest cumulative total? We record that maximum at the child node and move on. Once every row has been processed in this way, the largest value in the final row represents the maximum possible path sum.

Big Triangle: Full Solution

So, let's try this method on the 100-row triangle. The maximal path we can draw from that triangle is 7273 (you can verify here, but you may need an account). The visualisation of getting to that answer by using the method we describe above is shown below:

Notice what has happened. Every node in the triangle is processed exactly once. Instead of exploring 2⁹⁹ possible routes, we perform one calculation for each node and move on. It's difficult to understate just how significant of a shift this is: it has allowed us to solve the triangle in mere seconds, compared to the brute-force approach (examining all 2⁹⁹ possible routes) which would take a billion compute-years! 

Conclusion

Rather than focus on the actual answer to the 100-row triangle, or the code, what I think is quite cool is the shift in mindset that the solution demands. When faced with big problems like this, we often reactively reach for more power: bigger computers and faster chips, but our solution here shows that stopping to think about the problem for a bit can beat brute force approach. We've broken the big problem up into sub-problems: we’ve reduced the 100 row triangle to only 2 computations (rows) at a time, computed the maximum sum for each entry, and then recorded this value in the triangle index. This now represents the highest total of people interested in our bank, up until that row and index. In doing so, we've turned a billion-year brute-force problem to a few-seconds calculation on a simple laptop. Without being aware of it, we’ve stumbled upon a version of dynamic programming (DP). 

The surprising lesson isn't really about dynamic programming at all. It's about problem solving. Large, intimidating problems often become manageable once you stop trying to solve them directly and instead solve the smaller problems hidden inside them.

Following On

Next time we'll move from solving static optimisation problems to solving sequential decision problems, where today's choice changes tomorrow's options. That journey begins with reinforcement learning.

If you've found this useful or interesting, please consider subscribing, or share to interested colleagues. I publish long-form, in-depth articles on ML, AI, and Data Science (just like these) every two weeks or so, as well as practical business-oriented coding problems, like this one. If you'd like to get in touch, drop me a line.