Google Treasure Hunt - No solutions here, only hints
Google is holding a treasure hunt and I took a look and decided to give it a shot. I probably won’t make it all the way through, because I don’t have any low-level Linux knowledge (since low-level Linux trivia will be part of the treasure hunt). But the rest is fun.
So, begins the quest by a fun first question which talks about a robot and his quests through a grid. For some reason, the dumb robot wants to know all possible ways to reach from the upper left of the grid to the lower right of the grid. Being a programmer, my first impulse was to write a program that calculates the number of paths, and that didn’t take long. And here in lies the first hint of this puzzle:
Hint 1: Robot Puzzle: DO NOT use a computer program to do this. Even though you may get the algorithm right, it will take you millions of years to calculate 
the number of paths for anything larger than trivial sizes of this grid (of course, your computer will probably run out of memory first). You can try and optimize your algorithms of course. However, I resorted to simple maths and an excel sheet.
The problem is that the answers I am coming up with (and I am sure they are correct) are being rated as incorrect by Google. I think this may be due to a silly mistake I am making somewhere.
Hint 2: The File Sum and Multiplication Problem: This one was straight forward code, which took about 5 minutes to write. Remember, those who plan to do this manually (for any reason), you won’t see line breaks in notepad.
I have submitted the answer for this one, but am awaiting whether this is correct or not. Let’s see.
You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.
May 20th, 2008 at 7:18 pm
Okay, got it. The reason for why I was getting an incorrect answer for Number 1 is because Excel can’t handle precision to that extent.
Back to the programming board…
May 20th, 2008 at 7:51 pm
Rethink your programmatic solution. This problem can be solved without destroying your computer & memory.
May 20th, 2008 at 9:51 pm
@C, yup… working on it…
May 20th, 2008 at 10:59 pm
Well, got both of them correct… 2 of 2… yeah
May 20th, 2008 at 11:00 pm
i also started with excel but found out it only handles 15 digits of precision. There is a piece of software called xlprecision that is a excel plugin that is supposed to give you many more digits but it is not available for mac.
I opted to write a ruby program. Very straight forward, memory was no problem.
May 20th, 2008 at 11:24 pm
[...] recent attempts at playing the Google Treasure Hunt found me looking for ways to work with very large numbers. My solution to the first puzzle was [...]
May 20th, 2008 at 11:25 pm
@Ryan, yup… I wrote a program finally…
May 21st, 2008 at 4:48 am
The first one can be solved in one line of copious Haskell
May 27th, 2008 at 10:57 pm
[...] third installment of the Google Treasure Hunt is live. I have been through the first two challenges and been successful at solving them [...]
June 6th, 2008 at 2:13 pm
private static BigInteger linearRobot(int w, int h){
BigDecimal num= BigDecimal.ONE;
for(int i=1;i<h;i++){
num=num.divide(BigDecimal.valueOf(i), 10, BigDecimal.ROUND_HALF_UP).multiply(BigDecimal.valueOf(i+w-1));
}
return num.toBigInteger();
}
June 13th, 2008 at 8:40 pm
man bc for the robot question (unless you’re not fortunate enough to have unix/linux box handy).
“bc(1)
NAME
bc - An arbitrary precision calculator language
…”
Think factorial. Beware the fencepost.
I’ve got three confirmed and I’m cranking on the primes (last?) one in my free time. Maybe I’m missing something, but my first attack is a bit brute force. I did catch that it could be a (sort of) m+n prob instead of m*n.
Somehow my solution (if I can call it that, I don’t yet have an answer) doesn’t feel elegant yet.
June 14th, 2008 at 4:32 pm
I too am on the primes problem. I am still to start on it (no free time) and yes, I am also looking at brute force…