The first puzzle they have up goes something like this:
A robot is located at the top-left corner of a 52 x 52 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?
For a while I tried to picture the mechanics of this problem in my head. It was too much,.. I would soon get lost trying to keep track of a dozen different paths and shapes all at once. So i resorted to paper. Not too long and I was having good progress. I would draw grids with numbers in each cell representing how many paths could be made from that cell to the bottom right. The trick was to start small.
I drew grids for 2x2 and 3x3. I still couldnt work out the pattern,.. Then I drew 2x3 and 3x2 grids; Bingo.
Overlay/Imageine a 3x2 and 2x3 grid at the bottom-right of the grid above; To work out the total number of paths from the last missing cell (of 3x3) is simply all paths available in both the 2x3 and 3x2 grids. Still dont understand,..
Simply put: The number of unique paths from any cell to the finish is equal to the sum of, the number of paths from the cell on the right, and the cell below it.
Here is the Java source I used to calculate my grid (55 x 60). My answer was 696940125414123253093858308567840.
I would be interested in looking over the mathematical formula that calculates this directly incase anyone happens to know it.
Happy treasure hunting!
PS: My code calculates the map upside down and other way around... In other words, the robot is going from bottom right to top left. Not the same as the picture above.
7 comments:
the mathematical formula would be
(m+n-2)!/m!n!
Looks like Pascal's triangle to me.
I tried numbskull's formula and couldn't get it to work. I've probably made a silly error in my code. Here it is:
http://b22222.com/files/GoogleQuestion1_1.java
Any ideas?
Well the next puzzle was cool aswell. I'll post my code for that in a couple days once the question has aged a little.
The correct formula is:
((x-1)+(y-1))!/((x-1)!(y-1)!).
The numbers get very big very quickly, but it can be worked out with bc:
define fact(x) { if (x <= 1) return (1); return (fact(x-1) * x); }
define paths(x,y) { return(fact((x-1)+(y-1))/(fact(x-1)*fact(y-1))); }
paths(55,60)
696940125414123253093858308567840
There's actually pretty sweet simplification to make some of the numbers more tractable... For the equation you show of the form A/(BxC), you can eval a "partial" (there might a technical term for it) factorial where you get (A/B)/C. So say for example A is 99! and B is 65!
A/B = (1x2x3x...x65x66x...x98x99)
/ (1x2x3x...x65x66)
A factorial is just a special case repeating product like a Riemann sum. Usually denoted with a capital greek PI and looks like something from stonehenge (http://en.wikipedia.org/wiki/Multiplication#Capital_pi_notation).
So n! is defined as
PI(from 1 to n)
where from the above what we want is...
PI(from 66 to 99)
then divide that by the (smaller) factorial denoted by C and you're golden.
Whoops.
The above should read
A/B = (1x2x3x...x65x66x...x98x99)
/ (1x2x3x...x65)
Nice one genius. ;-)
Post a Comment