kirit.com
Return to Blog entry
After much head scratching, here is a pure maths solution….
If we have W as width of grid and H as height, then essentially every sequence of moves to get to bottom right will have W-1 'rights' and H-1 'downs'.
So for example in a 3 by 7 grid, the sequence of moves would be some combination of the 8 moves 'RRDDDDDD'
We essentially need to know the number of unique combinations of these letters. The total number of combinations is the factorial of the number of moves. For each possible combination, there will be a number of ways to re-arrange the Rs and Ds, so we will need to divide totall number of combinations by the number of ways to arrange the Rs and Ds
In the example above, there are 2! ways to arrange the Rs, and 6! ways to arrange the Ds
So the final number of solutions (paths for the robot) is in this case:
8! / (2! * 6!) = 40320 / (2*720) = 28
So, more generally:
Number of paths for robot = (W+H-2)! / ((W-1)! * (H-1)!)
(any simplification of this formula welcome!)
I came up with the same solution yesterday, but I didn't have post permission yet. The only simplification I can add is in terms of the computation: you don't have to calculate the factorials of all three numbers. This can easily be seen in your simpler example: 8! / (2! * 6!) = 8*7*6*5*4*3*2*1 / (2*1 * 6*5*4*3*2*1) = 8*7 / 2*1 = 56 / 2 = 28
Below is a Java program that calculates the final solution (which is 760,365,888,182,828,026,538,367,852). I used BigDecimals instead of BigIntegers, because I think there is a small chance that it not always possible to divide the two numbers in the for loop. However, it may very well be the case that I didn't have to worry about that. Anyway, it's not beautiful code, but it works.
import java.math.BigDecimal;
public class Treasure { public static void main(String[] args) { final int x = 54; final int y = 42; final int R = Math.min(x,y)-1; final int N = x+y-2; BigDecimal paths = new BigDecimal(1); for (int i = 0; i < R; i++) { paths = paths.multiply(new BigDecimal(N-i)).divide(new BigDecimal(i+1)); } System.out.println(“Paths: ”+paths); } }
By the way: there is a function on my calculator (TI-83) that would calculate this if it weren't for the too big numbers: N nCr R (or in this case 94 nCr 41)
Nice one Jon. This is the solution we discussed at BarCamp, but none of us could remember the formula for the combinations (or is it permutations? Can never remember which is which).
I'd missed the -1 bit on the possible moves in my code (whoops), but had also used the r and d convention. I was going through all of the permutations and counting them — turns out that's quite a lot to go through :(
I see my Java program is totally mangled… :-S Oh well…
I actually don't think it's very clear cut whether this is a permutation problem or a combination problem. In permutations the order of the elements matters, whereas in combinations it doesn't. I think that this problem is probably a permuation problem at heart, because you want the find the number of possible permutations of a sequence of moves to the right and to the bottom. However, Jon and I have restated the problem as a combination problem by asking “How many ways are there to pick R distinct integers from N distinct integers (as the indices of the moves to the right in the sequence)?”. I think you can usually do stuff like this, although in this case it is very easy, because there are only two possibilities for each move, so by having the indices for one kind of move, you can infer all moves.