What is the Highest Sum of a Number Triangle?

https://logicgrimoire.files.wordpress.com/2012/02/wpid-paper-triangles.jpg

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

Advertisements

7 thoughts on “What is the Highest Sum of a Number Triangle?

  1. 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 } }

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

  3. 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]);
    }
    }

    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s