Skip to content

The triangle problem

2012 October 7
by Richard Harrington

Recently I had to hire someone to help me out at work, and I was running the interviews, which I’d never done before.

My two co-workers (Ruby guys) told me that when one of them had been interviewing to work at our company, he was sent an exercise to complete. My other co-worker was already working there. He had tried the problem also, and had come up with a long, convoluted solution. So when the new guy emailed back with something that was about fifteen lines long, they hired him.

Here’s the problem: You have a triangle of numbers, like

     1
    4 3
   1 9 7 
  1 1 5 9

and the question is, what is the greatest of all the sums that you can get by tracing a path of adjacent numbers from the top of the triangle and adding one number per row as you go down the rows?

For instance, in this case the answer is 20: the sum of the numbers 1, 3, 7, and 9, tracing a path down the right edge.

(On the github page which goes along with this blog post, a text file called ‘triangle.txt’ is provided for this exercise which has 100 rows, too many to calculate without automating it. The answer to the problem for that text file is 732506.)

Before looking at either of my co-workers’ solutions, I tried it myself and thought I had come up with a pretty elegant solution using recursion and memoization to calculate all of the possible answers and store the partial ones as it goes along so it doesn’t take forever. The array it creates is, instead of numbers, an array of objects, where each object is a node in a tree containing pointers to the next two nodes down, as well as the value of the current node.

Here’s my code. It is intended to be run in Node.js on a file in the current directory, but you could change the beginning a little bit and run it on a string or something in the browser:

var fs = require('fs');
 
var max = function (file) {
 
  var text = fs.readFileSync(file, 'ascii');
  var array = text.split('\n').map(function(row) {
    return row.trim().split(' ').map(function(word) {
      return { num: parseInt(word) };
    });
  });
 
  array.forEach(function(row, i) {
    row.forEach(function(node, j) {
      var next_row = array[i+1];
      if (next_row) {
        node.left = next_row[j];
        node.right = next_row[j+1];
      };
    });
  });
  var root = array[0][0];
 
  return (function walk_tree(node) {
    if (!node) return 0;
    if (typeof node.memo_sum !== 'undefined') return node.memo_sum;
    node.memo_sum = node.num + Math.max(walk_tree(node.left), walk_tree(node.right));
    return node.memo_sum;
  })(root);
 
}  
 
console.log(max('triangle.txt'))

Then I looked at my co-worker’s solution, which is here (I have slightly modified it and translated it from Ruby to JavaScript, but this is the basic gist). It turns the triangle upside down and goes through it from the wide top to the single-element bottom, replacing each number in the triangle with the partial results based on the ones above it:

var fs = require('fs');
 
var max = function (file) {
 
  var text = fs.readFileSync(file, 'ascii');
  var array = text.split('\n').map(function(row) {
    return row.trim().split(' ').map(function(word) {
      return parseInt(word);
    });
  });
 
  array.reverse();
  array.forEach(function(row, i) {
    row.forEach(function(num, j) {
      if (i > 0) {
        var previousRow = array[i - 1];
        row[j] += Math.max(previousRow[j], previousRow[j + 1]);
      }
    });
  });
 
  return array[array.length - 1][0];
}  
 
console.log(max('triangle.txt'));

His was a lot shorter than mine, and more elegant. It was a lesson to me: recursion may seem cool, but it’s not always the best idea.

However, taking it up where my co-worker left off, I was able to make his version even more elegant by using the reduceRight array method, thus making it more pure, functional-programming-wise. My new function starts from the bottom of the triangle and works its way up, constantly updating an accumulator (called ‘sumRow’) that is a row of partial results, but it doesn’t touch the original array:

var fs = require('fs');
 
var max = function (file) {
 
  var text = fs.readFileSync(file, 'ascii');
  var array = text.split('\n').map(function(row) {
    return row.trim().split(' ').map(function(word) {
      return parseInt(word);
    });
  });
 
  return array.reduceRight(function(sumRow, row) {
    return row.map(function(num, i) {
      return num + Math.max(sumRow[i], sumRow[i + 1]);
    });
  })[0];
 
};
 
console.log(max('triangle.txt'));

As an exercise, I made versions of all these files in JavaScript, Ruby, and CoffeeScript, to see how they compared. You can see them on the github page. On that page I also added one final version in CoffeeScript which uses comprehensions to make it incredibly short, although it’s a little hard to read, I think. I’ll give it the benefit of the doubt in this case, though, and assume that I just don’t know how to write proper idiomatic CoffeeScript yet:

fs = require 'fs'
 
max = (file) ->
 
  array = ((parseInt word for word in row.trim().split(' ')) for row in fs.readFileSync(file, 'ascii').split('\n'))
 
  result = array.reduceRight (sumRow, row) ->
    num + Math.max sumRow[i], sumRow[i + 1] for num, i in row
 
  result[0]
 
console.log max 'triangle.txt'

Leave a Reply

Note: You may use basic HTML in your comments. Your email address will not be published.

Subscribe to this comment feed via RSS