#! /usr/local/bin/ruby

def time
  start = Time.now
  result = yield
  diff = Time.now - start
  puts "Elapsed time: #{diff} secs"
  p result
end

module Memoization
  private \
  def make_cache(arity)
    seed = "{}"
    (arity - 1).times do
      seed = "Hash.new { |h, k| h[k] = #{seed} }"
    end
    eval(seed)
  end

  def memoize(name)
    arity = method(name.to_sym).arity
    args = arity.times.map { |i| "x#{i}" }.join(",")
    args2 = arity.times.map { |i| "[x#{i}]" }.join
  
    instance_eval(<<~EOS)
      cache = make_cache(#{arity})
      define_singleton_method(name) do |#{args}|
        cache#{args2} ||= super(#{args})
      end
    EOS
  end
end

def tarai(x, y, z)
  return y if x <= y
  tarai(
    tarai(x - 1, y, z),
    tarai(y - 1, z, x),
    tarai(z - 1, x, y),
  )
end

extend Memoization
memoize :tarai

time { tarai(100, 50, 0) }
time { tarai(100, 50, 0) }