I found this one to be very similar to problem #15, so it “clicked” pretty quickly. I basically just store the solutions so I don’t have to do any re-computing.

I saw a pretty slick method in the forums that made use of Ruby’s Enumerable module which I’ll have to give a go next time I run into something like this.

Problem #18

Find the maximum total from top to bottom of the triangle below:

input = # triangle goes here

tree = []
cache = []

input.split("n").each do |row|
  tree << []
  cache << []
  row.split("s").each do |i|
    tree.last << i.to_i
  end
end

def sum tree, cache, row, index, total

  if tree[row] == nil or tree[row][index] == nil
    return 0
  end

  if cache[row][index] != nil
    return total += cache[row][index]
  end
  
  left  = sum( tree, cache, row + 1, index, total )
  right = sum( tree, cache, row + 1, index + 1, total )

  cache[row][index] = [left, right].max + tree[row][index]

end

puts sum( tree, cache, 0, 0, 0 )