/* * Richard A. DeVenezia * www.devenezia.com * * On Oct.23, 2003 Chang Chung posted this interesting problem > > ----------------------------------------------------------------------- > > The following puzzle was given out on National Public Radio (Sep. 17, > > 2000): > > > > This comes from listener Toby Gottfried: Take the state names > > ALASKA and KANSAS. The last two letters of ALASKA are the first > > two letters of KANSAS. Can you find a chain of five state names > > that overlap like this, in which the last two letters of > > each are the first two letters of the next? What is it? > > > > Or, what are they? Find the solution using three methods: (1) proc sql; > > (2) data and proc steps; and (3) pure macro: */ /* * I posted this response, which was remarked upon by Paul Dorfman it presents a case of an ostensibly cartesianish SQL query which in fact is really well optimized - indeed, to such a degree that the creatiion of the auxiliary indexed file appears to be superfluous, for the virtual tables being joined are hash-indexed internally: * * He made this determination (see last) using the undocumented _method option of * Proc SQL. */ /* SQL way */ data states; length state $15; do fip = 1 to 56; state = fipname(fip); if state not in ("" "INVALID CODE" "DISTRICT OF COLUMBIA") then output; end; run; proc sql; create table tags (index = (from to)) as select state , fip , substr(state,length(state)-1,2) as from , substr(state,1,2) as to from states; quit; proc sql _method; create table chains as select _1.state as state1, _1.fip as fip1 , _2.state as state2, _2.fip as fip2 , _3.state as state3, _3.fip as fip3 , _4.state as state4, _4.fip as fip4 , _5.state as state5, _5.fip as fip5 from tags as _1 , tags as _2 , tags as _3 , tags as _4 , tags as _5 where _1.from = _2.to and _2.from = _3.to and _3.from = _4.to and _4.from = _5.to /* and _1.state ne _2.state and _1.state ne _3.state and _1.state ne _4.state and _1.state ne _5.state and _2.state ne _3.state and _2.state ne _4.state and _2.state ne _5.state and _3.state ne _4.state and _3.state ne _5.state and _4.state ne _5.state */ ; quit; /* Pauls way, using the non-indexed original table, indexed like processing occurs! */ proc sql _method ; select _1.state as st1 , _2.state as st2 , _3.state as st3 , _4.state as st4 , _5.state as st5 from states _1 , states _2 , states _3 , states _4 , states _5 where substr (_1.state, length(_1.state)-1, 2) = substr (_2.state, 1, 2) and substr (_2.state, length(_2.state)-1, 2) = substr (_3.state, 1, 2) and substr (_3.state, length(_3.state)-1, 2) = substr (_4.state, 1, 2) and substr (_4.state, length(_4.state)-1, 2) = substr (_5.state, 1, 2) ; quit; /* Macro way, full outer join */ %macro fivechain; %local i j state first last; %let i = 0; %do j = 1 %to 56; %let state = %sysfunc (fipname(&j)); %if %quote(&state) ne %str() and %quote(&state) ne %str(INVALID CODE) and %quote(&state) ne %str(DISTRICT OF COLUMBIA) %then %do; %let i = %eval (&i+1); %local state&i first&i last&i; %let state&i = &state; %let first&i = %substr (&state,1,2); %let last&i = %substr (&state, %eval(%length(&state)-1),2); %end; %end; %do i1 = 1 %to 50; %do i2 = 1 %to 50; %if %quote(&&last&i1) ne %quote(&&first&i2) %then %goto next_i2; %do i3 = 1 %to 50; %if %quote(&&last&i2) ne %quote(&&first&i3) %then %goto next_i3; %do i4 = 1 %to 50; %if %quote(&&last&i3) ne %quote(&&first&i4) %then %goto next_i4; %do i5 = 1 %to 50; %if %quote(&&last&i4) ne %quote(&&first&i5) %then %goto next_i5; %put &&state&i1 -> &&state&i2 -> &&state&i3 -> &&state&i4 -> &&state&i5 ; %next_i5: %end; %next_i4: %end; %next_i3: %end; %next_i2: %end; %next_i1: %end; %mend; %fivechain; /* chart the solution */ ods listing; goptions reset=all ftext='Comic Sans MS' htext=1.8pct; goptions device=png gsfname=gout xmax=10in ymax=10in hsize=6in vsize=8in; filename gout "\\extreme\samples\state-chain.png"; data anno; retain xsys ysys '2'; length text $20 function $8; array fipn [100] _temporary_; xmin=9; xinc=(100-2*xmin)/(5-1); yinc=100/52; function = 'label'; do while (not end1); set states end=end1; n+1; fipn[fip] = n; x = xmin; do i = 1 to 5; text=state; y = n * yinc; y = 100-y; output; x + xinc; end; end; text='';function=''; do while (not end2); set chains end=end2; array st state1-state5; array stfip fip1-fip5; x = xmin; do i = 1 to 5; n = fipn[stfip[i]]; y = n * yinc; y = 100-y; if i=1 then function = 'move'; else function = 'draw'; output; x + xinc; end; end; stop; keep xsys ysys x y function text ; run; proc gslide anno=anno; run; quit; options noxwait noxsync; x "start %sysfunc(pathname(gout))";