Tim Varley Tim Varley

Euler 015 ruby Solution

Lattice path
Apr 5, 2017
3 minute read

Problem

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.

Euler 015

How many such routes are there through a 20×20 grid?

Answer: 137846528820

Solution

euler015.rb

#!/usr/bin/env ruby

def lattice_paths(grid_size)
  grid_dimension = grid_size + 1
  grid = Array.new(grid_dimension * grid_dimension) { 1 }
  (grid_size - 1).downto(0) do |x|
    (grid_size - 1).downto(0) do |y|
      pos = (y * grid_dimension) + x
      grid[pos] = grid[pos + 1] + grid[pos + grid_dimension]
    end
  end
  grid[0]
end

puts lattice_paths(20) if __FILE__ == $PROGRAM_NAME

See Also

# cpp go java php ruby rust javascript
1
2
3  
4    
5    
6      
7          
8          
9          
10          
11          
12          
# cpp ruby
13
14
15
16
17
18
19
20  
21  
22  
23  
24