euler problem 2 solution

euler2.rb

=begin
This computes the answer to Euler problem 2 at https://projecteuler.net/problem=2
The solution takes advantage that 
   - every 3rd number in the sequence is even
   - odd + odd = even 
   - even + odd = even

example below where [2], [8], [34], [144] are F3, F6, F9 

1,1,[2],3,5,[8],13,21,[34],55,89,[144]

by definition, F(n) = F(n-1) + F(n-2)
               F(n-1) = F(n-2) + F(n-3)
               F(n-2) = F(n-3) + F(n-4)

So by substitution we can arrive to F(n) = 4 * F(n-3) + F(n-6)

=end

class Euler2
  def initialize(limit)
    @limit = limit
  end

  def reset
    @fibMinus = 2           # F(n-3)
    @fibMinusMinus = 0      # F(n-6)
  end

  def multiplier
    4
  end
 
  def passes(num)
    num.even?
  end

  def answer
    reset()
    fibN = @fibMinus
    summed = @fibMinusMinus

    while fibN < @limit
      if passes(fibN) 
        summed += fibN 
      end 
      fibN = multiplier() * @fibMinus + @fibMinusMinus
      @fibMinusMinus = @fibMinus
      @fibMinus = fibN
    end
    summed
  end
end

class Euler2BothEvenAndOdd < Euler2
  def reset
    @fibMinus = 1           # F(n-1)
    @fibMinusMinus = 1      # F(n-2)
  end

  def passes(num)
    true
  end

  def multiplier
    1
  end
end

class Euler2Odd < Euler2
  def reset
    @fibMinus = 1           # F(n-1)
    @fibMinusMinus = 1      # F(n-2)
  end

  def multiplier
    1
  end

  def passes(num)
    num.odd?
  end
end

test_euler2.rb

require "./euler2"
require "test/unit"

class TestEuler2 < Test::Unit::TestCase

  def setup
    ## Nothing really
  end

  def teardown
    ## Nothing really
  end

  def test_answer
    assert_equal(4613732, Euler2.new(4000000).answer)
  end

  def test_other
    assert_equal(0, Euler2.new(2).answer)
    assert_equal(10, Euler2.new(10).answer)
    assert_equal(44, Euler2.new(143).answer)
    assert_equal(44, Euler2.new(144).answer)
    assert_equal(188, Euler2.new(145).answer)
  end

  def test_euler2_both_even_and_odd
    assert_equal(2, Euler2BothEvenAndOdd.new(2).answer)
    assert_equal(20, Euler2BothEvenAndOdd.new(10).answer)
    assert_equal(232, Euler2BothEvenAndOdd.new(143).answer)
  end

  def test_euler2_odd
    assert_equal(2, Euler2Odd.new(2).answer)
    assert_equal(2, Euler2Odd.new(3).answer)
    assert_equal(10, Euler2Odd.new(10).answer)
    assert_equal(23, Euler2Odd.new(20).answer)
    assert_equal(188, Euler2Odd.new(143).answer)
  end
end