cancel
Turn on suggestions
Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.
Showing results for 
Search instead for 
Did you mean: 
BookmarkSubscribeRSS Feed
FriedEgg
SAS Employee FriedEgg
SAS Employee

Google Treasure Hunt - Question 2

Posted 10-12-2011 07:07 PM (3155 views)

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

Google Treasure Hunt - Question 2

Posted 10-13-2011 02:38 AM (2820 views)  |   In reply to FriedEgg

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

Can you post the picture.

Network

0 Likes
Reply
Ksharp
Super User Ksharp
Super User

Google Treasure Hunt - Question 2

Posted 10-13-2011 04:16 AM (2820 views)  |   In reply to FriedEgg

there is a problem.

117.153.4.0/24 => 5.153.148.97

it is not correct ip address.

0 Likes
Reply
FriedEgg
SAS Employee FriedEgg
SAS Employee

Google Treasure Hunt - Question 2

Posted 10-13-2011 10:19 AM (2820 views)  |   In reply to Ksharp

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

0 Likes
Reply
FriedEgg
SAS Employee FriedEgg
SAS Employee

Google Treasure Hunt - Question 2

Posted 10-13-2011 01:05 PM (2820 views)  |   In reply to 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)

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

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

0 Likes
Reply
FriedEgg
SAS Employee FriedEgg
SAS Employee

Re: Google Treasure Hunt - Question 2

Posted 10-13-2011 03:38 PM (2820 views)  |   In reply to 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
0 Likes
Reply
Ksharp
Super User Ksharp
Super User

Re: Google Treasure Hunt - Question 2

Posted 10-14-2011 06:30 AM (2820 views)  |   In reply to FriedEgg

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

0 Likes
Reply
PGStats
Opal | Level 21 PGStats
Opal | Level 21

Re: Google Treasure Hunt - Question 2

Posted 03-29-2012 10:05 PM (2820 views)  |   In reply to Ksharp

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
0 Likes
Reply
Ksharp
Super User Ksharp
Super User

Re: Google Treasure Hunt - Question 2

Posted 03-30-2012 01:56 AM (2820 views)  |   In reply to PGStats

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

0 Likes
Reply
PGStats
Opal | Level 21 PGStats
Opal | Level 21

Re: Google Treasure Hunt - Question 2

Posted 03-30-2012 11:03 PM (2820 views)  |   In reply to Ksharp

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

Re: Google Treasure Hunt - Question 2

Posted 03-30-2012 10:44 PM (2744 views)  |   In reply to Ksharp

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
0 Likes
Reply

hackathon24-white-horiz.png

The 2025 SAS Hackathon has begun!

It's finally time to hack! Remember to visit the SAS Hacker's Hub regularly for news and updates.

Latest Updates

How to Concatenate Values

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

Watch How to Concatenate Values on YouTube

Find more tutorials on the SAS Users YouTube channel.

SAS Training: Just a Click Away

 Ready to level-up your skills? Choose your own adventure.

Browse our catalog!

Discussion stats
  • 10 replies
  • ‎10-12-2011 07:07 PM
  • 3156 views
  • 0 likes
  • 3 in conversation