Tim Varley Tim Varley

Euler 015 c++ Solution

Lattice paths
Feb 11, 2015
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.cpp

#include <iostream>
#include <vector>

uint64_t lattice_path(size_t grid_size)
{
  std::vector< uint64_t > grid((grid_size+1)*(grid_size+1),1);

  for (int x = grid_size-1; 0 <= x ; x--) {
    for (int y = grid_size-1; 0 <= y; y--) {
      int pos = (y*(grid_size+1))+x;
      grid.at(pos) = grid.at(pos+1) + grid.at(pos+(grid_size+1));
    }
  }
  return grid.at(0);
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[])
{
  std::cout << "Answer: " << lattice_path(20) << std::endl;
  return 0;
}
#endif // #if ! defined UNITTEST_MODE

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