# Project Euler - Problem 15
# http://projecteuler.net/index.php?section=problems&id=15
#
# Starting in the top left corner of a 2×2 grid, there are 6 routes
# (without backtracking) to the bottom right corner.
#
# *******  ****--+  ****--+  *--+--+  *--+--+  *--+--+
# |  |  *  |  *  |  |  *  |  *  |  |  *  |  |  *  |  |
# +--+--*  +--****  +--*--+  *******  ****--+  *--+--+
# |  |  *  |  |  *  |  *  |  |  |  *  |  *  |  *  |  |
# +--+--*  +--+--*  +--****  +--+--*  +--****  *******
#
# How many routes are there through a 20×20 grid?
 
class Problem15
  def solve
    count_paths [0, 0], 20
  end
 
  def count_paths(start, size)
    sx, sy = *start
 
    return 1 if sx == size || sy == size
 
    count_paths_cached([sx + 1, sy], size) +
    count_paths_cached([sx, sy + 1], size)
  end
 
  def count_paths_cached(start, dest)
    @cache ||= {}
 
    unless @cache.has_key? start
      @cache[start] = count_paths(start, dest)
    end
 
    @cache[start]
  end
end
 
puts Problem15.new.solve