- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
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.)
- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
It looks like our gateway not allow me to visit http://treasurehunt.appspot.com
Can you post the picture.
- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
there is a problem.
117.153.4.0/24 => 5.153.148.97
it is not correct ip address.
- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
%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
- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
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;
- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
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
- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content
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