Dec

16

Project Euler: Determining the number of paths in a grid

Filed Under hisabati, project euler by  

For problem 15 from Project Euler, we are asked to find the number of paths leading from the top left corner of a grid to the bottom right corner that do not involve backtracking.

Starting in the top left corner of a 2 by 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20 by 20 grid?

Given the way the problem is set up, for any one node there are at most two nodes that can lead directly to the node. If we assign coordinates to the grid with (0,0) being the top-left corner, the only nodes that have direct outgoing paths to (1,1) are (0,1) and (1,0). Trivially, each of the nodes in row 0 (the top row) has only one node that can lead into it (the node immediately to its left). Similarly, nodes in column 0 (the left-most column) each have one node leading into them (the node immediately above them). We can use this information to calculate the number of paths ending at any one node in the grid.

To do this, consider nodes A, B and C that form the lower right triangle of an arbitrary square in the grid. We label the nodes such that A is the lower left corner of the square, B is the lower right corner while C is the upper right corner of the square. As shown before, the only way to get a path ending at B is to take a path ending at either A or C and add one step to it. We also know that a path ending at A cannot pass through C (since we don’t allow backtracking) and similarly a path ending at C cannot pass through A. Therefore, the number of paths ending at B = number of paths ending at A + number of paths ending at C.

This leads to the following rather short algorithm:

  1: def num_paths_to_grid_bottom(numRowCells, numColumnCells):
  2:     currRow = [1 for x in range(numColumnCells + 1)]
  3:     # the number of nodes to consider = numRowCells + 1
  4:     for numRow in range(1, numRowCells + 1):
  5:         for numColumn in range(1, numColumnCells + 1):
  6:             currRow[numColumn] += currRow[numColumn - 1]
  7:     return currRow[numColumnCells]

Comments

Comments are closed.