A Quantum Immortal

I have a friend that likes riddling me riddles, kind of like a sphinx.
The last riddle, out of a computer science course, asked to solve programatically the following problem:

You are in a lattice, at some position (x,y), with x>=0 & y>=0. How many different routes do you have for reaching the origin (0,0), where in each step you either go one unit down, or go one unit left?

I found three solutions, each better in time complexity than the previous one:

Solution 1 – Just translate the question

As the title of this post claims, a great deal of the magic of programming is knowing how to translate problems from human language to machine language. The first algorithm should be straight forward – just do as a human would:

public long CountWays1(int x, int y)
{
  if (x == 0 || y ==0)
  {
    // you've reached the edge of the positive quadrant
    // only one way from here - either straight down or straight left
    return 1;
  }
 
  // else, we're somewhere with x>=1 and y>=1.
  return
    // Either you go down now
    CountWays1(x, y-1) +
    // Or you go left
    CountWays1(x-1, y);
}

It’s easy to verify this solves the problem. No magic involved, just take the literal description of the problem and turn it into a language a computer will understand.

Solution 2 – Add a little cache

A quick complexity analysis will reveal actually running this program on not too large inputs will never complete. The solution is hyper-exponential (grows faster than 2^(x+y)). This is because the same sub problem is computed over and over again. When calculating CountWays1(40,40), you will calculate CountWays1(20,20) many times over again (I’m ignoring integer overflow for the sake of discussion). This can be solved by adding a cache, or memory, to our solution:

public long CountWays2(int x, int y)
{
  long[,] solutions = new long[x,y];
  return CountWays2Impl(x, y, solutions);
}
 
private long CountWays2Impl(int x, int y, long[,] solutions)
{
  if (x == 0 || y ==0)
  {
    // you've reached the edge of the positive quadrant
    // only one way from here - either straight down or straight left
    return 1;
  }
 
  // !!! Change from CountWays1 !!!
  if (solutions[x,y] != 0)
  {
    // we already know the solution for (x,y), let's not recalculate it
    return solutions[x,y];
  }
 
  // else, we're somewhere with x>=1 and y>=1, and you don't know the answer yet
  long solution =
    // Either you go down now
    CountWays1(x, y-1, solutions) +
    // Or you go left
    CountWays1(x-1, y, solutions);
 
  // !!! Change from CountWays1 !!!
  // We found the solution for (x,y), let's store the result in the array to avoid recalculations
  solutions[x,y] = solution;
  return solution;
}

In fact, this solution is so simple it can be “coded” in an Excel sheet. Just put 1 in the first row & column, put “=A2+B1” in the (2,2) cell, and copy this formula to all other cells.

The time and space complexity of this solution is O(x*y) – the size of our matrix, where filling every cell in it takes a constant amount of steps.

Solution 3 – Remember Pascal

After playing with Excel and actually calculated some values, I remembered this problem is actually equivalent to Pascal’s Triangle

An association every programmer should have for Pascal’s Triangle is combinatorics. If you think about the problem in terms of combinatorics instead computer science, you’ll see the solution is actually the total number of ways one can order a certain sequence of actions of length X+Y:

In X+Y moves, you will reach the origin (unless you step out of the positive quadrant). Every move is either Down or Left, so to get the number of ways you can calculate the total number of different orders of length X+Y, where every item is either Down or Left, and you have exactly X number of Lefts and Y number of Downs.

The number of ways to order a sequence of length X+Y is (X+Y)! Then, we divide by the number of ways to order the Left actions (X!), and by the number of ways to order the Down actions (Y!). This is because our initial number (X+Y)! counted the sequence “Left, Left, Down” twice.

So the most efficient way to answer the riddle is simply this:

public long CountWays3(int x, int y)
{
  return Factorial(x+y)/Factorial(x)/Factorial(y);
}
 
private long Factorial(int x)
{
  if (x <= 1)
    return 1;
 
  return x*Factorial(x-1);
}

(Note this is Tail Recursion, so don’t give me arguments about inefficient recursion – this can be optimized into a loop by the compiler).