Monday, 2 June 2008

How to Solve the Third Question - Google Treasure Hunt 2008

This third question had me slightly confused. As I had no knowledge of network theory, it seemed at first too big a problem. But then, when I Googled the solution, I found that others felt the same way. And really, you don't need great network knowledge to solve this problem. All you need to solve the third problem in the Google Treasure Hunt 2008 is common sense and the ability to follow instructions.

Firstly, a bit about how network routing works.

Third Question:
  • 1- Start at node S
  • 2- First, add the current network node to the path. If D is the current network node the algorithm outputs the path and ends since the packet was just delivered to D. Otherwise advance to the next step.
  • 3- Iterate each routing table entry:
  • 4- D matches the Nth entry's network? Set the current node as the Nth entry's target gateway and Jump to step 2
  • 5- D does *not* match any of the routing table entries? Set the current node as the current default gateway and Jump to step 2
So what does this actually mean? Basically, given the starting node, look for the destination IP address in the three Routing Table Entries. If it's there, follow on to the IP address specified in that table entry. Otherwise, follow on to the default gateway. Repeat this process until you come to the destination node. It's that simple!

This doesn't even need a program to calculate it. I performed these operations by hand, and it only took about 10 minutes. I'm still waiting on the answer, but I'm fairly confident that it's correct. If you want a spoiler for the default question, click here. The next question's coming out June 3rd (tomorrow) so you'd better hurry if you want to answer this!

By the way, if you're puzzling over those "/24"s, check out Route summarization on Wikipedia.

The Treasure hunt has been a great opportunity so far for the geeks of the world to get creative with some problem solving. I've enjoyed it, as I'm sure many others have. Hopefully Google will continue to promote these "fun" activites, as they get the developer community active and give Google a good image in so far as community involvement goes. Thanks Google!

Update: My answer was correct! :D