Hi,
It has been quite some time since the last post I made like this so I hope people will enjoy it.
The numbers on a typical phone pad are arranged as follows
1 2 3
4 5 6
7 8 9
0
Starting from the digit 1, and choosing successive digits as a knight moves in chess, determine how many different paths can be formed of length n. There is no need to make a list of the paths, only to count them.
A knight moves two steps either horizontally or vertically followed by one step in the perpendicular direction; thus, from the digit 1 on the keypad a knight can move to digits 6 or 8, and from the digit 4 on the keypad a knight can move to digits 3, 9 or 0. A path may visit the same digit more than once.
I took me a while to figure out how simple it was, but here it is :
%let n=50;
data knightPad(keep=n n13);
array Ns{6} n13 n2 n46 n79 n8 n0 (6*1);
array Ts{6} t13 t2 t46 t79 t8 t0;
format n13 best32.;
n=1;
output;
do n=2 to &n;
do j=1 to 6; Ts{j} = Ns{j}; end;
n13 = t46 + t8;
n2 = t79 + t79;
n46 = t13 + t79 + t0;
n79 = t2 + t46;
n8 = t13 + t13;
n0 = t46 + t46;
output;
end;
proc print; run;
PG
If I understood what is your mean .
data temp; infile datalines dlm=' ' ; input _start $ _end $; flag+1; datalines; 1 6 1 8 2 7 2 9 2 0 3 4 3 8 4 3 4 9 4 0 6 1 6 7 6 0 7 2 7 6 8 1 8 3 9 2 9 4 0 4 0 6 ; run; %let start=1; %let length=8; proc sort data=temp nodupkey; by _start _end; run; data _null_; 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('count','path'); pa.definedone(); do until(last); set temp(where=(_start="&start")) end=last; _count+1; count=_count; path=cats(_start,_end); pa.add(); end; do while(h_p.next()=0 and length(path) le &length); _path=path; if length(path) eq &length then n+1; do while(hi.next()=0); if substr(path,length(path),1) eq strip(_start) then do; _count+1;count=_count;path=cats(path,_end);pa.add(); path=_path; end; end; end; putlog 'How many paths ' n ; run;
Ksharp
Hi,
Can you please explain how it would from 4 to 0.
Thanks & Regards,
Manoj Bansal
A knight moves two steps either horizontally or vertically followed by one step .
So first move two steps 4 -> . then followed by one step . -> 0
1 2 3
4 5 6
7 8 9
. 0 .
So We Can consider the . to traverse the path but . cannot be destination. am i right?
I think so. But this need to ask FriedEgg. Maybe He can clarify it more.
KSharp,
As always I can count on you for a solution. The assumption for traversing from 4 -> 0 or 6-> 0 and visa-versa is fine. There is a issue with your proposed solution however. You have traversal 2 -> 0, this is not possible and causes an inaccurate solution. Once this is removed your code will provide accurate solutions, very quickly, for short paths. Finding the solution to a longer path however is very painful with this method. Say a length of 50, for example. Can you come up with a way to calculate longer paths?
Ksharp wrote:
data temp;
infile datalines dlm=' ' ;
input _start $ _end $;
flag+1;
datalines;
1 6
1 8
2 7
2 9
2 0
Now I want to know where this Math Puzzle come from ?
And It is fastest method I can think.
data temp; infile datalines dlm=' ' ; input _start : $1. _end : $1.; datalines; 1 6 1 8 2 7 2 9 3 4 3 8 4 3 4 9 4 0 6 1 6 7 6 0 7 2 7 6 8 1 8 3 9 2 9 4 0 4 0 6 ; run; %let start=1; %let length=16; data _null_; if _n_ eq 1 then do; length path _path $ 51; if 0 then set temp; declare hash ha(hashexp:10,dataset:'temp',multidata:'Y'); declare hiter hi('ha'); ha.definekey('_start'); ha.definedata('_end'); ha.definedone(); end; declare hash pa(ordered:'Y'); declare hiter h_p('pa'); pa.definekey('count'); pa.definedata('path'); pa.definedone(); set temp(where=(_start="&start")) end=last ; count=0;count+1; call missing(path);path=cats(_start,_end); pa.add(); do while(h_p.next()=0 and length(path) lt &length+1); _path=path; if length(path) eq &length then n+1; _start=substr(path,length(path),1); if (ha.find()=0) then do; count+1; path=cats(path,_end); pa.add(); path=_path; rc=ha.find_next(); do while(rc=0); count+1; path=cats(path,_end); pa.add(); path=_path; rc=ha.find_next(); end; end; end; if last then putlog 'How many paths ' n ; run;
Ksharp
This puzzle was presented to me by a friend (who is a math professor at the University of Colorado) via email, I'm not sure where he got it from or if he made it up.
Haha.
I find a faster way.
data temp; infile datalines dlm=' ' ; input _start : $1. _end : $1.; datalines; 1 6 1 8 2 7 2 9 3 4 3 8 4 3 4 9 4 0 6 1 6 7 6 0 7 2 7 6 8 1 8 3 9 2 9 4 0 4 0 6 ; run; %let start=1; %let length=16; %let len=%eval(&length+1); data _null_; if _n_ eq 1 then do; length end temp_end $ 1; length length temp_len 4 ; if 0 then set temp; declare hash ha(hashexp:10,dataset:'temp',multidata:'Y'); declare hiter hi('ha'); ha.definekey('_start'); ha.definedata('_end'); ha.definedone(); end; declare hash pa(ordered:'Y'); declare hiter h_p('pa'); pa.definekey('count'); pa.definedata('end','length'); pa.definedone(); set temp(where=(_start="&start")) end=last ; count=0;count+1; end=_end; length=2; pa.add(); do while(h_p.next()=0 and length lt &len ); temp_end=end; temp_len=length; if length eq &length then n+1; if (ha.find(key:end)=0) then do; count+1; end=_end ; length+1; pa.add(); end=temp_end; length=temp_len; rc=ha.find_next(); do while(rc=0); count+1; end=_end ; length+1; pa.add(); end=temp_end; length=temp_len; rc=ha.find_next(); end; end; end; if last then putlog 'How many paths ' n ; run;
Ksharp
Nice work on improving the brute force method. It can still be taken a step further to calculate nearly any given length extremely fast. The answer of n paths of x length follows a sequence that can be exploited. If you want more clues send me a email.
Kudos for the attempt.Unfortunately this could not be run on SAS 9.1.3
Yes. Because I used a new method find_next().
I can modify my code to run under SAS9.1.3, If you were interested.
Ksharp
That would be great!
FriedEgg.
Under your implication, It is a faster code. I am thinking a better algorithm.
data temp; infile datalines dlm=' ' ; input _start : $1. _end : $1. ; datalines; 1 6 1 8 2 7 2 9 3 4 3 8 4 3 4 9 4 0 6 1 6 7 6 0 7 2 7 6 8 1 8 3 9 2 9 4 0 4 0 6 ; run; %let start=1; %let length=16; %let len=%eval(&length+1); data _null_; length end $ 1; length temp_len length 4; declare hash pa(ordered:'Y',hashexp:16); declare hiter h_p('pa'); pa.definekey('count'); pa.definedata('end','length'); pa.definedone(); set temp(where=(_start="&start")) end=last ; count=0;count+1; end=_end; length=2; pa.add(); do while(h_p.next()=0 and length lt &len ); temp_len=length; if length eq &length then sum+1 ; else do; select(end); when('0') do; count+1;end='4';length+1;pa.add();length=temp_len; count+1;end='6';length+1;pa.add(); end; when('1') do; count+1;end='6';length+1;pa.add();length=temp_len; count+1;end='8';length+1;pa.add(); end; when('2') do; count+1;end='7';length+1;pa.add();length=temp_len; count+1;end='9';length+1;pa.add(); end; when('3') do; count+1;end='4';length+1;pa.add();length=temp_len; count+1;end='8';length+1;pa.add(); end; when('4') do; count+1;end='3';length+1;pa.add();length=temp_len; count+1;end='9';length+1;pa.add();length=temp_len; count+1;end='0';length+1;pa.add(); end; when('6') do; count+1;end='1';length+1;pa.add();length=temp_len; count+1;end='7';length+1;pa.add();length=temp_len; count+1;end='0';length+1;pa.add(); end; when('7') do; count+1;end='2';length+1;pa.add();length=temp_len; count+1;end='6';length+1;pa.add(); end; when('8') do; count+1;end='1';length+1;pa.add();length=temp_len; count+1;end='3';length+1;pa.add(); end; when('9') do; count+1;end='4';length+1;pa.add();length=temp_len; count+1;end='2';length+1;pa.add(); end; otherwise; end; end; end; if last then putlog 'How many paths : ' sum ; run;
Ksharp
Available on demand!
Missed SAS Innovate Las Vegas? Watch all the action for free! View the keynotes, general sessions and 22 breakouts on demand.
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.