Pathfinding in a lattice - help to understand example

Question

I am working on a problem where I calculate the number of possible paths to a lattice of N * N possible options. There have been some mathematical answers that suggest a simple "combinatorics" answer, but I have no experience with combinatorics. Searching around I found this relatively short answer, but it does not make much sense to me, even when I try to step through the sequential logic to follow the code.

#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 rows = grid_size - 1; rows >= 0 ; --rows) {
    for (int cols = grid_size - 1; cols >= 0; --cols) {
      int pos = (cols * (grid_size + 1)) + rows;
      grid.at(pos) = grid.at(pos + 1) + grid.at(pos + (grid_size + 1));
    }
  }
  return grid.at(0);
}

int main()
{
  std::cout << "Paths: " << lattice_path(20) << std::endl;
  return 0;
}

This code was taken from http://tvarley.github.io/blog/euler/cpp/problem_015 this website - (bad author for submitting answers xD) - some edits to make cleaner.

I chose this code because of my goals to use STL containers and method/member functions to solve the problem, but the sequential logic makes little sense to me in this example.

Usually the problems on projecteuler have simpler precursor examples (like the 2x2 grid) which are easy to model out in code by examining sequential logic. Then it is as simple as putting in the larger test. In this case, though, I can't really model out the simple lattice in code.

Answer 1

There are quite a few ways how you can arrive at the correct answer for this question, depending on how you approach it.

I would highly recommend you to first try to solve the puzzle on your own & not to look at other solutions - that usually has the best learning effect.

I'll only explain the logic behind the different approaches, but not provide any code examples for them.

Number of paths to a specific point

There are only two ways you can arrive at a certain point in the grid: either you come to it from the point directly above from it or from the point directly to it's left.

For the top & left side of the grid it's easy; there is only one way to reach each point - by moving straight in the specific direction, e.g.:

From that you can start to fill in the number of possible paths to each point. Because there are only 2 ways on how to get to each point, the number of possible paths to a specific point is the sum of the possible paths of the point directly to the left and the point directly above that point, e.g.:

From that you can just keep going to fill in all the other points on the grid until you reach the bottom-right corner, which will contain your solution:

In this case for a 3 × 3 grid the number of possible paths would be 20.

This is also the approach your code sample uses: it calculates the number of possible paths for each point in the grid - although it does so from the bottom to the top instead of from the top to the bottom like in my example.

Here's a godbolt that shows the grid your code is building.

---

Noticing the pattern

From the above approach you might notice two things:

• We calculate each number as the sum of two neighbors
• The numbers seem to follow some pattern

In fact the numbers we were calculating are the binomial coefficients - notice how the 3 × 3 grid from above matches the elements of pascal's triangle:

So you can cut out the grid calculation from above & instead simply calculate the binomial coefficient you're looking for.

In this case for a x × y grid the formula would be:

If we pluck in 20 for both x & y we get the correct answer as well:

---

Always the same moves

You're only ever allowed to move either right or down - so the only way to get one square down is to move down, and the only way to get to the right is a move to the right (and there's no way to move left / up) - so the amount of moves you make - regardless of which path you take - is always the same.

Namely exactly the height of the grid moves down and exactly the width of the grid moves to the right.

e.g. on a 4x3 grid you get exactly 4 moves to the right and 3 moves down:

So at the beginning you have a "bag" of all moves you can make, in the above case it would be {⮞,⮞,⮞,⮞,⮟,⮟,⮟} and at every point of the path you get to choose if you want to take a ⮞ or a ⮟ from your bag, to move into that direction (unless you run out of one, in that case you only have one choice).

The mathematical term for this "bag" would be a Multiset.
In the above case we could also write it as {⮞⁴, ⮟³}, to make it shorter.

Now to answer the question how many possible paths there are we need to find out how many possible ways there are to use the elements from our multiset, e.g.:

⮞⮞⮞⮟⮞⮟⮟, ⮟⮞⮟⮞⮟⮞⮞, etc...

So we're looking for all possible permutations of our multiset (with the same length as we have elements in the multiset)

This is called a multiset permutation, and the formula for it is quite easy to remember:

where n is total amount of items in the multiset (7 in the example above), and m₁, m₂, etc... are the counts of each element in the set (in this case we just have m₁ = 4 and m₂ = 3, so n = 7).

So to generalize it in a grid of size x × y the formula for the number of possible paths would be:

If you pluck in 20 for both x & y into the above equation you get the same correct answer of 137846528820, for the number of possible paths in a 20 × 20 grid.

This approach also has the benefit that it works in more than 2 dimensions, e.g. you could also solve a 3 dimensional variant of this puzzle with this.