Scott's Cheap Flights code exercise

README.md

I implemented this as a gem which can be found at https://github.com/tilthouse/scf_exercise For much higher performance, there exist native gems, We could also use the 'job_interview' gem: https://github.com/ruby-jokes/job_interview

FWIW, this seemed familiar. Turns out I did this problem from Project Euler in 2012. I did not create a gem for it at that time. My "get the answer quickly" solution from the time is at https://github.com/tilthouse/project_euler/blob/master/problems/002/answer002.rb I did look this up after doing this exercise again. My previous solution did not use caching, for example.

solution.rb

# Full gem I wrote for this exercise is at https://github.com/tilthouse/scf_exercise
# The core components are the main lib:
# -------------------------------------------------------------------------------------------
require 'fib/version'

module Fib
  class Recursive
    attr_accessor :values

    def initialize
      @values = {}
    end

    # Customers gotta have their fibbonacci numbers
    def value(n)
      return @values[n] unless @values[n].nil?
      @values[n] = if n < 1
                     0
                   elsif n <= 2
                     1
                   else
                     value(n - 1) + value(n - 2)
                   end
    end

    # This would not be in a real gem – but have to answer the
    # actual question somewhere
    MAX_FIB_VALUE = 4_000_000
    def self.project_euler_net_2
      fib_calculator = Fib::Recursive.new
      index = 0
      even_acc = 0
      last_value = 0
      while last_value <= MAX_FIB_VALUE
        last_value = fib_calculator.value(index)
        even_acc += last_value if last_value.even?
        index += 1
      end
      even_acc
    end
  end
end
# -------------------------------------------------------------------------------------------
# And the minitest test file:
# -------------------------------------------------------------------------------------------
require 'test_helper'

class FibTest < Minitest::Test
  context 'gem' do
    should 'have a version number' do
      refute_nil ::Fib::VERSION
    end
  end

  context 'recursive calculations' do
    setup do
      @fib = Fib::Recursive.new
    end
    should 'be correct for 0' do
      assert_equal 0, @fib.value(0)
    end

    should 'be correct for 1' do
      assert_equal 1, @fib.value(1)
    end

    should 'be correct for 2' do
      assert_equal 1, @fib.value(2)
    end

    should 'be correct for 3' do
      assert_equal 2, @fib.value(3)
    end

    should 'be correct for 4' do
      assert_equal 3, @fib.value(4)
    end

    should 'be correct for a large value' do
      assert_equal 12586269025, @fib.value(50)
    end

    should 'tell me the answer to Project Euler #2' do
      assert_equal 4613732, Fib::Recursive.project_euler_net_2
    end
  end
end
# -------------------------------------------------------------------------------------------