BookmarkSubscribeRSS Feed
FriedEgg
SAS Employee

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
10 REPLIES 10
Ksharp
Super User

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

Can you post the picture.

Network

Ksharp
Super User

there is a problem.

117.153.4.0/24 => 5.153.148.97

it is not correct ip address.

FriedEgg
SAS Employee

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
SAS Employee

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

FriedEgg
SAS Employee

%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
Super User

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
Opal | Level 21

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
Ksharp
Super User

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
Opal | Level 21

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
PGStats
Opal | Level 21

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

sas-innovate-2024.png

Join us for SAS Innovate April 16-19 at the Aria in Las Vegas. Bring the team and save big with our group pricing for a limited time only.

Pre-conference courses and tutorials are filling up fast and are always a sellout. Register today to reserve your seat.

 

Register now!

How to Concatenate Values

Learn how use the CAT functions in SAS to join values from multiple variables into a single value.

Find more tutorials on the SAS Users YouTube channel.

Click image to register for webinarClick image to register for webinar

Classroom Training Available!

Select SAS Training centers are offering in-person courses. View upcoming courses for:

View all other training opportunities.

Discussion stats
  • 10 replies
  • 1410 views
  • 0 likes
  • 3 in conversation