I recently stumbled across the Google Treasure Hunt - a puzzle contest designed to test problem-solving skills in computer science, networking, and low-level UNIX trivia.
I got my first question generated for me;
You are at the top left of 66x46 grid. You can move one position down or right at any time (ie: from {0,0} to {0,1} or to {1,0}. How many possible unique paths are there for you to reach the bottom right of the grid?
After half an hour or so, I had a brute force general solution for this, involving lots of iterations, lots of checking against previous results and lots of random numbers. It worked, and was accurate up to a grid of dimensions 8,8 (3432 solutions or so), at a speed of 1000 nodes/second.
Not really ideal.
I emailed the problem to a couple of maths lovers, and then continued trying to do things the computer science way. I've now got a lovely recursive algorithm to solve the problem - and it only takes up 11 lines of code! It can count at 1million results (not nodes) a second, and I've been trying to run it on the 66,46 grid ever since I wrote it.
The first time I managed to get an Int32 Overflow, as the answer's apparently over 4.3billion. The second time (with Int64 firmly in place - let's hope the answer's not bigger than 16,000,000,000,000,000,000) the counter reached about 6.5billion before Microsoft IT Corporate Policy decided my machine needed to be rebooted. The problem with a sexy 11 lines of code is that there's not really much saving of state to be had on reboot.
It's running away again now (205 million and counting), but that doesn't actually matter, because apparently Google decide to generate a new question every time you log in to the Google Challenge, and so I don't actually have the opportunity to answer this one! Instead I now have to mess around with filesystems...
Screw Google :(
Tuesday, 20 May 2008
Screw Google
Subscribe to:
Post Comments (Atom)
Hello, world!
Leave a comment, or read the 6 comments so far.
You can solve it much easier with combinatorics.
The solution is:
(x + y - 2)! / ((x - 1)! * (y - 1)!)
:)
Everyone's a mathematician eh? ;) Well, Google said it was a computing challenge, not maths :p
Here's the other mathsy answer I got from a fried:
(n+m-2)C(m)
So, for a 65x65 grid: (65+65 - 2)!/65!
Hi Ina!
I'm a Google engineer involved with creating the Treasure Hunt! Just wanted to make sure that you noticed that we are in fact still accepting entries for the first question, as well as the new second question!
You can find the current live question at:
http://treasurehunt.appspot.com/
And you can find the first question
at: http://treasurehunt.appspot.com/historic/robot/
(There is a small link on the main page, but it's easy to overlook, I guess!) Best wishes, and good luck with the Treasure Hunt! :)
The "mathematical" method is certainly concise, but computing factorials is not the most efficient way.
Since the number of paths available to each node is simply the sum of the number of paths available to its two downhill neighbors, we can just make a grid, put a "1" in the bottom-right corner, and work backwards through the squares adding the number below to the number to the right.
Of course a computational solution only needs to remember the previous row, not the whole grid. The following is in Ruby, but could be converted to your language of choice:
def robot(x,y)
row = Array.new(x,1)
(y-1).times do
(1..x-1).each do |i|
row[i] += row[i-1]
end
end
return row[x-1]
end
puts robot(66,46)
Whoops, I might have reconsidered this post title if I remembered it would appear on the backlinks part of the Google Blog post ;)
Thanks for the help Eric. I'll put my entry in shortly!
Jonathan, your solution's pretty close to what I eventually came up with - in C# of all things.
Jonathan,
I came up with the exact same solution using Python. It can calculate the result to a 2000x2000 maze in less than 9 seconds (on my amd64 Python), the result being a 1202 digit long number. Still, the mathematical method seems to be even faster. I'll try and code it to see what happens :) Perhaps it can be done even faster in C/C++ using GMP...
Anyway, Ina, nice post here :) If anyone's interested in my approach:
http://aatiis.blogspot.com/2008/05/google-treasure-hunt-python-approach.html
Post a Comment