Knights of the Dialing Pad (Math Puzzle)

[FriedEgg]

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.

[Ksharp]

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]

Hi,

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

Thanks  & Regards,

Manoj Bansal

[Ksharp]

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]

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

[Ksharp]

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

[FriedEgg]

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]

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]

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]

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]

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]

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

[Ksharp]

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]

That would be great!

[Ksharp]

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