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.