Google Treasure Hunt - Question 2

[FriedEgg]

Hi,

Here is a new challenge from the google treasure hunt 2008.  http://treasurehunt.appspot.com

I found the first question rather entertaining if not a little troublesome. http://communities.sas.com/thread/31422?tstart=0

Question

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 O with a destination of 117.153.4.238. 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	224.216.69.120	134.24.6.169 => 134.24.6.169	22.230.113.114 => 89.88.225.242	7.86.78.0/24 => 22.230.113.114	190.64.129.17
B	89.88.225.242	89.88.225.242 => 5.153.148.97	190.64.129.17 => 224.216.69.120	85.113.64.0/24 => 22.230.113.114	134.24.6.169
C	5.153.148.97	190.64.129.17 => 89.86.234.208	116.134.182.91 => 190.64.129.17	84.104.233.0/24 => 117.153.4.238	89.88.225.242
D	89.86.234.208	85.250.166.178 => 116.134.182.91	89.88.225.242 => 84.104.233.40	117.153.4.0/24 => 45.87.155.12	85.113.64.65
E	84.104.233.40	7.86.78.45 => 7.86.78.45	116.134.182.91 => 85.250.166.178	134.24.6.0/24 => 89.86.234.208	9.140.95.24
F	85.250.166.178	9.140.95.24 => 9.140.95.24	117.153.4.238 => 7.86.78.45	134.24.6.0/24 => 84.104.233.40	45.87.155.12
G	45.87.155.12	89.88.225.242 => 116.134.182.91	117.153.4.238 => 85.250.166.178	116.134.182.0/24 => 117.153.4.238	89.86.234.208
H	116.134.182.91	117.153.4.238 => 7.86.78.45	89.86.234.208 => 45.87.155.12	244.102.114.0/24 => 117.153.4.238	89.86.234.208
I	7.86.78.45	117.153.4.238 => 9.140.95.24	190.64.129.17 => 84.104.233.40	224.216.69.0/24 => 85.250.166.178	116.134.182.91
J	9.140.95.24	134.24.6.169 => 85.250.166.178	22.230.113.114 => 7.86.78.45	117.153.4.0/24 => 117.153.4.238	84.104.233.40
K	117.153.4.238	190.64.129.17 => 5.153.148.97	22.230.113.114 => 89.86.234.208	117.153.4.0/24 => 85.113.64.65	45.87.155.12
L	85.113.64.65	84.104.233.40 => 134.24.6.169	134.24.6.169 => 5.153.148.97	89.88.225.0/24 => 117.153.4.238	89.86.234.208
M	134.24.6.169	22.230.113.114 => 89.88.225.242	244.102.114.233 => 224.216.69.120	116.134.182.0/24 => 22.230.113.114	85.113.64.65
N	22.230.113.114	84.104.233.40 => 134.24.6.169	244.102.114.233 => 224.216.69.120	85.113.64.0/24 => 244.102.114.233	89.88.225.242
O	244.102.114.233	224.216.69.120 => 5.153.148.97	84.104.233.40 => 85.113.64.65	117.153.4.0/24 => 22.230.113.114	190.64.129.17
P	190.64.129.17	9.140.95.24 => 244.102.114.233	22.230.113.114 => 224.216.69.120	117.153.4.0/24 => 5.153.148.97	85.113.64.65

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

[Ksharp]

It looks like our gateway not allow me to visit http://treasurehunt.appspot.com

Can you post the picture.

[Ksharp]

there is a problem.

117.153.4.0/24 => 5.153.148.97

it is not correct ip address.

[FriedEgg]

These are valid.  Look into route summarization.  It is the combination of IP Address and subnet mask.

For example

117.153.4.0/24 is the ip address 117.153.4.0 with the subnet mask 255.255.255.0

[FriedEgg]

This is a fairly simple logic puzzle.  You can easily solve by hand, once you understand the /24 piece.  Basically is similar to saying 117.153.4.* (where star is a catch all from 0-255)

O => 117.153.4.238(j)

============================================================================================================================================================

O	244.102.114.233	224.216.69.120 => 5.153.148.97	84.104.233.40 => 85.113.64.65	117.153.4.0/24 => 22.230.113.114	190.64.129.17

o-22.230.113.114(n)

N

22.230.113.114

84.104.233.40 => 134.24.6.169

244.102.114.233 => 224.216.69.120

85.113.64.0/24 => 244.102.114.233

89.88.225.242

n-89.88.225.242(b)

B

89.88.225.242

89.88.225.242 => 5.153.148.97

190.64.129.17 => 224.216.69.120

85.113.64.0/24 => 22.230.113.114

134.24.6.169

b-134.24.6.169(m)

M	134.24.6.169	22.230.113.114 => 89.88.225.242	244.102.114.233 => 224.216.69.120	116.134.182.0/24 => 22.230.113.114	85.113.64.65

m-85.113.64.65(l)

L	85.113.64.65	84.104.233.40 => 134.24.6.169	134.24.6.169 => 5.153.148.97	89.88.225.0/24 => 117.153.4.238	89.86.234.208

l-89.86.234.208(d)

D

89.86.234.208

85.250.166.178 => 116.134.182.91

89.88.225.242 => 84.104.233.40

117.153.4.0/24 => 45.87.155.12

85.113.64.65

d-45.87.155.12(g)

G	45.87.155.12	89.88.225.242 => 116.134.182.91	117.153.4.238 => 85.250.166.178	116.134.182.0/24 => 117.153.4.238	89.86.234.208

g-85.250.166.178(f)

F	85.250.166.178	9.140.95.24 => 9.140.95.24	117.153.4.238 => 7.86.78.45	134.24.6.0/24 => 84.104.233.40	45.87.155.12

f-7.86.78.45(i)

I

7.86.78.45

117.153.4.238 => 9.140.95.24

190.64.129.17 => 84.104.233.40

224.216.69.0/24 => 85.250.166.178

116.134.182.91

i-9.140.95.24(j)

J

9.140.95.24

134.24.6.169 => 85.250.166.178

22.230.113.114 => 7.86.78.45

117.153.4.0/24 => 117.153.4.238

84.104.233.40

j-117.153.4.238(k)... done!

ONBMLDGFIJK

[FriedEgg]

%let start=O;
%let destination=117.153.4.238;
data route_map;
 infile '/nas/sasbox/users/mkastin/gth2008.txt' dsd dlm='~' truncover;
 input @;
  _infile_=prxchange('s/          | => /~/',-1,_infile_);
 input @1 n :$1 (ip dest1 goto1 dest2 goto2 dest3 goto3 goto4) (:$40.);
  if ip="&destination" then call symput('dest',n);
  call symput(n,put(_n_,best.));
  call symput('ip' || compress(strip(ip),'.'),put(_n_,best.));
run;
data _null_;
 length route $40;
 retain route ' ';
 obsnum=symget("&start")*1;
 do until(obsnum=symget('ip' || compress(strip("&destination"),'.')));
  set route_map point=obsnum;
  route=cats(of route n);
  array dest[3]; array goto[4]; 
  j=0; i=1;
  do until(j>0);
   if i>3 then j=4;
   else if dest="&destination" then j=i;
   else if index(dest,'/') then
    if prxmatch('/' || strip(substr(prxchange('s/\./\\./',3,dest),1,length(strip(dest))-4)) || '/',"&destination") then j=i;
   i+1;
  end;
  obsnum=symget('ip' || compress(strip(goto),'.'));
 end;
 route=cats(route,"&dest");
 put 'SOLUTION FOUND: ' route;
 stop;
run;

SOLUTION FOUND: ONBMLDGFIJK

[Ksharp]

OK. I have another varying version of this treasure.

The following is a map which illustrate from which note to which note.

E.X For  obs 2 is A => F.

I want find all the path of O => K.

not only the shortest path.

I give the path I find and the code.

How can you get that?

_start     _end
A     C
A     F
B     C
B     E
B     H
B     K
D     G
E     K
E     L
E     M
F     H
H     F
H     K
H     N
H     P
I     I
I     N
J     J
J     O
K     C
K     F
K     G
K     I
K     J
K     K
K     L
K     N
L     N
L     O
M     C
M     D
M     E
M     F
M     M
N     A
N     B
N     D
N     I
O     A
O     K
P     A
P     C
P     D
P     E






ALL PATH:

OAFHK
OAFHNBEK
OAFHNBK
OAFHPEK
OAFHPELNBK
OK




data temp;
infile datalines expandtabs;
input _start $ _end $;
flag+1;
datalines;
A     C
A     F
B     C
B     E
B     H
B     K
D     G
E     K
E     L
E     M
F     H
H     F
H     K
H     N
H     P
I     I
I     N
J     J
J     O
K     C
K     F
K     G
K     I
K     J
K     K
K     L
K     N
L     N
L     O
M     C
M     D
M     E
M     F
M     M
N     A
N     B
N     D
N     I
O     A
O     K
P     A
P     C
P     D
P     E
;
run;
proc sort data=temp nodupkey;
 by _start _end;
run;
data want;
 if 0 then set temp;
 declare hash ha(hashexp:10,dataset:'temp');
 declare hiter hi('ha');
  ha.definekey('flag');
  ha.definedata('_start','_end');
  ha.definedone();
length path _path $ 800;
 declare hash pa(ordered:'Y');
 declare hiter h_p('pa');
  pa.definekey('count');
  pa.definedata('path');
  pa.definedone();

set temp(where=(_start='O'));
 count=0;path=_start;pa.add();

do while(h_p.next()=0);
   _path=path; found=0;
   do while(hi.next()=0);
    path=_path;
    if substr(left(reverse(path)),1,1) eq strip(_start) and not find(path,strip(_end)) then do;
             count+1;path=cats(path,_end);
                           pa.add();found=1;
                                                             end;
   end;
   if not found and find(path,'K') then output;
end;
run;
data path(keep=want_path);
 set want(keep=path);
 want_path=substr(path,1,find(path,'K'));
run;
proc sort data=path nodupkey;
 by want_path;
run;

Ksharp

[PGStats]

Another way to have fun, with SQL joins...

data arcs;
input _start : $1. _end : $1.;
datalines;
A     C
A     F
B     C
B     E
B     H
B     K
D     G
E     K
E     L
E     M
F     H
H     F
H     K
H     N
H     P
I     I
I     N
J     J
J     O
K     C
K     F
K     G
K     I
K     J
K     K
K     L
K     N
L     N
L     O
M     C
M     D
M     E
M     F
M     M
N     A
N     B
N     D
N     I
O     A
O     K
P     A
P     C
P     D
P     E
;

%macro test(arcs,s,e);
proc sql;
create table _t0 as select cats(_start, _end) as path length=2 from &arcs where _start = "&s";
%let tTables=_t0;
%let i=0;
%do %until(&SQLOBS=0);
create table _t%eval(&i+1) as
select cats(path,_end) as path length=%eval(&i+3)
from _t&i inner join arcs
on char(path,%eval(&i+2))=_start and findc(path,_end)=0 
where char(path,%eval(&i+2)) ne "&e";
%let tTables=&tTables,_t%eval(&i+1);
%let i=%eval(&i+1);
%end;
quit;

data want; length path $32; set _t:; if findc(path,"&e")>0; run;

proc sql; drop table &tTables ; quit;
%mend;

%test(arcs,O,K);

proc print data=want; run;

[Ksharp]

Hello PG.

I don't think SQL is a good tool to handle such problem ,especially when you have lots and lots of branches to search.

By the way, Did you figure out a solution for searching a Hamilton Path which posted by FriedEgg a couple of days ago ? I am still fighting for it.

Ksharp

[PGStats]

Hi Ksharp, I was tempted to try solving the "Datacenter Cooling" problem. But in thinking about it I concluded that this was an intrinsically difficult problem (this was later confirmed by FriedEgg). If I still had an efficient compiler on my machine I would try it. I would love to try solving that problem with object programming (c++, java, c#). But with SAS? No fun.

PG

[PGStats]

On first try, prove it can be done; on second try, do it properly (simpler, cleaner, named nodes) :

data arcs;
input _start : $ _end : $;
datalines;
A     C
A     F
B     C
B     E
B     H
B     KS
D     G
E     KS
E     L
E     M
F     H
H     F
H     KS
H     N
H     PG
I     I
I     N
J     J
J     O
KS     C
KS     F
KS     G
KS     I
KS     J
KS     KS
KS     L
KS     N
L     N
L     O
M     C
M     D
M     E
M     F
M     M
N     A
N     B
N     D
N     I
O     A
O     KS
PG     A
PG     C
PG     D
PG     E
;

%macro test(arcs,s,e);
proc sql NOWARNRECURS NOPRINT;
create table _a as select * from &arcs where _start ne "&e" and _start ne _end;
create table _t0 as select _start as nodes, _end from _a where _start = "&s";
%do %until(&endCount=0);
create table _t0 as select catx("^",nodes,_t0._end) as nodes, _a._end
from _t0 left join _a on _t0._end=_a._start and findw(nodes,_a._end,"^","T")=0;
select count(_end) into :endCount from _t0;
%end;
create table want as
select tranwrd(nodes,"^"," - ") as path from _t0 where findw(nodes,"&e","^","T") > 0;
drop table _a, _t0;
quit;
%mend;

%test(arcs,O,KS);

proc print data=want; run;

PG