## A Description of the Problem

We are given a triangle of numbers, and we are asked to write a program that computes the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base.

Some additional restrictions:

- Each step can go diagonally down to the left or the right.
- The number of rows in the triangle will be between 1 and 100, inclusive.
- The numbers that populate the triangle are integers between 0 and 99.

(Read the original description here.)

## What are our Inputs and Outputs?

Our initial input data will live in a file called `triangle-input.txt`

, which contains the following:

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

Note that the first line of the file is not part of the triangle itself; it’s there to tell us how many levels deep the triangle goes.

30

We’ll place our output in a file called `triangle-output.txt`

, which will contain a single integer. We’ll place the names of our input and output files in the program constants `INPUT_FILE`

and `OUTPUT_FILE`

, respectively.

## Reading the Input, Writing the Output

First, we’ll need to get the values out of `triangle-input.txt`

and store them in a convenient structure. In this case, an array of arrays should do.

We begin by creating an empty array, *tmp*, which will act as a temporary storage space for the lines of `triangle-input.txt`

.

We’ll read the lines of the file one at a time. For each line, we `split`

the string, e.g., “1 2 3 4 5\n”, into a list, and `push`

that line onto our array `tmp`

.

tmp = [] File.open(INPUT_FILE, "r") do |f| f.lines.each do |line| tmp.push line.split end end

Unfortunately, we’re pushing an array of strings onto *tmp*, since

```
"4 5 2 6 5\n".split
```

returns this:

["4", "5", "2", "6", "5"]

Therefore, we’ll take a second pass through and convert those arrays of strings into arrays of numbers. The resulting array will allow us to – finally! – begin our real work. Notice that this is a nested call to `map`

, best read from the inside out. The value returned by the inner `map`

is returned to the outer, with the results stored in variable *tri*, since the return value of `map`

is always an array.

tri = tmp.map { |array| array.map { |elem| elem.to_i } }

We’ll wrap everything here up in a method, `read_triangle_input`

, which will show up in the complete program listing below. We’ll also leave the `write_triangle_output`

method for the listing; it requires little explanation.

## Solving our Actual Problem

Now that the housekeeping chores are out of the way, we can jump in and begin the real work of finding the highest sum in our triangle.

We’d like to write a method, `triangle_sum`

, which, given an array of arrays like the one we’ve just constructed, returns an integer representing the highest sum calculated on its imagined path “down through the triangle.”

Since our route through the triangle is restricted to “steps” that can “go diagonally down to the left or the right,” the most natural representation of this data is as a tree. We’ll simulate this in a crude way using an array of arrays.

### The Inner Loop

Since our fundamental data structure is an array, we’ll need to choose a looping construct; we’ll stick with the “C-style” iterative constructs here since they map well onto this problem (no pun intended). We’ll use an `index`

variable to keep track of where we are in the iteration.

Inside the loop, we want to know three things (among others):

- Where am I?
- Where is the element to my upper left?
- Where is the element to my upper right?

We’ll denote the answers to these questions with the variables `this`

, `upleft`

, and `upright`

in our program listing below.

Remember the problem description: Starting at the root of the tree, we’ll keep a running sum of all the numbers we’ve seen thus far on this particular path through the tree.

#### Visualizing Our Movement Down the Triangle

In order to solve this problem, we started with some hand-simulation of what would eventually become the final algorithm. The example below shows how it works: given where we are in the array of arrays, we look “up and to the left” and “up and to the right” of where we are. In the following diagrams, we denote our position in the algorithm with a lovely text arrow.

Index: 1 [7] <--- [3, 8] [8, 1, 0] [2, 7, 4, 4] [4, 5, 2, 6, 5]

When `index`

is 1, there isn’t anything to do, since we can’t look “up” at anything. Therefore, move on.

Index: 2 [7] [10, 15] <--- Was: [3, 8] [8, 1, 0] [2, 7, 4, 4] [4, 5, 2, 6, 5]

When `index`

is 2, we look up and to the left (7), and up and to the right (also 7). Each time through the loop, we create a new temporary array called `next_row`

, in which to store the running sums. In this case, we create a new array `[10, 15]`

by adding 7 to each of `[3, 8]`

. We then replace the old array with the new.

Index: 3 [7] [10, 15] [18, 11, 16, 15] <--- Was: [8, 1, 0] [2, 7, 4, 4] [4, 5, 2, 6, 5]

`index`

is now 3. We perform the same operations as above: first, create an empty array. Then, for each element in the old array `[8, 1, 0]`

, we add the value of the element (which we’ll call `this`

in our program code) to the values of `upleft`

and `upright`

(these are obviously our variable names for the “up and to the left” and “up and to the right” values we’ve already mentioned). In each case we push the results of these additions onto the new temporary array. Once we’ve finished, we replace the existing array with the new, as before.

Index: 4 [7] [10, 15] [18, 11, 16, 15] [20, 25, 18, 15, 20, 20] <--- Was: [2, 7, 4, 4] [4, 5, 2, 6, 5] Index: 5 [7] [10, 15] [18, 11, 16, 15] [20, 25, 18, 15, 20, 20] [24, 25, 30, 27, 20, 24, 21, 20] <--- Was: [4, 5, 2, 6, 5] Result: 30

Here we show two steps more of the process, and its completion. We can easily see that 30 is the largest sum in the last array, and our answer.

We notice that the “new” interior arrays we’re creating on each turn through the loop are longer than the originals they replace, so we’re not being as efficient with memory as we’d like. At least Array expansion is an *O(n)* operation!

## The Complete Program Listing of `triangle.rb`

This essay is over 1200 words long already according to `wc -w`

. Therefore, since this algorithm can be described very succinctly in code, I’ll break the rules of literate programming and simply end with the program listing itself. Note the temporary variables `next_row`

, `this`

, `upleft`

, and `upright`

, which are described in the section “Visualizing Our Movement Down the Triangle” above.

As always, the contents of this literate program are available at Github.

(Update: better solutions and discussion over at the Ruby Reddit)

#!/usr/bin/env ruby require 'test/unit' INPUT_FILE = "triangle-input.txt" OUTPUT_FILE = "triangle-output.txt" def read_triangle_input tmp = [] File.open(INPUT_FILE, "r") do |f| f.lines.each do |line| tmp.push line.split end end tri = tmp.map { |array| array.map { |elem| elem.to_i } } end def write_triangle_output(result) File.open(OUTPUT_FILE, "w") do |f| f.print result end end def triangle_sum(tri) a = Array.new(tri) index = 1 len = a.shift[0]-1 while index <= len next_row = [] for i in 0..index this = a[index][i] upleft = a[index-1][i-1] upright = a[index-1][i] if i == 0 next_row.push this + upright elsif i == index next_row.push this + upleft else next_row.push this + upleft next_row.push this + upright end end a[index] = next_row index += 1 end a[index-1].max end tri = read_triangle_input highest_sum = triangle_sum(tri) write_triangle_output(highest_sum) class TestTriangleSum < Test::Unit::TestCase def test_01 tri = read_triangle_input expected = triangle_sum(tri) assert_equal expected, 30 end end

(Image courtesy Mélisande* under Creative Commons license.)

you can replace the split and convert to integer by the following shortcut:

File.open(INPUT_FILE, “r”) do |f|

f.lines.each do |line|

tmp.push line.split #your code

tmp.push line.split.map(&:to_i) #shorter one

end

end

Like this you will not need to run over the array once again:

#line to remove

tri = tmp.map { |array| array.map { |elem| elem.to_i } }

Very nice, thanks. I need to retrain my brain to think about chaining methods together in a more functional style.

This approach is “very” imperative, that would translate to C++ just by changing the commands.

This is a binary tree, so another imperative approach would be to use bits to represent the stepping decisions (go left, go right), and a method to walk the given path.

You would then start at %0000 and increment it up to %1111.

For example %0101 means: go left, go right, go left, go right, and the function returns the sum of the path. If that sum is greater than the previous, you discard the previous.

8+8+7+7+5 sure its 30 ….

Wow, so embarrassing. I think the number is 36, but your point stands! Thanks for pointing that out.

I read this in 2015

I prefer bottom-up approach. Here is what I tried to code in Java and yes the answer to the above input is 30.

import java.io.*;

import java.util.StringTokenizer;

public class SumTrainStringToken {

public static void main(String args[])throws IOException

{

BufferedReader obj=new BufferedReader(new InputStreamReader(System.in));

int t=Integer.parseInt(obj.readLine());

StringTokenizer st;

while(t–>0)

{

int a=Integer.parseInt(obj.readLine());

int arr[][]=new int[a][a];

for(int i=0;i<a;i++)

{

st=new StringTokenizer(obj.readLine());

for(int j=0;j=0;i–)

{

for(int j=0;jright)?below:right;

}

}

System.out.println(arr[0][0]);

}

}

}