topic Knights of the Dialing Pad (Math Puzzle) in SAS Programming

Knights of the Dialing Pad (Math Puzzle)

FriedEgg — Sat, 25 Feb 2012 00:00:06 GMT

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

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.

Knights of the Dialing Pad (Math Puzzle)

Ksharp — Mon, 27 Feb 2012 06:42:34 GMT

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

Knights of the Dialing Pad (Math Puzzle)

manojinpec — Mon, 27 Feb 2012 08:29:04 GMT

Hi,

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

Thanks & Regards,

Manoj Bansal

Knights of the Dialing Pad (Math Puzzle)

Ksharp — Mon, 27 Feb 2012 08:48:00 GMT

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 .

Knights of the Dialing Pad (Math Puzzle)

manojinpec — Mon, 27 Feb 2012 09:52:24 GMT

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

Knights of the Dialing Pad (Math Puzzle)

Ksharp — Tue, 28 Feb 2012 01:39:56 GMT

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

Knights of the Dialing Pad (Math Puzzle)

FriedEgg — Tue, 28 Feb 2012 03:49:32 GMT

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

Re: Knights of the Dialing Pad (Math Puzzle)

Ksharp — Tue, 28 Feb 2012 06:24:19 GMT

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

Knights of the Dialing Pad (Math Puzzle)

Ksharp — Tue, 28 Feb 2012 07:12:19 GMT

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

Knights of the Dialing Pad (Math Puzzle)

FriedEgg — Tue, 28 Feb 2012 16:24:53 GMT

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.

Knights of the Dialing Pad (Math Puzzle)

FriedEgg — Tue, 28 Feb 2012 16:29:12 GMT

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.

Knights of the Dialing Pad (Math Puzzle)

SASPhile — Tue, 28 Feb 2012 20:50:38 GMT

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

Knights of the Dialing Pad (Math Puzzle)

Ksharp — Wed, 29 Feb 2012 02:44:28 GMT

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

Knights of the Dialing Pad (Math Puzzle)

Ksharp — Wed, 29 Feb 2012 04:41:36 GMT

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

Knights of the Dialing Pad (Math Puzzle)

SASPhile — Wed, 29 Feb 2012 16:14:47 GMT

That would be great!

Re: Knights of the Dialing Pad (Math Puzzle)

PGStats — Wed, 29 Feb 2012 17:03:39 GMT

Thank you Fried for a nice puzzle!

For large n values, I can only think of approximate solutions, such as

(20/9)**(n-1)

or perhaps,

(10/4)**FLOOR((n-1)/2) * (10/5)**CEIL((n-1)/2)

No, come to think of it, the following value should be closer:

(2**7*3**2)**((n-1)/9) = 2.188575**(n-1)

I'm curious to know how far those approximations are to the exact walk counts.

Message enhanced by: PG

Re: Knights of the Dialing Pad (Math Puzzle)

Ksharp — Thu, 01 Mar 2012 05:45:21 GMT

Hi. FriedEgg.

I optimized my code again. It should be faster.

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);
 temp_len=length;
 if length eq &len then sum+ ifn(end in ('4' '6'),3,2) ;
 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

Re: Knights of the Dialing Pad (Math Puzzle)

FriedEgg — Tue, 06 Mar 2012 20:31:41 GMT

PG,

Here is a snippet with the first 27 answers to the problem along with your three attempts.

data test;

n=1;

do i=1,2,5,10,26,52,136,272,712,1424,3728,7456,19520,39040,102208,204416,535168,1070336,2802176,5604352,14672384,29344768,76825600,153651200,402264064,804528128,2106281984;

x=(20/9)**(n-1);

y=(10/4)**floor((n-1)/2)*(10/5)**ceil((n-1)/2);

z=(2**7*3**2)**((n-1)/9);

output;

n+1;

end;

run;

n i x y z

1 1 1.00 1 1.00

2 2 2.22 2 2.19

3 5 4.94 5 4.79

4 10 10.97 10 10.48

5 26 24.39 25 22.94

6 52 54.19 50 50.21

7 136 120.43 125 109.89

8 272 267.62 250 240.51

9 712 594.70 625 526.37

10 1424 1321.56 1250 1152.00

11 3728 2936.80 3125 2521.24

12 7456 6526.23 6250 5517.92

13 19520 14502.73 15625 12076.38

14 39040 32228.29 31250 26430.05

15 102208 71618.43 78125 57844.15

16 204416 159152.07 156250 126596.24

17 535168 353671.27 390625 277065.33

18 1070336 785936.15 781250 606378.19

19 2802176 1746524.78 1953125 1327104.00

20 5604352 3881166.18 3906250 2904466.32

21 14672384 8624813.73 9765625 6356641.68

22 29344768 19166252.74 19531250 13911985.55

23 76825600 42591672.75 48828125 30447420.45

24 153651200 94648161.67 97656250 66636455.93

25 402264064 210329248.15 244140625 145838865.61

26 804528128 467398329.22 488281250 319179260.46

27 2106281984 1038662953.83 1220703125 698547673.69

Re: Knights of the Dialing Pad (Math Puzzle)

PGStats — Tue, 06 Mar 2012 21:17:21 GMT

Thanks Fried. I wasn't very close but apparently, I had found the proper form of the solution. Now I just have to figure out why the answer was N = 2.272590393435**(n-1) :smileygrin:. I would venture to guess that the true value for n=17 is closer to 506220.

Re: Knights of the Dialing Pad (Math Puzzle)

Ksharp — Wed, 07 Mar 2012 05:52:25 GMT

the true value for n=17 is 535168 .

Ksharp