BookmarkSubscribeRSS Feed
🔒 This topic is solved and locked. Need further help from the community? Please sign in and ask a new question.

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.

1 ACCEPTED SOLUTION

Accepted Solutions
PGStats
Opal | Level 21

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

PG

View solution in original post

24 REPLIES 24
Ksharp
Super User

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

manojinpec
Obsidian | Level 7

Hi,

Can you please explain how it would from 4 to 0.

Thanks  & Regards,

Manoj Bansal

Ksharp
Super User

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 .

manojinpec
Obsidian | Level 7

So We Can consider the . to traverse the path but . cannot be destination. am i right?

Ksharp
Super User

I think so. But this need to ask FriedEgg. Maybe He can clarify it more.

FriedEgg
SAS Employee

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

Ksharp
Super User

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

FriedEgg
SAS Employee

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.

Ksharp
Super User

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

FriedEgg
SAS Employee

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.

SASPhile
Quartz | Level 8

Kudos for the attempt.Unfortunately this could not be run on SAS 9.1.3

Ksharp
Super User

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

SASPhile
Quartz | Level 8

That would be great!

Ksharp
Super User

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

sas-innovate-2024.png

Join us for SAS Innovate April 16-19 at the Aria in Las Vegas. Bring the team and save big with our group pricing for a limited time only.

Pre-conference courses and tutorials are filling up fast and are always a sellout. Register today to reserve your seat.

 

Register now!

How to Concatenate Values

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.

Click image to register for webinarClick image to register for webinar

Classroom Training Available!

Select SAS Training centers are offering in-person courses. View upcoming courses for:

View all other training opportunities.

Discussion stats
  • 24 replies
  • 3226 views
  • 6 likes
  • 5 in conversation