stphung.blog

My solution of problem number 18 and 67 from projecteuler.net.  I highly recommend tackling some of the problems there, they are fun and challenging.

The Problem

The problem at hand is from projecteuler.net, problem number 18 or 67 which can be found at http://projecteuler.net/index.php?section=problems&id=18 and http://projecteuler.net/index.php?section=problems&id=67.  The difference between problem 18 and 67 is the input size.  The problem summarized is, starting at the top of a triangle structure of numbers where a number can move to adjacent numbers on the row below, find the maximum cost path to the base.  In the example given on projecteuler, this triangle made up using four rows of numbers the maximum sum is 3+7+4+9=23.

3

7 4

2 4 6

8 5 9 3

Brute Force Feasibility

The problem that is asked for us to solve is to find the maximum cost path down a triangle of 15 rows.  The feasibility of testing every case for 15 rows isn't bad.  By observation, the number of paths in a triangle with 1 row is 1, 2 rows is 2, 3 rows is 4, so for the general case we have for n rows 2^n-1 distinct paths.  For n=15 we only have 2^15-1=16,384 distinct path which is definitely possible to brute force but the number of distinct paths increases exponentially with n which would make for an algorithm with O(2ⁿ) runtime.  Problem 67 however is not possible to brute force since there are 100 rows which equates to 2^100-1 distinct paths.

Using Optimal Substructure

Looking at simpler problems where n is small such as n=1 or n=2 the problem feels like it should have some optimal substructure since the maximum path from one level can probably be used somehow to compute the maximum path to the next level.

If n=1 the maximum cost path is the cost of that single number since there is only one choice, in this case, a.

a

If n=2 there are two distinct paths down the triangle which are, choose the single number in row 1, then either choose the first number or the second number in row 2.  In this particular triangle the paths would be ab or ac.  The values a+b and a+c here would represent the maximum cost path down triangle such that you end up at b or c respectively.  The answer to the question in this case is max(a+b, a+c).

a

b c

If n=3 there are now four distinct paths down the triangle.

a

b c

d e f

Optimal substructure becomes most apparent for this value of n in my opinion.  If we had precomputed values to the n=2 case which were the maximum cost path to get to b and c then we could easily compute the maximum cost path to get to d, e, and f.  The maximum cost path to get to a node k will be denoted m_k.  Using this structure produced by solving n=2 it is intuitive how to solve n=3.

m_a

m_b m_c

d e f

Looking at d, there is only one option,b , which makes sense since there are no paths that can get to d that also contain c which means m_d = (m_b+d).  

Looking at e, there are complications here since it is an interior node that can be traversed to by b or c.  The maximum cost path to reach e would be computed as m_e = max(m_b+e, m_c+e).  

Looking at f, this is a case which is similar to computing md since f is not an interior node which can be traversed to by two nodes, m_f=(m_c+f).

After these solving n=3 we have the following structure.

m_a

m_b m_c

m_d m_e m_f

The solution to the problem for n=3 is max(m_d, m_e, m_f) since the maximum cost path to get to the bottom of the triangle is going to be the maximum cost path to get to one of the nodes at the bottom of the triangle.  

Generalizing

Computing the maximum cost paths for row n+1 given the maximum cost paths from row n is easy.  The intuition here is that after computing the maximum cost paths for row n there are only a few choices for maximum cost paths for row n+1.  As a generalization, the solution for a triangle of n rows is to compute the the maximum cost paths for for row k using the maximum cost paths from row k-1 starting at row 2 until k=n then taking the reduction using the max operator on the maximum cost paths in row n.  Building the triangle top down we now have an algorithm which runs in O(n²/2) which is definitely faster than O(2ⁿ) for large values of n.

The approach taken here can basically be classified as modified Dijkstra which relaxes edges if the weights are higher rather than lower, the graph structure is emulated using a grid structure in my implementation.