DATA Step, Macro, Functions and more

Google Treasure Hunt - Question 2

Reply
Trusted Advisor
Posts: 1,300

Google Treasure Hunt - Question 2

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)

Network

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

NodeIp addressRouting table entryRouting table entryRouting table entryDefault route
A224.216.69.120134.24.6.169 => 134.24.6.16922.230.113.114 => 89.88.225.2427.86.78.0/24 => 22.230.113.114190.64.129.17
B89.88.225.24289.88.225.242 => 5.153.148.97190.64.129.17 => 224.216.69.12085.113.64.0/24 => 22.230.113.114134.24.6.169
C5.153.148.97190.64.129.17 => 89.86.234.208116.134.182.91 => 190.64.129.1784.104.233.0/24 => 117.153.4.23889.88.225.242
D89.86.234.20885.250.166.178 => 116.134.182.9189.88.225.242 => 84.104.233.40117.153.4.0/24 => 45.87.155.1285.113.64.65
E84.104.233.407.86.78.45 => 7.86.78.45116.134.182.91 => 85.250.166.178134.24.6.0/24 => 89.86.234.2089.140.95.24
F85.250.166.1789.140.95.24 => 9.140.95.24117.153.4.238 => 7.86.78.45134.24.6.0/24 => 84.104.233.4045.87.155.12
G45.87.155.1289.88.225.242 => 116.134.182.91117.153.4.238 => 85.250.166.178116.134.182.0/24 => 117.153.4.23889.86.234.208
H116.134.182.91117.153.4.238 => 7.86.78.4589.86.234.208 => 45.87.155.12244.102.114.0/24 => 117.153.4.23889.86.234.208
I7.86.78.45117.153.4.238 => 9.140.95.24190.64.129.17 => 84.104.233.40224.216.69.0/24 => 85.250.166.178116.134.182.91
J9.140.95.24134.24.6.169 => 85.250.166.17822.230.113.114 => 7.86.78.45117.153.4.0/24 => 117.153.4.23884.104.233.40
K117.153.4.238190.64.129.17 => 5.153.148.9722.230.113.114 => 89.86.234.208117.153.4.0/24 => 85.113.64.6545.87.155.12
L85.113.64.6584.104.233.40 => 134.24.6.169134.24.6.169 => 5.153.148.9789.88.225.0/24 => 117.153.4.23889.86.234.208
M134.24.6.16922.230.113.114 => 89.88.225.242244.102.114.233 => 224.216.69.120116.134.182.0/24 => 22.230.113.11485.113.64.65
N22.230.113.11484.104.233.40 => 134.24.6.169244.102.114.233 => 224.216.69.12085.113.64.0/24 => 244.102.114.23389.88.225.242
O244.102.114.233224.216.69.120 => 5.153.148.9784.104.233.40 => 85.113.64.65117.153.4.0/24 => 22.230.113.114190.64.129.17
P190.64.129.179.140.95.24 => 244.102.114.23322.230.113.114 => 224.216.69.120117.153.4.0/24 => 5.153.148.9785.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.)


network.png
Super User
Posts: 9,687

Google Treasure Hunt - Question 2

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

Can you post the picture.

Network

Super User
Posts: 9,687

Google Treasure Hunt - Question 2

there is a problem.

117.153.4.0/24 => 5.153.148.97

it is not correct ip address.

Trusted Advisor
Posts: 1,300

Google Treasure Hunt - Question 2

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

Trusted Advisor
Posts: 1,300

Google Treasure Hunt - Question 2

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)

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

O244.102.114.233224.216.69.120 => 5.153.148.9784.104.233.40 => 85.113.64.65117.153.4.0/24 => 22.230.113.114190.64.129.17

o-22.230.113.114(n)

N22.230.113.11484.104.233.40 => 134.24.6.169244.102.114.233 => 224.216.69.12085.113.64.0/24 => 244.102.114.23389.88.225.242

n-89.88.225.242(b)

B89.88.225.24289.88.225.242 => 5.153.148.97190.64.129.17 => 224.216.69.12085.113.64.0/24 => 22.230.113.114134.24.6.169

b-134.24.6.169(m)

M134.24.6.16922.230.113.114 => 89.88.225.242244.102.114.233 => 224.216.69.120116.134.182.0/24 => 22.230.113.11485.113.64.65

m-85.113.64.65(l)

L85.113.64.6584.104.233.40 => 134.24.6.169134.24.6.169 => 5.153.148.9789.88.225.0/24 => 117.153.4.23889.86.234.208

l-89.86.234.208(d)

D89.86.234.20885.250.166.178 => 116.134.182.9189.88.225.242 => 84.104.233.40117.153.4.0/24 => 45.87.155.1285.113.64.65

d-45.87.155.12(g)

G45.87.155.1289.88.225.242 => 116.134.182.91117.153.4.238 => 85.250.166.178116.134.182.0/24 => 117.153.4.23889.86.234.208

g-85.250.166.178(f)

F85.250.166.1789.140.95.24 => 9.140.95.24117.153.4.238 => 7.86.78.45134.24.6.0/24 => 84.104.233.4045.87.155.12

f-7.86.78.45(i)

I7.86.78.45117.153.4.238 => 9.140.95.24190.64.129.17 => 84.104.233.40224.216.69.0/24 => 85.250.166.178116.134.182.91

i-9.140.95.24(j)

J9.140.95.24134.24.6.169 => 85.250.166.17822.230.113.114 => 7.86.78.45117.153.4.0/24 => 117.153.4.23884.104.233.40

j-117.153.4.238(k)... done!

ONBMLDGFIJK

Trusted Advisor
Posts: 1,300

Re: Google Treasure Hunt - Question 2

%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

Super User
Posts: 9,687

Re: Google Treasure Hunt - Question 2

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

Respected Advisor
Posts: 4,654

Re: Google Treasure Hunt - Question 2

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;

PG
Super User
Posts: 9,687

Re: Google Treasure Hunt - Question 2

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

Respected Advisor
Posts: 4,654

Re: Google Treasure Hunt - Question 2

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

PG
Respected Advisor
Posts: 4,654

Re: Google Treasure Hunt - Question 2

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

PG
Ask a Question
Discussion stats
  • 10 replies
  • 552 views
  • 0 likes
  • 3 in conversation