# What is the Highest Sum of a Number Triangle?

## 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.

• 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.

## 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"

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

highest_sum = triangle_sum(tri)
write_triangle_output(highest_sum)

class TestTriangleSum < Test::Unit::TestCase
def test_01
expected = triangle_sum(tri)
assert_equal expected, 30
end
end
```

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

# Finding the Equilibrium Index of an Array

## The Problem Description

A zero-indexed array A consisting of N integers is given. An
equilibrium index of this array is any integer P such that 0 <=
P < N and the sum of elements of lower indices is equal to the sum
of elements of higher indices, i.e.,

```A[0] + A[1] + ... + A[P-1] =
A[P+1] + ... + A[N-2] + A[N-1].
```

The sum of zero elements is assumed to be equal to 0.

Write a function that, given a zero-indexed array A consisting of
N integers, returns any of its equilibrium indices. The function
should return -1 if no equilibrium index exists.

• Expected worst-case time complexity is O(N)
• Expected worst-case space complexity is O(N), beyond input storage

(not counting the storage required for input arguments).

The above is taken from the problem description by Codility; they discuss one solution (written in C) here.

## Notes on this Implementation

First things first: we’ll avoid the `return -1` “C-ism,” as it’s more natural to return `nil` in Ruby. In fact, Ruby sees -1 as `True`, so returning it will break many common predicates, whereas `nil` won’t.

Experienced programmers will observe that this implementation does not meet the `O(n)` time and space complexity requirements as listed above. Absolute simplicity of implementation is the focus right now, but that may change in a future version.

Finally, notice that this short essay is itself a literate program, implemented using the wonderful Org-mode capabilities which are included with the Emacs text editor.

## The Inner Loop

Since most of the program’s work is done inside a single `while` loop, we’ll begin there.

Let A be the Ruby array

```[-7, 1, 5, 2, -4, 3, 0].
```

The equilibrium index of A can be computed by hand, so it’s a good place to start. It’s also our first test case (see below).

We’ve chosen to implement the iteration over A using a `while` loop rather than the more idiomatic `Array#each` method since we need to keep track of our current index into the array.

As we begin the loop, the variable `index` is initialized as the length of the array minus one. This is required because Ruby’s arrays are zero-based, but the value returned by its `Array#length` method is not.

```while index > 0
left  = a[0..index-1].reduce(:+)
right = a[index+1..len].reduce(:+)
if left == right
return index
end
index -= 1
end
```

We’ll iterate backwards through the array from the end. At each value of `index`, we’ll split A into two smaller arrays, `left` and `right`. This requires allocating two new arrays in memory, reading the values of the desired “slices” of A, and copying them into `left` and `right`, respectively. This operation provides for an implementation that is simple to visualize and understand, but it’s also the reason why we fail to meet the requirements for `O(n)` space and time complexity. A more efficient implementation would avoid these unnecessary allocation and copying steps, and we might change this program at some point to achieve that.

## Visualizing the Iteration

Let’s look at `left` and `right` at each stage of the iteration:

We can see that when we split A at `index`, we always leave a “gap” in between, and it’s this gap which will provide us with the answer we seek: the equilibrium index (provided that the equilibrium index is defined for the given array, that is). At every iteration in the diagram above, we sum the values within `left` and `right` using the `Array#reduce` method. If `left` and `right` are equal, `index` is defined as the equilibrium index, and we `return index`. Otherwise, we’ll end up escaping the loop and returning `nil`.

## The `equi` Function

Looking briefly at the entire `equi` function, we can see that it’s just a wrapper for the `while` loop. First we set the value of `index` and `len` as bookkeeping measures. We then enter the `while` loop as described above. If the loop completes without returning a value, the program returns to the next outer context and returns the `nil` value, which lets our caller know that this array doesn’t have an equilibrium index.

```def equi(a)
index = a.length-1
len   = a.length-1
while index > 0
left  = a[0..index-1].reduce(:+)
right = a[index+1..len].reduce(:+)
if left == right
return index
end
index -= 1
end
nil
end

```

## Test Cases

Over the course of developing the program, a number of test cases have come to mind. We’ll begin with the given array A that we started with.

```def test_random
sample_array = [-7, 1, 5, 2, -4, 3, 0]
expected = equi(sample_array)
assert_equal expected, 3
end

```

Here we’ve defined a trivial `pyramid’ array of values that ascend and descend symmetrically.

```def test_trivial_pyramid
sample_array = [1, 2, 3, 4, 3, 2, 1]
expected = equi(sample_array)
assert_equal expected, 3
end
```

This test checks the case where the first value is equal to the sum of all the rest (save the equilibrium index, of course).

``` def test_biggest_first
sample_array = [99, 0, 66, 32, 1]
expected = equi(sample_array)
assert_equal expected, 1
end
```

Similarly, we check for the case where the last value alone is equal to the sum of `left`.

```def test_biggest_last
sample_array = [66, 32, 1, 0, 99]
expected = equi(sample_array)
assert_equal expected, 3
end
```

We should return `nil` for an array with a single element, since the equilibrium index is not defined in that case.

```def test_single_element
sample_array = [0]
expected = equi(sample_array)
assert_equal expected, nil
end
```

The same is true of an array containing a single `nil`.

```def test_single_nil
sample_array = [nil]
expected = equi(sample_array)
assert_equal expected, nil
end
```

## The Complete Program Listing

Finally, we have the complete program listing for the `tangle`‘d file `literate-equi.rb`. Since we’ve included our tests by subclassing the `Test::Unit` class, Ruby will run them for us when we invoke the program. Running `ruby literate-equi.rb` at the command shell should return the following output:

```~/Desktop/Dropbox/current/logicgrimoire \$ ruby literate-equi.rb
Started
......
Finished in 0.002195 seconds.

6 tests, 6 assertions, 0 failures, 0 errors
```

The program itself:

```#!/usr/bin/env ruby

require 'test/unit'

def equi(a)
index = a.length-1
len   = a.length-1
while index > 0
left  = a[0..index-1].reduce(:+)
right = a[index+1..len].reduce(:+)
if left == right
return index
end
index -= 1
end
nil
end

class TestEqui < Test::Unit::TestCase
def test_random
sample_array = [-7, 1, 5, 2, -4, 3, 0]
expected = equi(sample_array)
assert_equal expected, 3
end

def test_trivial_pyramid
sample_array = [1, 2, 3, 4, 3, 2, 1]
expected = equi(sample_array)
assert_equal expected, 3
end
def test_biggest_first
sample_array = [99, 0, 66, 32, 1]
expected = equi(sample_array)
assert_equal expected, 1
end
def test_biggest_last
sample_array = [66, 32, 1, 0, 99]
expected = equi(sample_array)
assert_equal expected, 3
end
def test_single_element
sample_array = [0]
expected = equi(sample_array)
assert_equal expected, nil
end
def test_single_nil
sample_array = [nil]
expected = equi(sample_array)
assert_equal expected, nil
end

end
```