23 May 09 Project Euler: Problem 67 in Ruby

I guess my solution to #18 was good enough since it worked for #67 as well.

Problem #67

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 )

Ran pretty fast in 1.8.6

$ time ruby 18.rb
real	0m0.012s
user	0m0.008s
sys	0m0.004s

$ time ruby 67.rb
real	0m0.115s
user	0m0.104s
sys	0m0.012s

And a little worse in 1.9

$ time ruby1.9 18.rb
real	0m0.028s
user	0m0.016s
sys	0m0.008s

$ time ruby1.9 67.rb
real	0m0.116s
user	0m0.104s
sys	0m0.004s

Tags: project euler, ruby