# Paths down a triangle, continued

Published on 2011-07-26Like problem 18, problem 67 of Project Euler asks you to find the greatest sum that can be achieved by adding together the numbers encountered by walking down a triangle composed thereof. The original writer states the problem more clearly. Problems 18 and 67 both start with the following text:

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

Problem 18 then continues by asking you to find the maximum total from top to bottom of a 15-row triangle, and problem 67 links to a text file, triangle.txt, and asks you to find the maximum total of a journey down the 100-row triangle contained therein. Now, the 15-row triangle problem can be solved by simply calculating the total obtained from each journey. There are, after all, "only" 16,384 possible routes that can be taken: each step down the triangle presents two possible, each of which presents two choices, each of which presents two choices, etcetera on down to the bottom of the triangle. The number of routes is therefore 2^{x}, where `x`

equals the number of choices that must be made, i.e., one less than the number of rows in the triangle. 2^{14} is a reasonable number of possible routes to evaluate, but 2^{99} is not. As the problem author points out, a brute force solution would take over 20 billion years to process. And that's on a fast computer.

The trick to solving this problem quickly is to literally approach the problem from the bottom up. Each number on the bottom row of the triangle is the potential end for an insanely large number of routes, but it was ultimately arrived at through a single, binary choice: option A or option B. This choice was made from a number on the second row from the bottom, meaning that that number on the second row has a maximum possible total of its value plus the value of either option A or option B, whichever is greater. If we take the triangle given as an example in the problem text, we can see that the most valuable place to land is on the six, because its maximum ultimate value is 6 + 9, whereas the maximum ultimate value of the other two numbers on that row are 10 (2 + 8) and 13 (4 + 9). Starting at the bottom, this:

7 4

2 4 6

8 5 9 3

becomes this:

7 4

10 13 15

which, in turn, becomes this:

20 19

using System; using System.IO; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem067 { class Program { static void Main(string[] args) { List<int[]> triangle = new List<int[]>(); string fileName = @"C:\Users\jonny\Desktop\triangle.txt"; StreamReader textReader = new StreamReader(fileName); do { string[] triangleRawInput = textReader.ReadLine().Split(); int[] triangleInput = new int[triangleRawInput.Length]; for (int i = 0; i < triangleInput.Length; i++) triangleInput[i] = Int32.Parse(triangleRawInput[i]); triangle.Add(triangleInput); } while (textReader.Peek() != -1); for (int i = triangle.Count() - 2; i >= 0; i--) { for (int j = 0; j < triangle[i].Length; j++) { triangle[i][j] += Math.Max(triangle[i + 1][j], triangle[i + 1][j + 1]); } } Console.WriteLine("The maximum total is {0}", triangle[0][0]); } } }