How Many Ways from A to C via B? Counting the Unique Paths Walking in a Grid

Let’s see this question: If Jack starts at A, and he can only travels one move at a time to the north or east, and he cannot go back. If he needs to travel through B, and finally reach C, how many ways are there for him to complete his journey?

travel-from-a-to-b-to-c

Brute-force?

In theory, you can write a program to count each possible path from A to C, then, only those paths through B are valid. This could take ages. For example, if A and B are separated by x steps horizontally and y steps vertically (x steps east and y steps north), the total number of paths is:

or

This reads: the number of ways to choose x or y items from (x + y) items. In this case, the x=8 and y=9, which makes the bruteforce inefficient.

Pure Math Solution

A better way is to simplify the problem into two steps. First is to travel from A to B and the second step is to travel from B to C, thus, if we denote f(a, b) the number of paths from a to b, then the total number is:

.

According to the above, and which sums up to 8820.

Recursion

Let’s write a function f(x, y) which returns the number of different paths for x steps east and y steps north.

function f($x, $y) {
  if (($x == 0) || ($y == 0)) {
    return 1;
  }
  return f($x - 1, $y) + f($x, $y - 1); // we can take either 1 step north or 1 step east.
}

And the answer is just:

echo f(3, 4) * f(5, 5); // 8820

For each recursive call, there are two choices: 1 step north or 1 step east, so the answer is just to add these two (decompose into two smaller problems). The exiting conditions are when the offset is zero (step count is zero), this is when the answer should be returned as 1.

Dynamic Programming (Memorization)

The recursion is straightforward. However, it does not work well if the input is large, as a lot of intermediate results are computed again and again. You can memorize the intermediate results, which will speed up the computation (each f(x,y) is only computed once because next time the result will be fetched from memory):

$cache = array();

function f($x, $y) {
  global $cache;
  if (($x == 0) || ($y == 0)) {
    return 1;
  }
  $key = $x.' '.$y; 
  if (isset($cache[$key])) { // has the result been computed?
    return $cache[$key];
  } 
  $sol = f($x - 1, $y) + f($x, $y - 1);
  $cache[$key] = $sol; // store the result
  return $sol;
}

The next improvement to improve this Dynamic Programming DP implementation is to use the iteration, which avoids the recursion. This is computed bottom-up direction.

function f($x, $y) {
  $ans = array();
  for ($i = 0; $i <= $x; ++ $i) $ans[$i][0] = 1;
  for ($i = 0; $i <= $y; ++ $i) $ans[0][$i] = 1;
  for ($i = 1; $i <= $x; ++ $i) {
    for ($j = 1; $j <= $y; ++ $j) {
      $ans[$i][$j] = $ans[$i - 1][$j] + $ans[$i][$j - 1]; 
    }
  }
  return $ans[$x][$y];
}

This runs at complexity O(xy) as well as the space complexity (need to declare a 2-dimensional array). Is this optimial? No, you can further reduce the complexity to O(y).

Algorithms to Walk in a Grid

Here are some posts on the path counting or probability on a Grid:

• Teaching Kids Programming – Probability Matrix of Walking in a Grid (Unique Paths)
• Teaching Kids Programming – Count Number of Ways to Walk in a Grid using Dynamic Programming or Combination
• How Many Ways from A to C via B?

–EOF (The Ultimate Computing & Technology Blog) —