Google Treasure Hunt 3: a Depth-First Search Solution
This is another Google Treasure Hunt I
solved. I know that with this one, you really doesn’t need to use any kind of
programming skills. But I guess that there would be no fun if you just use only
your mind to solve it! Try to teach your computer to make it for you… The
problem I got was the following:
“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 4.229.231.150. Which nodes does the
packet pass through on its way to the destination? (include start and final
node in your answer)”
The diagram for the given computer network can
be designated by the routing table below:
“
A 26.40.28.17 75.174.216.140
=> 126.186.188.58 26.40.28.17 => 17.100.195.84 4.229.231.0/24
=> 75.174.216.140 13.157.234.26
B 13.157.234.26 76.246.145.72 => 53.12.68.161 126.186.188.58 => 75.174.216.140 53.12.68.0/24 => 26.40.28.17 17.100.195.84
C 53.12.68.161 75.174.216.140 =>
219.88.219.35 229.23.61.42 =>
13.157.234.26 17.100.195.0/24
=> 103.19.57.145 126.186.188.58
D 103.19.57.145 86.60.122.237 => 86.60.122.237
117.146.177.141 => 53.12.68.161 229.23.61.0/24 => 219.88.219.35 212.222.1.12
E 4.229.231.150 4.229.231.150 => 103.19.57.145
54.35.7.207 => 54.35.7.207 126.186.188.0/24
=> 199.223.210.72 229.23.61.42
F 54.35.7.207 4.229.231.150 =>
229.23.61.42 13.157.234.26 =>
199.223.210.72 26.40.28.0/24 =>
4.229.231.150 86.60.122.237
G 86.60.122.237 229.23.61.42 => 54.35.7.207 13.157.234.26 => 103.19.57.145 103.19.57.0/24 => 212.222.1.12 219.88.219.35
H 212.222.1.12 126.186.188.58 =>
219.88.219.35 75.174.216.140 =>
86.60.122.237 103.19.57.0/24 =>
103.19.57.145 229.23.61.42
I 229.23.61.42 4.229.231.150 =>
4.229.231.150 117.146.177.141 =>
54.35.7.207 126.186.188.0/24 =>
199.223.210.72 212.222.1.12
J 199.223.210.72 53.12.68.161 => 229.23.61.42 4.229.231.150 => 54.35.7.207 219.88.219.0/24 => 219.88.219.35 4.229.231.150
K 219.88.219.35
4.229.231.150 =>
199.223.210.72 17.100.195.84 =>
212.222.1.12 126.186.188.0/24
=> 86.60.122.237 103.19.57.145
L 117.146.177.141
4.229.231.150 =>
219.88.219.35 117.146.177.141 =>
126.186.188.58 26.40.28.0/24 =>
76.246.145.72 75.174.216.140
M 75.174.216.140
199.223.210.72 =>
13.157.234.26 4.229.231.150 =>
117.146.177.141 126.186.188.0/24 =>
17.100.195.84 26.40.28.17
N 17.100.195.84
4.229.231.150 =>
26.40.28.17 219.88.219.35 =>
13.157.234.26 17.100.195.0/24 =>
75.174.216.140 76.246.145.72
O 76.246.145.72
4.229.231.150 =>
17.100.195.84 86.60.122.237 =>
126.186.188.58 13.157.234.0/24 =>
53.12.68.161 117.146.177.141
P 126.186.188.58
13.157.234.26 =>
53.12.68.161 4.229.231.150 =>
76.246.145.72 103.19.57.0/24 =>
26.40.28.17 117.146.177.141
”
As you may suppose, the first symbol is the
character identifying the network node, followed by its IP number. Next, you have
a sequence of 3 routing rules, where the related node can see if one of these rules can fit with the
incoming packet. The last IP number gives us the “default
route”, just in the case the network node couldn’t find any matching
rule. In this case, the packet will be forwarded through the
outgoing network card to the given host in the last column.
I proposed a solution with C++, which uses depth-first search as the method to look for a
valid path going from a given point to another in the problem network
model. My main idea is to put my depth-first search function walking node by node (labeled as A, B, C, etc.), iterating over each one
of the routing table rules, and searching for one of these rules that
can route my packet through the network. The function below is
self-explainable:
“
bool RoutingTable::routeTo(
string node, string* resp )
{
bool do_it_again = true;
RoutingEntry rentry = findRouteEntry( node );
if ( rentry.doneThis() )
return false;
resp->append( rentry.getId() );
if (
rentry.getAddress().compare(getFinalDestination()) == 0 ) {
return false;
}
vector<RoutingRule> routing_rules = rentry.getRules();
vector<RoutingRule>::iterator i;
rentry.markThis(true);
// go through each of the routing rules
for ( i = routing_rules.begin(); ( i !=
routing_rules.end() ) &&
do_it_again; i++ )
{
if ( (*i).canRoute(getFinalDestination()) )
{
do_it_again
= routeTo( (*i).getRedirection(), resp );
} // if
} // for
rentry.markThis(false);
// no rules; asks the default gateway…
if ( do_it_again )
{
do_it_again = routeTo(
rentry.getDefaultRoute().getRedirection(),
&nb
