Google Treasure Hunt - use logic to solve 3rd question
The third installment of the Google Treasure Hunt is live. I have been through the first two challenges and been successful at solving them correctly.
However, the third one seemed as if it required knowledge of networking and how routing tables work. Of course, I have no idea about these things, but I think I have managed to solve this one nevertheless (of course, I am awaiting the result on my submitted answer). Here is the reasoning I used to answer my puzzle. It was pure logic.
The questions is to find out the path a packet will take on a network of computers connected in a certain way. There is a table given that shows how each computer deals with the packets that it has to transmit. In my puzzle each computer was connected with 4 others and so this table contained 4 entries for each computer.
I noticed that these entries were made of IP addresses which were the same or similar to IP addresses of the other computers on the network. Since this was a routing table, then it must be telling me how each computer forwards the packet based on where it has to be sent.
So, I began with the starting node and simply went through the entries of that node to see where it would need to go next. If the destination address was in any of the entries, then I would simply need to go to address in the second part of that entry, else I would go to the default route entry. And I kept repeating this process till I got to the destination node.
I am fairly certain that my answer should be correct (unless I made a careless mistake while tracing the path). No need to know networking on any fancy Linux commands.
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 27th, 2008 at 11:10 pm
That’s how I answered it too. Without more information from the question, I don’t see how it could be done any other way. Nothing was said about finding optimal paths or anything like that. I suppose it could come down to needing to know some obscure fact about the way IP routing works. Like, suppose that, for some reason, when a path becomes “too long” (whatever that would mean), the sender defaults to it’s default gateway, even though it had a direct entry in its table for the destination. That’s just an “off the top of my head” example of the type of curve ball that could be contained in this, otherwise totally straight-forward (easy!), question. They did say it would the treasure hunt would test trivial knowledge.
May 27th, 2008 at 11:13 pm
@Spotcat… well, if there is a curveball, we will get to know about it when we receive a result on the answer.
However, going through default routes only in my question was running me in circles, so, I think this should have been it.
May 28th, 2008 at 1:27 am
Yup..I did the same way too.
May 28th, 2008 at 5:17 am
I like your term, “fancy Linux commands”
May 28th, 2008 at 2:02 pm
I had to check the subnet calculator near the end nodes (cheat?), that was tricky… Except if i missed something on the first nodes X_X
May 28th, 2008 at 3:18 pm
@Godie… nopes, no cheat… although i didn’t use the subnet calculator, but I think in my case, most IPs were /24 (which meant that I didn’t have to take the default route)… not sure if that made sense…
May 28th, 2008 at 3:22 pm
Like you, I’m not into networking, but I figured out how it should be done, and consulted about those /24s with Wikipedia.
Then, this is the point where I erred:
I did a quick regex replace to convert the table into Java code loading the table in an array, programmed a recursive solution, got the result, and submitted it. But this took me about forty minutes!
Only then did I realise that with so many little nodes, I could have reasoned from the start that it would have been much faster to compute manually.
Grrrrrrr!
May 28th, 2008 at 4:47 pm
@dwardu… i identify with your pain. sometime you have to step back and look for a simpler way out. i did the same in the first puzzle, where i thought i will brute force the solution. turned out that i would never have got there, then i tried some finesses and it worked.
May 28th, 2008 at 5:34 pm
@Vaibhav… good, at least I’m not alone
May 29th, 2008 at 9:21 am
Yup… got it correct (the second time.. must have made a silly mistake the first time around)….
June 2nd, 2008 at 10:25 am
Thanks for this. It helped me in working out my solution (http://thebigbyte.blogspot.com/2008/06/how-to-solve-third-question-google.html). I’m looking forward to the next question!
Cheers,
David