Monday, May 19, 2008

Binomial robot

Stumbled upon a Google Treasure Hunt 'brainteaser':

A robot is located at the top-left corner of a n x k grid.
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.
How many possible unique paths are there?
(Note: Answer must be an exact, decimal representation of the number. Image not to scale.)

Do not continue if you don't want your brain-teasing to by spoiled.

Let's see, the robot will take N = (n-1)+(k-1) steps. Out of these N steps, n-l will be down and k-1 will be right. Now, one may recall the binomial coeficient: we want to know how many different ways the robot can take these N steps, i.e. how many different ways he can choose to go either down or right. To put it into an other way: we want to find out the number of combinations the robot can choose to go down. This implies that the answer is ((rows-1+cols-1)!)/((rows-1)!*(cols-1)!).

But the correct answer can be found without recalling any binomial or combination stuff. This quick and dirty java code gives the answer as well. The idea here is that for a two-row grid, the number of possible different paths is k: the robot can pick any of the k columns in the grid to take his single down step. Now what happens if we add an additional row, say a third row? Now the robot can also walk straight through the new row and for all cells he can choose to go down. If he goes down into the second row in the i-th column, then the additional path possibilities are given by the result of a similar puzzle where n = n-1 and k = k-1-i;
Hence adding an extra row means we have to sum over k the possibilities of the same problem with n-1 rows.
final int ROWS = 57; //n
final int COLS = 44; //k
BigInteger [][] result = new BigInteger [ROWS+1][COLS+1];
private BigInteger sumPrevLevel(int row, int cols){
BigInteger res = new BigInteger("0");
for (int col = 1; col <= cols; col++){
res = res.add(result[row-1][col]);
return res;
public void testTreasureHunt(){
for (int row = 0; row <= ROWS; row++){
result [row][0] = new BigInteger("0");
for (int col = 1; col <= COLS; col++){
result[0][col] = new BigInteger("0");
result[1][col] = new BigInteger("1");
//do the work
for (int row = 2; row <= ROWS; row++){
for (int col = 1; col <= COLS; col++){
result[row][col] = sumPrevLevel(row, col);
//print the result

No comments: