Treasure Hunt is a geek contest, involving puzzles drawing from Computer Science and Math fields.
Every week a new puzzle will be posted, and the first winners will receive a prize.
A robot is located at the top-left corner of a (rows) x (columns) 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?
Day 1 – First attempt:
It took me about an hour to write an algorithm, which was not too complicated after all, that could successfully solve the puzzle.
The algorithm simulated every possible unique movement until the end of the path.
For small grids (like 5×5), it was taking only a few seconds to find the correct answer.
However for larger grids, for example 25×25, the algorithm could take infinite time.
Puzzle’s grid was large enough, about 60×40, and therefore it could not be solved in this manner.
Day 2 – Second attempt
As unique paths could overlap at certain points (grid cells), I tried to alter the previous algorithm, in a way to avoid following the same path again again.
I started filling-up a sample 5×5 grid on a paper by adding on each cell the sum of its adjacent left and upper cells like that:
And to my surprise, that was the answer to the problem!
The bottom-right corner of any grid is always equal to the number of the unique paths that the robot can follow.
Therefore I immediately wrote some code to simulate the filling-up of any (rows) x (columns) grid.
It was pretty easy, no more than 10-12 lines.
I run it, and the final answer was about 20-25 digits long!
No wonder why my first algorithm would never finish.
I have submitted it, and 24 hours later found that it is indeed the correct answer.
I am happy that the solution involved some math logic (grid reminds of Pascal’s triangle), and some coding of course.
I am pretty sure that the puzzle can also be solved via a mathematical formula.
If anyone knows it, please feel free to post it in the comments below.
Looking forward to the next puzzle!