Project Euler : Problem 15 - Lattice paths

Problem Statement : Lattice paths

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?

Concept and Theory

One can see from the above diagram, the number of routes from $(0,0)$ to $(m, n)$ is equal to the number of routes from $(0,0)$ to $(m−1, n)$ plus the number of routes from $(0,0)$ to $(m, n−1)$. A very simple recursive algorithm can be written based on the above observation.

Recursive Programming

/**
 * A function which returns the number of the path from one corner to other
 * corner in a grid
 *
 * @param n : length of the grid
 *
 * @param m : height of the grid
 *
 * @return number of the paths
 */
public static int countRoutes(int n, int m) {
  if (n == 0 || m == 0) {
    return 1;
  } else {
    return countRoutes(n, m - 1) + countRoutes(n - 1, m);
  }
}

But again the problem is that we are recomputing some points again and again. Cache them!!!

Dynamic Programming

/**
 * A function which tells the number of ways of reaching the bottom right corner
 * from top left corner
 *
 * @param n : width of the grid
 *
 * @param m : height of the grid
 *
 * @return the numbers of ways
 */
public static long getTotalPath(int n, int m) {
  long M = 1000000007L;
  long[][] grid = new long[n + 1][m + 1];

  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      if (i == 0 || j == 0) {
        grid[i][j] = 1;
      } else {
        grid[i][j] = (grid[i - 1][j] + grid[i][j - 1]) % M;
      }
    }
  }

  return grid[n][m];
}

Mathematical Approach

Since we can only move right or down, we will be needing $m$ steps right and $n$ steps down always, to reach the bottom corner. So the number of combinations of $m$ rights and $n$ down moves is our answer. Thus the formula for such combination is given as,

$$\frac{(m+n)!}{n! \times m!}$$

A single configuration, once we place the the right movements we immediately know where the downward movements must go (as they cannot go anywhere else). All we really have to know is how many ways we can place the right movements. The number of ways we can do this, mathematically, is denoted with the binomial coefficient $\binom{m+n}{m}$.

Mathematically choosing $k$ elements from $n$ elements is given as follows,

$$\binom{n}{k} = \frac{n!}{k!(n-k)!} \\ = \frac{n(n-1) \dots (n-k+1)}{k!}$$

Using this formula we can calculate $\binom{m+n}{m}$,

$$\binom{m+n}{m} = \frac{(m+n)!}{m! n!}$$

When $m=n$

$$\binom{2m}{m} = \frac{2m \times (2m-1) \times \dots \times (m+1)}{m \times (m-1) \times \dots \times 2 \times 1} \\ = \prod_{i=1}^{m} \frac{m+i}{i}$$

Test Your Skills

Wanna try a harder version of the above problem ? Check this HackerRank problem.

Solution

The solution will remain same as given in the above mentioned post, $getTotalPath$, you just need to call it for each test case.

References and Further Readings

• ProjectEuler
• Wolfram