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
Don't miss out on SAS Innovate - Register now for the FREE Livestream!
Can't make it to Vegas? No problem! Watch our general sessions LIVE or on-demand starting April 17th. Hear from SAS execs, best-selling author Adam Grant, Hot Ones host Sean Evans, top tech journalist Kara Swisher, AI expert Cassie Kozyrkov, and the mind-blowing dance crew iLuminate! Plus, get access to over 20 breakout sessions.
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.