Project Euler 15: Lattice Paths

Starting in the top left corner of a 2 by 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?

The matrix to solve the problem is one larger than the number of squares in the challenge. Along the edges of the matrix, only one pathway is possible: straight to the right or down. We can calculate the number of possible paths for the other squares by adding the number to the right and below the point under consideration. The code loops through the matrix backwards, adding the number of paths step by step.

$$p_{i,j}=p_{i,j-1}+p_{{i+1},j}$$

For the two by two lattice the solution space is:

6  3  1
3  2  1
1  1  .

The total number of pathways from the upper left corner to the lower right corner is thus 6. This logic can now be applied to a grid of any arbitrary size using the following code. The code defines the lattice and initiates the boundary conditions. The bottom row and the right column are filled with 1 as there is only one solution from these points. The code then calculates the pathways by working backwards through the matrix. The final solution is the number is the first cell.

ProjectEuler

  ## Project Euler 15: Lattice Paths
  # Define lattice
  nLattice <- 2
  lattice = matrix(ncol = nLattice + 1, nrow = nLattice + 1)

  # Boundary conditions
  lattice[nLattice + 1, -(nLattice + 1)] <- 1
  lattice[-(nLattice + 1), nLattice + 1] <- 1

  # Calculate Pathways
  for (i in nLattice:1) {
      for (j in nLattice:1) {
          lattice[i,j] <- lattice[i+1, j] + lattice[i, j+1]
      }
  }
  answer <- lattice[1,1]
  print(answer)