Project Euler 18: Maximum Sum from Top to Bottom of the Triangle

The problem presented by Project Euler in Problem 18 is an optimization problem where you need to find the route through a triangle which maximizes the sum.  The problem reads

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2
4 6
8 5
9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

I will present you with two different solutions for this Project Euler problem. First a brute force solution, which the note state is possible for this problem, but not for Problem 67.  And latter I will present a Dynamic programming solution which can be reused for Problem 67. However, before addressing the algorithm part of the answer I will address the data representation, and how to read the data input.

At each level in the pyramid we always have two choices; we can go either left or right. Choosing left all he time will make us end up in the lower left corner, while choosing right will end us up in the lower right corner.

Data Representation

I have chosen to store the input data in a 2-dimensional array (int[ , ] in C# syntax) for this problem, instead of an array of arrays (int[ ][ ] in C# syntax). I know that I could have saved almost half of the memory by doing it the other way, but I felt it was easier.

I have stored the problem in memory such in the following way

3 0 0 0
7 4 0 0
2 4 6 0
8 5 9 3

such that going right increases the index by one, and going left keeps the index, and the triangle is padded with zeros.

I wrote a small input function so I could read the problem data from a text file and store it in a 2-dimensional array. I will use the input reader for both solutions. The C# implementation of the input function looks like

```private int[,] readInput(string filename) {
string line;
string[] linePieces;
int lines = 0;

while ((line = r.ReadLine()) != null) {
lines++;
}

int[,]  inputTriangle = new int[lines, lines];
r.BaseStream.Seek(0, SeekOrigin.Begin);

int j = 0;
while ((line = r.ReadLine()) != null) {
linePieces = line.Split(' ');
for (int i = 0; i < linePieces.Length; i++) {
inputTriangle[j, i] = int.Parse(linePieces[i]);
}
j++;
}
r.Close();
return inputTriangle;
}
```

All it does is find the number of lines in the file, allocate an array that fits, and read in the data.

Brute Force

When answering the problem with a brute force solution, it is pretty simple to go through the steps, we just need to try all combinations. Since we have a binary choice each time. We can iterate through all possibilities with a normal integer counter, and use the bits of the number to pick the direction left or right. While running through the path, we sum up the numbers and check if they are larger than the current maximum found.

I chose an implementation where I bitshift to find the left/right direction. It can be implemented in C# as

```string filename = Environment.GetFolderPath(Environment.SpecialFolder.DesktopDirectory) + "\\input.txt";

int posSolutions = (int)Math.Pow(2, inputTriangle.GetLength(0) - 1);
int largestSum = 0;
int tempSum, index;

for (int i = 0; i <= posSolutions; i++) {
tempSum = inputTriangle[0, 0];
index = 0;
for (int j = 0; j < inputTriangle.GetLength(0) - 1; j++) {         index = index + (i >> j & 1);
tempSum += inputTriangle[j + 1, index];
}
if (tempSum > largestSum) {
largestSum = tempSum;
}
}
```

It is a simple and easy approach, which works fine for this problem. The output of the code is

```The largest sum through the triangle is: 1074
Solution took 15 ms
```

Dynamic Programming

The given problem is a classical example of dynamic programming, and it really works well for it. The methodology is a bit more complex than the brute force solution, but I will take a shot at explaining it anyway.
I will use the four line example to explain the idea throughout this section.

Standing at the top of the triangle we have to choose between going left and right. In order to make the optimal choice (which maximizes the sum), we would have to know how large a sum we can get if we go either way. So in order to answer the question we would basically have to solve the two smaller problems which I have marked with blue and the orange in the figure to the right.

We can break each of the sub-problems down in a similar way, and we can continue to do so until we reach a sub-problem at the bottom line consisting of only one number, then the question becomes trivial to answer, since the answer is the number it self. Once that question is answered we can move up one line, and answer the questions posed there with a solution which is a + max(b,c).

Once we know the answer to all 3 sub-problems on the next to last line, we can move up and answer the posed sub-problems by the same formula already applied. And we can continue to do so until we reach the original question of whether to go left or right.

Optimal Sub-structure

If we break down the problem into sub-problems we can see that breaking the orange sub-problem into two and breaking the blue sub-problem into two would yield us 4 sub-problems. However the sub-problem in the overlapping part is identical.  In this problem solving the sub-problem yields the same result no matter how we reached the it. This is fairly easy to see in this example. When a problem has this property it is said to have optimal sub-structure. Since we have a problem with optimal we only have to solve three sub-problem in the next to bottom line, and therefore the dynamic programming is effective.

It can be proven that the problem has an optimal sub-structure. However, I wont go into the details of that here, but leave that as an open end you can pick up and explore.

Savings with Dynamic Programming

If we want to solve the small problem with brute force, we would need to test all 8 paths, each resulting in 3 additions, in total 24 additions.

If we use dynamic programming, the first iteration would require 3 maximum comparison operations and 3 additions. The next line would require 2 maximum comparison operations and 2 additions, and the first line would require one of each. So a total of 6 maximum comparison operations and 6 additions.

For small problems this saving is small if any at all, but for a problem with 15 lines, solving the first iteration would and brute forcing from there would reduce the number of brute force additions from 15*214 to 14*213 a saving of approximately 131000 fewer additions, at the cost of 15 additions and 15 maximum comparison operations. That is a pretty good saving.

Dynamic Programming – The Algorithm

We can make a short-cut with the algorithm, as we don’t have to break the problem into sub-problems, but can start from the bottom and work the way up through the triangle until we reach the top and the algorithm spits out a number.

3
7 4
2 4 6
8 5 9 3

Applying the algorithm to the small problem we will need three iterations. The first iteration we apply the rule a + max(b,c) which creates a new triangle which looks as

3
7 4
10 13 15

Making the second iteration of the algorithm makes the triangle look

3
20 19

And if we run the algorithm once more, the triangle collapses to one number – 23 – which is the answer to the question.

My implementation of the algorithm in C# looks like

```string filename = Environment.GetFolderPath(Environment.SpecialFolder.DesktopDirectory) + "\\input.txt";
int lines = inputTriangle.GetLength(0);

for (int i = lines - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
inputTriangle[i, j] += Math.Max(inputTriangle[i+1,j], inputTriangle[i+1, j+1]);
}
}
```

The output of the algorithm is

```The largest sum through the triangle is: 1074
Solution took 3 ms
```

Closing Remarks

For Problem 18 as we have solved here, the difference is very small. However, once we apply the algorithms one Problem 67, the different approaches will be a matter of getting the answer or not.

I have seen another solution using Dynamic Programming over at Functional fun, where he goes the other way through the triangle. I think mine is easier to understand, and ends up with one solution rather than a series of numbers you need to find the maximum of, but I will let you decide.

As usual I have uploaded the source code for you to play around with. Any comments, suggestions or improvements are very welcome; both for the code and for the explanation. I love to get feedback on how to improve my communication and problem solving skills.

Posted by Kristian

[…] answer. After solving the solution in an awful, brute force way, I found a more elegant dynamic solution that worked for large data sets (It appears this is the solution for Problem 18 from Project Euler, […]

hukka

Awesome, thanks so much for the solution. I stumbled on this site and it is really a great blog.

Kristian

You are welcome.

chasemydreaming

Thank you so much for the different methods. Any ideas of the time complexity about two solutions?

Kristian

Hi, and thanks.

The brute force solution is exponential in time, it will have to test 2^n solutions, where n is the number of rows.

The other one I am a bit, it needs to perform one operation for each element in the line, and each new line grows. However, it is linear in time with respect to the number of lines I guess.

Trace

This problems was giving me a lot of trouble. Your explanation is the first that has made sense to me. Thanks.

Kristian

Thanks 🙂

jyoti

Your explanation is just awesome 🙂

Sahand

there is a better way man, just start from the top and add the numbers together.
what i mean is that for any number at a give position you have calculated the sum up to its above line so u have two choice to choose from so you choose the larger one. and by the last line you have calculated the largest possible for every item in the last row and then you simply choose the largest one in the last row and thats your solution.

Kristian

Hi

What you suggest there is basically the same thing as the dynamic programming algorithm I have suggested in my post. It is going the other way through, but you will have the same amount of calculations.

[…] 算法参考这篇文章: Project Euler 18: Maximum Sum from Top to Bottom of the Triangle […]

Sathish Kumar

Thank you very much,
it was very useful, the way you have explained was awesome.

Jean-Marie Hachey

Hi Kristian,

The maximum total from top to bottom of the triangle shown in the article is 1064.
(75+95+47+87+82+75+73+28+83+47+43+73+91+67+98 = 1064)

However, the algo (2) gives a sum of 1074; (t = 3 ms).

Another source (3) also gives 1074; (t = 1,7353 ms)

___

Sources:

1) Project Euler.net
Maximum path sum I
Problem 18
http://projecteuler.net/problem=18

2) Kristian’s algo
http://www.mathblog.dk/files/euler/Problem18.cs

3) Coding experiments
http://coding-experiments.blogspot.ca/2008/04/project-euler-problem-18.html

Jean-Marie Hachey

Hi Kristian,

Re : Maximum Sum from Top to Bottom of the Triangle

Relative to my previous comment:

I was referring to the plausible path:
(75+95+47+87+82+75+73+28+83+47+43+73+91+67+98 = 1064)

If we consider the optimal path (1), we get the solution obtained via the 2 algos (2, 3):
(75+64+82+87+82+75+73+28+83+32+91+78+58+73+93 = 1074)

___

Sources:

1) Project Euler: Problem 18
longje
http://www.solvebysearch.com/blog/post/2012/02/24/Project-Euler-Problem-18.aspx

2) Kristian’s algo
http://www.mathblog.dk/files/euler/Problem18.cs

3) Coding experiments
Agnius Vasiliauskas
http://coding-experiments.blogspot.ca/2008/04/project-euler-problem-18.html

Idan

I didn’t understand this line: “index = index + (i >> j & 1);”
Could you explain that for me?

isidoro

Hi Kristian,

I don’t know why but I get 2 errors, one is invalid input and the other if format exception. Could you help me?

isidoro

Peter

Hi Kristian,
thank you very much for solution describtion.
I’m very interested in the way you make decision in alg. #1 whether left(down) or right to move next: i >> j & 1. How to prove formally this will sum up into 2^(n-1) different paths. And could you plz propose alternative ways to implement this.
Peter.

Kristian

I simply use the numbers in binary form, and if I encounter a 0 I go left and if I encounter a 1 I go right.

So if you have a pyramid that is 3 levels deep, you need to make two decisions. This can be represented with 2 bits, or all the numbers 0 to 3.

00 – left, left
01 – left, right
10 – right, left
11 – right, right

You can draw it yourself to verify.
So if I just loop through all the numbers in this case 2^14 = 16384 we will go through all the cases.

Tommy

Thanks a lot for this. It seems so obvious now, that I regret having read the solution. I think your explanation (starting from the bottom) is the optimal one. Cool blog! I have lots of respect for smart mathematicians like yourself!

Mayur Arora

If you just explain the index = index + (i >> j & 1); part. I could not use the same in Javascript. I did go through your previous remarks regarding this. Is there any other way to get hold of every possibility. Something other than the shift operators.

Kristian

I am pretty sure that you can use bit shift operators in javascript. Otherwise you should be able to convert the number to a binary string format and then parse that.

http://stackoverflow.com/questions/9939760/how-do-i-convert-an-integer-to-binary-in-javascript

Fatih

Hi, I solved the problem by using a solution mixed with some graph theory and its time complexity is n^2. every node is tested once. I guess that is better than your both solutions.

shalitha

my python code
l = []
for i in range(0,15):
l.append(input().split())
print(l)
def triformer(lu,lb):
lbn=[]
for i in range(0,len(lu)):
if int(lu[i])+int(lb[i+1])>int(lu[i])+int(lb[i]):
lbn.append(int(lu[i])+int(lb[i+1]))
else:
lbn.append(int(lu[i])+int(lb[i]))
l.pop()
l.pop()
l.append(lbn)

for i in range(13,-1,-1):
triformer(l[i],l[i+1])

print(l)
# for input, you have to copy-paste the triangle

Anant Sajnani

Top Down Approach

public static int maxSumPath(int[][] i, int r, int pc, int ps,int[][] m) {

int result = 0;

if (r > i.length – 1) {
return ps;
} else {

int startIndex = 0;
int endIndex = 0;

if (r != 0) {
startIndex = pc;
endIndex = pc + 1;
}

for (int j = startIndex; j <= endIndex && endIndex 0; j++) {
if (m[r][j]!=0) {
return m[r+1][j];

}
int sum = 0;
sum = maxSumPath(i, r + 1, j, ps + i[r][j],m);
sum = Math.max(sum, result);
m[r+1][j]=sum;
result = sum;

}
}

return result;
}

felix

I cannot understand that bit shift algorithm in this post, but was itching to compare brute force to dynamic programming. Below is my take on the brute force method using recursion programmed in C#. the triangle is stored in an array of arrays of different lengths

private void bfSolve(ref long sol, long[][] tri)
{
long bfSum = 0;
bfAdd(0, 0, 0, ref sol, tri);
}

``` //i is row, j is col index private void bfAdd(int i, int j, long sum,ref long maxsum, long[][]tri ) { //add self to sum sum += tri[i][j];```

``` //check if the last row is reached, return the larger number o maxsum if (i == tri.Length-1) { maxsum = sum > maxsum ? sum : maxsum; return; } ```

``` //bottom row not reached, recursively call this method to go down to the next row //add left bfAdd(i + 1, j, sum, ref maxsum, tri); //add right bfAdd(i + 1, j + 1, sum, ref maxsum, tri); } ```

Can any one help please ? While calculating the max number i am unable to get the last row result, i also need to check that if the last number is even next added should be odd
1
8 9
1 5 9
4 5 2 3
Output:
Max sum: 16
Path: 1, 8, 5, 2

below algorithm is used:

public static int CalculateSum()
{
int MaxSum = 0;
int temp, index;
bool IsEven = false;
int TotalLength = (int)Math.Pow(2, EvenOddTriangle.GetLength(0) -1);
IsEven = IsEvenNumber(EvenOddTriangle[0, 0]);
for (int i = 0; i <= TotalLength; i++)
{

``` temp = EvenOddTriangle[0, 0]; index = 0; for (int j = 0; j < EvenOddTriangle.GetLength(0)-1 ; j++) { index = index + (i >> j & 1); if (IsEven) { if (!IsEvenNumber(EvenOddTriangle[j + 1, index])) { temp += EvenOddTriangle[j + 1, index]; IsEven = IsEvenNumber(EvenOddTriangle[j + 1, index]); }```

``` } else { if (IsEvenNumber(EvenOddTriangle[j + 1, index])) { temp += EvenOddTriangle[j + 1, index]; IsEven = IsEvenNumber(EvenOddTriangle[j + 1, index]); } ```

``` } } if (MaxSum < temp) { MaxSum = temp; } } return MaxSum; } ```

Željko Perić

I have found path from top to bottom trough the triangle with largest sum 1116 .
Correct answer according to the above solutions is 1074 ?!
Perhaps the problem is in the definition of adjacent numbers.

75 75 75
95 64 64 64
17 47 82 82 82
18 35 87 10 87 87
20 04 82 47 65 82 82
19 01 23 75 03 34 75 75
88 02 77 73 07 63 67 77 73
99 65 04 28 06 16 70 92 65 28
41 41 26 56 83 40 80 70 33 41 83
41 48 72 33 47 32 37 16 94 29 72 32
53 71 44 65 25 43 91 52 97 51 14 71 91
70 11 33 28 77 73 17 78 39 68 17 57 70 78
91 71 52 38 17 14 91 43 58 50 27 29 48 91 58
63 66 04 68 89 53 67 30 73 16 69 87 40 31 66 73
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23 98 93
1116 1074

All the best,
Željko Perić

@Zeljko The first row should contain one number only.

Ardit

How can I print the values of the path, so the numbers which were added up to form the final sum.

For example if the input is this triangle:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

I want the output to be:
30
7 3 8 7 5

Robert Pilgrim

Could you start at the bottom and for each value in the next to the last row add the larger of the two value below it? Then repeat with the next row up from the bottom until you reached the top. Of course to you would have to save the path as you moved up so you could recreate it from top to bottom…

Aviv Murlakov

@Kristian
I think you have a redundant run in the brute force you run 2^n + 1 since i starts from 0 to 2^n (inclusive).
The stop condition for the loop should be i < posSolutions and not i <= posSolutions

Aviv Murlakov

For those who have difficulty understanding the BF magic line – ‘index = index + (i >> j & 1)’

First note that (i >> j & 1) can get either 0 or 1, so ‘index’ is either the same as before or it’s one bigger than the previous one.
Moreover note that if we look on two consecutive rows and say we are at some index i on the top row.
Then the same index i on the bottom corresponds to a “left” choice, while the index i + 1 on the bottom (which is guaranteed to exist due to the input form) corresponds to a “right” choice.

Note that ‘i’ is running through all the states (2^n) where n is the number of rows. (For example for 5 rows: i = 00000, 00001, 00010… etc till 11111 )
We read the states from the least significant bit to the most significant bit (right to left). A 0 means we keep the previous index, which we showed before corresponds to “left” direction. A 1 corresponds to a “right” direction (shown before).

So if we have 5 rows and i is currently 24 which is 01100 in binary, this corresponds to the option (reading ‘01100’ from right to left): Left, Left, Right, Right, Left. And in Indices it will be
(0+0) 0, (0+0) 0, (0+1) 1,(1+1) 2, (2+0) 2
which you can verify exactly matches this path of ‘Left, Left, Right, Right, Left’ if we represent the data as a 2-dimensional array.

Hope this helped clarify things.