Google Treasure Hunt Week 3 Problem/Solution

Google is hosting a puzzle contest called the Treasure Hunt, testing knowledge of computer science, networking, problem solving, etc. It is free and open to anybody, and there are prizes for those extraordinary people who can get all of the questions right.

Go to http://treasurehunt.appspot.com/ to see the questions and enter the contest.

Here is the networking question (week 3) http://treasurehunt.appspot.com/historic/network:

Below is a diagram of a computer network. The nodes are hosts on the network, and the lines between them are links. A packet is sent out from host P with a destination of 106.5.163.253. Which nodes does the packet pass through on its way to the destination? (include start and final node in your answer)

Here is a network routing table you'll need to determine the path taken:

Node	Ip address	Routing table entry	Routing table entry	Routing table entry	Default route
A	41.2.90.147	15.248.192.89 => 59.17.173.9	106.5.163.253 => 184.195.111.249	184.195.111.0/24 => 118.52.102.45	168.179.92.1
B	168.179.92.1	69.245.219.240 => 118.52.102.45	41.2.90.147 => 184.195.111.249	148.75.75.0/24 => 41.2.90.147	50.193.16.193
C	50.193.16.193	168.179.92.1 => 10.182.187.92	184.195.111.249 => 168.179.92.1	48.13.8.0/24 => 15.248.192.89	171.222.55.228
D	171.222.55.228	219.192.84.234 => 69.245.219.240	41.2.90.147 => 173.46.61.110	106.5.163.0/24 => 10.182.187.92	48.13.8.8
E	48.13.8.8	171.222.55.228 => 171.222.55.228	106.5.163.253 => 106.5.163.253	173.46.61.0/24 => 229.217.5.126	148.75.75.148
F	106.5.163.253	59.17.173.9 => 48.13.8.8	168.179.92.1 => 229.217.5.126	184.195.111.0/24 => 148.75.75.148	69.245.219.240
G	69.245.219.240	59.17.173.9 => 106.5.163.253	15.248.192.89 => 171.222.55.228	168.179.92.0/24 => 173.46.61.110	15.248.192.89
H	173.46.61.110	15.248.192.89 => 229.217.5.126	219.192.84.234 => 69.245.219.240	48.13.8.0/24 => 15.248.192.89	171.222.55.228
I	229.217.5.126	15.248.192.89 => 173.46.61.110	41.2.90.147 => 106.5.163.253	69.245.219.0/24 => 148.75.75.148	48.13.8.8
J	148.75.75.148	229.217.5.126 => 15.248.192.89	118.52.102.45 => 229.217.5.126	106.5.163.0/24 => 48.13.8.8	106.5.163.253
K	15.248.192.89	106.5.163.253 => 148.75.75.148	41.2.90.147 => 69.245.219.240	229.217.5.0/24 => 10.182.187.92	173.46.61.110
L	10.182.187.92	148.75.75.148 => 171.222.55.228	118.52.102.45 => 219.192.84.234	106.5.163.0/24 => 15.248.192.89	50.193.16.193
M	118.52.102.45	118.52.102.45 => 41.2.90.147	50.193.16.193 => 10.182.187.92	48.13.8.0/24 => 168.179.92.1	184.195.111.249
N	184.195.111.249	184.195.111.249 => 168.179.92.1	41.2.90.147 => 41.2.90.147	106.5.163.0/24 => 219.192.84.234	118.52.102.45
O	219.192.84.234	173.46.61.110 => 10.182.187.92	219.192.84.234 => 59.17.173.9	48.13.8.0/24 => 184.195.111.249	50.193.16.193
P	59.17.173.9	50.193.16.193 => 50.193.16.193	106.5.163.253 => 41.2.90.147	171.222.55.0/24 => 10.182.187.92	219.192.84.234

Enter the nodes the packet passes through below
(Note: Answer must start with P, end with the destination node name, and contain only node names.)

Spoiler: to see the answer, click here!

To re-hide the answer, clear your browsing history and reload this page.

All you have to do for question 3 is read the network routing table, start at the designated starting node, and under the table entries see what IP address it goes to for the destination IP address. In the above example, we start at node P, then find the routing table entry for 106.5.163.253, and there is an entry 106.5.163.253 => 41.2.90.147. This means that to get to 106.5.163.253, it will first go to 41.2.90.147, which in the table resolves to node A. Then find the entry under node A for 106.5.163.253, which is 106.5.163.253 => 184.195.111.249, and 184.195.111.249 resolves to node N, etc.

Google Treasure Hunt Week 1 Problem/Solution

Google is hosting a puzzle contest called the Treasure Hunt, testing knowledge of computer science, networking, problem solving, etc. It is free and open to anybody, and there are prizes for the first person who can get all of the questions right.

Go to http://treasurehunt.appspot.com/ to see the questions and enter the contest.

Here is the robot in a grid question (week 1) http://treasurehunt.appspot.com/historic/robot/:

A robot is located at the top-left corner of a 58 x 48 grid (marked 'Start' in the diagram below).

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 (marked 'Finish' in the diagram below).

Note: The grid below is 7x3, and is used to illustrate the problem. It is not drawn to scale.

How many possible unique paths are there?

Spoiler: to see the answer, click here.
To re-hide the answer, clear your browsing history and reload this page.


For question 2, you just have to think about the basic concepts of probability and combinatorics. Let's use the example with the 7 by 3 grid. In this case, the robot has to go 6 units to the right and 2 units down. This is a total of 6+2=8 steps the robot will end up taking. Using the counting principle/permutations, the number of ways of ordering these 8 steps is 8! (8 factorial, or 8*7*6*5*4*3*2*1). I thought about it like the permutations of this set of characters: R R R R R R D D (6 steps right and 2 steps down). But, we need to divide out the repetition here. Think of the option R R R R R R D D: this is one path the robot can take. But with 6 Rs that are all the same, it doesn't matter if we switch them around a little, like the first and last R switch places. So, we have to divide out the repetition: the number of ways of ordering all the right steps and all the down steps: this is 6!2!, so our final answer is 8!/(6!2!)=28 for the 7 by 3 grid example. I used the same method for the 58 by 48 problem.