Project Euler: Problem 2 in Ruby

My solution for Project Euler problem #2 came out a little fugly mainly because of the global variables, but it works. The “secret” to getting the program to run in a reasonable amount of time is to store the values of the fibonacci sequence as you compute them instead of processing the same data over again.

Problem #2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

My Solution

max    = 4_000_000
total  = 0
$stack = []

def fib n
  if n == 0
    return 1
  end
  if n == 1
    return 2
  end
  return $stack[n - 1] + $stack[n - 2]
end

max.times do |i|
  $stack[i] = fib i
  if $stack[i] > max
    break
  end
  if $stack[i] & 1 == 0
    total += $stack[i]
  end
end

puts total

As is quickly becoming the case, Olathe’s solution was much more elegant than mine:

x, y, sum = 1, 1, 0
while sum < 1_000_000
  sum += (x + y)
  x, y = x + 2*y, 2*x + 3*y
end
 
puts "Sum is #{ sum }."