Background
Last week Google Australia has posted about the Google Treasure Hunt 2008.
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.
First Puzzle
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.
Conclusion
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!
it’s not really fair that you’re posting your solution
I agree that it’s sad to see the solution posted. Maybe a hint, but an outright solution kind of defeats the purpose for everyone trying to do it themselves.
Thankfully I’d already figured it out in much the same manner so it didn’t spoil it for me but I feel sorry for anyone that doesn’t take the time to figure it out for themselves and instead stumbles across this.
I have included the word “solution” right in the post’s topic, so that people who really want to do it themselves won’t click!
Anyone who is searching for a solution via Google, or clicks to read this topic, he knows what to expect.
This was posted for people who would like some help with the problem, or want to discuss different solutions/approaches. There could be other solutions posted around the web.
Also I don’t think I ruined the prizes, as only the first correct answers are supposed to win something.
Anyway, more puzzles will follow during the next weeks. I am not going to post about them if that upsets some people.
Well the answer is correct but it is not explanatory.
I would suggest that start from bottom-right corner.
Right now that value at the cell(2,B) is 2. But with a bottom up approach the value at cell (2,B) would give the number of unique paths from (2,B) to (5,E)
Again I agree that, Its not fair to post a solution till the contest is over. May be google is looking for some programmers, who really deserve appreciation.
regards,
sujoy.adhikari@nechclst.in
>> … reminds of Pascal’s triangle …
It actually _IS_ Pascal’s triangle, if you rotate your spreadsheet (or your screen, or your head) 45 degrees the mysterious square/triangle mystery will dissolve. If you think more about the problem that’s being put forward, and how you create Pascal’s triangle, you should see the connection
>> Well the answer is correct but it is not explanatory.
It’s only one step away from being explanatory. The first step is to recognise the pattern, the next step is to extend the pattern it to make a predictions (or in this case, predict solution which was validated 24 hours later), and the final step is to rationalise the pattern and the extension.
My hint towards this rationalisation (in the interest of provoking more thinking) is to understand what the numbers in each cell REALLY mean – consider B1, A2 and the bottom right (target cell) B2? Then how about C1, C2, A3, B3, and the bottom right C3?
>> However for larger grids, for example 25×25, the algorithm could take infinite time.
It’s not really infinite – just a little slow on most hardware… Perhaps the next question in the treasure hunt should be: “for the naive implementation of this solution, with a 100×100 grid, what’s the order of magnitude for processing, and memory usage required to produce a correct solution?”
>> Also I don’t think I ruined the prizes, as only the first correct answers are supposed to win something.
I suspect a lot of the concern here is “there’s prizes out there and this makes it easy for other people to find the answer ahead of me” (hey, I’m the first to admit that that was my first reaction).
While this may be true at some level (yes, it does make it easier for people to cheat and get the answer without working through it if that’s what they really want to do), people also need to read things carefully. This from the solution page for the first question (note “first”):
… and the first person to answer them all correctly will win a prize …
So, if you’re relying on finding the solution posted on the interweb somewhere, you’ve already missed the boat. The person who posted it is ahead of you.
Good on you for wanting to share your process, help others, and learn more!
@Sujoy: Google has other ways to judge a programmer’s skills. You can find on the web many information about how Google finds potential employees, the interview process etc. Anyone can send a CV, but not anyone will receive a phone call.
@Martin: I really appreciate your comment, thanks a lot. That’s exactly what this post was all about.
Hey, decoding. I found the answer to the problem a few days ago, but I still can’t submit it.
Do you have msn? I’d like to talk to you about it, as there’s 1 tiny part of the problem that I can’t solve!
@Matt: Sure, I am going to add you as a contact on MSN.
A hint. Or perhaps a spoiler…
Questions like this are old chestnuts of combinatorics classes. The trick is to encode the robots journey as a sequence of directions, in this case only right and down. The problem falls out because you can know an awful lot about the possible sequences, plenty enough to characterise a way of enumerating them. (Sequence length and composition.)
None of which helps you if you can’t find a tool to compute that large a binomial. Should have remembered the spreadsheet.
Jim’s right.
Think about a smaller grid – say 5 x 5
The moves can be sequenced as follows:
DDDDRRRR
DDDRDRRR
…
etc.
In other words, the solution is how many ways you can permute 4 Ds and 4 Rs while eliminating doubles.
Then you just expand to the bigger problem of a 66 x 41 grid.
I agree with moo. The game looses all the fun if one or two clever ppl. posts solutions and then lots of dumb people submit perfect answers. Where is the competition? If you say speed: maybe some of the people are not online when the quiz is posted, and start working on it later.
My advice: even if you upload the complete solution, do it after the round is over.
According to Google: “The second puzzle will be appearing soon — to be exact, 936266827 seconds before Y2K38, so keep yer eyes open.”
Anyone tried to calculate the exact date?
If Y2K38 is 2038-01-01 00:00:00, and we subtract the above amount of seconds, the result date seems to be earlier than our current date. Tried it on both .NET and Python.
Am I missing something here?
“Am I missing something here?”
Yes, the honor code and spirit of the game. Anyone could have posted the solution to this problem which is rather easy as far as puzzles go. But we don’t because it takes the fun out of the contest for people trying to win the prize, because now other people who wouldn’t have been able to pass question 1 can get the solution here.
@Treasure: As I said before, since this post caused some mixed feelings, I am not going to post other solutions. Even this solution is not complete, since not anyone is able to write some code to get the result.
Nobody is going to lose the prize from someone who found a solution 3-4 days after the first correct submitted answers of puzzle #1 (which is supposed to be the easier one).
I’m not sure if you noticed, but if you turn your spreadsheet output on its side (so that 0 is the top of a triangle), it forms Pascal’s triangle. Though in my opinion 0 should be 1.
And hence you have your formula…
the robot has to move down 34 times, and right 60 times, so there are 94 moves to be made. Specifying the sequence of moves (DRDDR…) determines the path, and to determine that sequence you just have to specify the positions of the 34 down moves (D_DD_…)
The answer should be the number of unique ways to choose 34 things from a set of 94 things, or 94 choose 34 .
94!/(60!34!)
or
44262542670579410443898814
since presumably the sizes are different for everyone, be sure to notice that the number of moves you have to make in each direction is one less than the size.
one a 2×2 board you have 1 right move and 1 down move.
>According to Google: “The second puzzle will be appearing >soon — to be exact, 936266827 seconds before Y2K38, so >keep yer eyes open.”
>
>Anyone tried to calculate the exact date?
>
>If Y2K38 is 2038-01-01 00:00:00, and we subtract the above >amount of seconds, the result date seems to be earlier than >our current date. Tried it on both .NET and Python.
>
>Am I missing something here?
Are you counting leap years? Cause that might do it.
@blah: The date functions take care of the leap years I suppose. Like Date.Subtract in .NET. Have you tried it?
The solution can be done with dynamic programming in 6 lines in python.
Or using combinations like mentioned. We did this exact problem in discrete math.
Y2k38 is a specific day google it,
You get a time which is pretty near.
@Erek: Thanks a lot, found it! I thought it was 1/1/2038, not a specific day in 2038. The result makes sense now.
Yeah, no programming needed for this question other than possibly to find that large binomial coefficient. Next puzzle is 17:07GMT today. Think there is anything to that time?
Regarding spoilers, I don’t see much wrong with discussing solutions. A treasure hunt should be fun and participatory. Helping people through is part of it. Nothing wrong with challenging yourself and doing it on your own either, mind.
I thought the google puzzles were gonna be harder. Here is explanation of how i worked out the answer to the first question.
http://mindmeat.blogspot.com/2008/05/google-treasure-hunt-2008.html
or mirrored here:
http://pat.b22222.com/
I don’t see how posting the solution or walkthrough spoils it for everyone else. If you are googling for an answer then what the hell do you expect to find? If you really want to figure it out for ourself then you wouldn’t start at a search engine.
The solution for NxM board from one corner to the other is (N+M-2)!/(N-1)!/(M-1)!
If you need a calculator that can handle big numbers: http://jagx.pimpsofpain.com/calculator.zip has a TI-89 calculator emulator
Here’s an explanation for those that are curious.
To get from the top corner to the bottom corner, we have to go down M-1 times and go to the right N-1 times.
We can consider each path as a string of Rs and Ds, where R means move right and D means move down. We know our string will have M-1 Ds and N-1 Rs in any order. Consider how many letters that is: M-1 + N-1 = M+N-2
How many ways are there to arrange this many letters? Well assume all the letters are unique; then the answer is just (M+N-2)!
But.. we have to realize that since we dont have unique objects the answer is actually gonna be smaller.
We can solve this easily by considering a 4×4 matrix and then scaling up.
For a 3×3 matrix we could have for example: RDRD ^ ^ that R and the other R could have been switched but are still the same path Now we can just consider how many ways the Rs could have been arranged. 2! or if we scale it up… N-1! This number is simply the number of duplicates for each and EVERY path we have.
How about the Ds.. same thing M-1!
Now we divide our original result that assumed each path was unique by the number of duplicates per path.
This is simply (N+M-2)!/(N-1)!/(M-1)!
I hope this helps. Most people won’t understand but those other programmers out there who aren’t that great at math might. Cheers!!!
Formula for x by y grid: [(x+y-2)!]/[(x-1)!(y-1)!]
Looms messy, but that’s because of the “-1″ bits, caused by the fact that you have to make (x-1) moves right and (y-1) moves down. Satisfyingly, the solution for a grid x by y is the same as one for a grid y by x, as one would intuitively expect.
how’bout the second puzzle?
i guess they wanna make some test on linux bash programming but i have coded it in java and some string work. it lasts about 30 minutes.
any brilliant idea?
@istimbot: Yeah, it took me 15-20 minutes to write some .NET code for the second puzzle’s solution. I would expect something harder, or something related to some math logic again. Retrieving files from folders, and simply reading them wasn’t challenging at all. Looking forward for the third puzzle.
from path import path
filepaths = list(path(”puzzle_data”).walkfiles())
line_4_filepaths = [filepath for filepath in filepaths if "def" in filepath and filepath.endswith(".txt")]
line_5_filepaths = [filepath for filepath in filepaths if "jkl" in filepath and filepath.endswith(".rtf")]
def get_number_from_line(filepath, linenumber):
try:
return int(filepath.lines()[linenumber-1])
except IndexError:
return 0
line_4_sum = sum([get_number_from_line(filepath, 4) for filepath in line_4_filepaths])
line_5_sum = sum([get_number_from_line(filepath, 5) for filepath in line_5_filepaths])
print line_4_sum * line_5_sum
Sorry about my first comment being a bit negative. I see your point that no one who finds the solution via a Web search would prevent anyone from winning a prize. Unless there are many prizes. (Google crawl updates are pretty fast!) I think because most people found out about the treasure hunt after it had been live for a while, via the Google Blog post and at the same time right underneath is your post with the solution. That’s why people got annoyed. I agree it is fun to discuss hints and different approaches with others. I guess nobody can object to posting about it after the next puzzle goes live.
I originally came back to give an actual hint to your question about Y2K38 but it looks like someone already did.
Yeah, I thought these puzzles were going to be harder!
For puzzle 2, I wonder if there’s some super quick one-line compound Unix command that can do the trick.
@Treasure: That’s alright, thank you. Google blogs have something like automatic trackback, I really didn’t want my post to appear underneath their original post. Shortly after more solutions have been posted around the Web, even with complete source code.
>>For puzzle 2, I wonder if there’s some super quick one-line compound Unix command that can do the trick.
Good idea, any Unix experts out there?
I guess it is hard to find puzzles that do not already exist on the Web in a similar form.
puzzle 2 in bash:
e.g. all files containing zzz ending with .js 5th line:
find ./ -type f | grep zzz | grep .js$ | xargs -n 1 sed -n ‘5p’ | awk ‘{s=s+$1;} END {print s;}’
my bash approach is :
find -regex .*def.*xml|awk ‘{system(”cat -n “$0)}’|awk ‘ / 5/ {s+=$2} END{print s}’
I’m not comfortable with the system(cat ..”), I find your xarg and sed much cleaner.
but I think you can shorten your greps, isn’t it ?
mine is
$ find . -type f -regex .\*EFG.\*txt$ | while read f; do sed -n ‘5p’ < $f; done | awk ‘{ sum=sum + $1 } END { print sum }’
some explanation and java code on the 1st quiz:
http://bpgergo.blogspot.com/2008/05/binomial-robot.html
java and bash implementation of the 2nd quiz:
http://bpgergo.blogspot.com/2008/05/treasure-hunt-2.html
This Google Treasure Hunt is turning out to be a joke, look at the difficulty level of the quesitions, its been exponentially decreasing, first there was a mediocre robot problem, which involved at least some logic.
The second was a silly problem which involved some brute force search and thats it.
Google made me laugh @ the 3 rd problem, which required absolutely no help of computers(apart from getting to the website).
I would really appreciate if Google did something worthwhile with the resource they are using for GTH.
I agree. Third puzzle was ridiculously easy. (Even tho the two Cisco guys in my shop shrugged their shoulders and said, “I dunno”)
The first puzzle I remembered from Discrete Math. Plugged the numbers into Windows Calc (It works, try it).
Second puzzle, dir *.prf /s /b | find “abc”. Then eyeballed it with a43.
[...] I have missed the first three puzzles (first, second and third) but I’ll give the fourth puzzle a [...]
I happened to have solved this same problem in the past, but not for google. Here’s how I did it, in perl; now I realize the much simpler combinatorial approach. Regardless, this script runs very quickly (due to the optional caching, you may safely ignore the “cache” stuff) – so I’m happy with it.
#Usage: foo.pl
my %cache;
sub hax {
my ($x,$y) = @_;
return 1 if $x*$y==0;
if ( defined $cache{”$x,$y”} || defined $cache{”$y,$x”} ) {
return $cache{”$x,$y”};
}
if ( $x==$y ) {
$t = 2*&hax($x-1,$y);
$cache{”$x,$y”} = $t;
return $t;
}
$t = &hax($x-1,$y) + &hax($x,$y-1);
$cache{”$x,$y”} = $cache{”$y,$x”} = $t;
return $t;
}
print &hax(shift, shift)
Whoops, the parser stripped my “tags”.
# Usage: foo.pl [rows] [columns]
Wow, decoding. What a huge demographic of incredibly stupid snarky people.