The triangle problem
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:
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: