Google Treasure Hunt 2008 Robot Maze
All images and questions from Google Treasure Hunt 2008.
Question:
A robot is located at the top-left corner of a 58 x 64 grid (marked).
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 (marked ‘Finish’).
How many possible unique paths are there?
The image is not drawn to scale. For illustration purposes only.
Solution
Since I love PHP, I will be attempting the solve the problem in PHP.
Here’s how I am gonna do it.
Since it is a 58×64 grid, to reach the 1,1 location the robot needs to go down 57 times and go to the right 63 times yielding a total of exactly 120 steps to reach its location.
So the rule is:
Number of times to go down = Y coordinate origin of robot – 1 = numdown
Number of times to go right = X coordinate origin of robot – 1 = numright
Number of steps to reach location = Number of times to go down + Number of times to go right = maxnum
The Plan
Generate
Generate strings maxnum length using two characters of my own choice which will be 0 and 1. 0 will represent movement to the right while 1 will be movement downwards.
I will generate the strings 0000…001, 0000…010 to 1111…111. All must be of length maxnum or in my case 120.
Screening
On the course of generation, one conditional with two arguments will be made.
These are, if the number of 0s and 1s in the string being generated exceed the number of allowable 0s and 1s (numright and numdown), then throw the string and proceed to the other.
Increment the Counter
If it passes the screening, then increment the counter. After the generation of possible combinations, echo or print the number in the counter. The number represents the number of possible movements.
Optimization
The code to be used could be optimized by:
- screening should be done every after generation of a complete maxnum length string instead of screening the string while generating it character-by-character.
My head is already aching! Waaaa, I wanna solve it during the week. I won’t stop until I solve this. Amf!!
Try to play it here.



Conrad Miguel E. Gozalo is a 17-year old guy from General Santos City, Philippines. He is currently taking up his BS Computer Science at the University of the Philippines Diliman. He is a proud Linux user since August 2008. He is also a big fan of Free and Open Source Software. Know more about him on the 

6 Responses to “Google Treasure Hunt 2008 Robot Maze” (join them?)
May 26, 2008 at 3:37 pm
ok na yung laptop
andito me now.. buy mo na to.. nyok
Jehzeel Laurente’s last blog post..My New Business Card
May 26, 2008 at 3:41 pm
@Jehz-ebel:
Yey, you’re there!!
May 26, 2008 at 5:21 pm
The answer is (58! + 64!) / (58 * 64).
Fitz’s last blog post..Creating Tech Marvels Out Of A $40 Wii Remote
May 26, 2008 at 8:15 pm
@Fitz – i think it was not just the sum of two factorials divided by the product of two factorials.. hmmmmmmm…
Jehzeel Laurente’s last blog post..My New Business Card
May 28, 2008 at 5:12 am
@Jehz
I know. Was just playing around with formulas. Pero aminin, napa-isip ka noh? Hehe.
Fitz’s last blog post..The Million Pesos Calculator
June 2, 2008 at 10:39 pm
I know what the answer is in factorial form, but I can’t figure out how to get the exact value of the 40+ digit number. Any ideas?
Leave a reply!