Project Euler # 18

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

74

246

8 593That 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)

## Brute Force

The obvious solution is to brute force the solution by trying every possible route, through recursion. However, since at each junction the path branches into two, there will be 2^{14} = 16384 routes. With a 100 rows, there will be 2^{99} rows, which is way too much to brute force!

## Non – Obvious method

Logic:

Let us understand this with the help of this small triangle:

**3**

**7** 4

2 **4** 6

8 5 **9** 3

Each element can lead to the element directly below, or the element directly below and to the right.

Assuming a given element is a point on the solution path, the next element has to be the greatest of the two possible elements. Thus add the greatest number below a given number to it and iterate upwards. This is demonstrated on the small triangle.

Original:

**3**

**7** 4

2 **4** 6

8 5 **9** 3

Add bottom row elements to the top.

8 > 5

9 > 5

9 > 3

**3**

**7** 4

10 **13** 15

8 5 **9** 3

Add the new row to the row above it.

10 < 13

13 < 15

**3**

**20** 19

10 **13** 15

8 5 **9** 3

And again, add the new row, this time to the topmost row.

20 > 19

**23**

**20** 19

10 **13** 15

8 5 **9** 3

The topmost element is the largest sum!

Data file containing triangle (Program reads from this file)

Note: You can use this to solve problem 67 as well. Remember to change array sizes, iteration limits and the data file!