Snippet

project_euler/15.rb

Code:

# Project Euler Problem 15: Lattice Paths

# https://projecteuler.net/problem=15

# Starting in the top left corner of a 2 × 2 grid, and only being able to move
# to the right and down, there are exactly 6 routes to the bottom right corner.
# How many such routes are there through a 20 × 20 grid?

$cache = {}

def path(x, y)
    return 1 if (x == 0 || y == 0)
    return $cache[[x, y]] if $cache.key?([x, y])
    count = path(x - 1, y) + path(x, y - 1)
    $cache[[x, y]] = count
    return count
end

puts path(2, 2)
puts path(20, 20)

Output:

6
137846528820