Knights of the Dialing Pad (Math Puzzle)

[PGStats]

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.

PG

Message enhanced by: PG

[FriedEgg]

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

[PGStats]

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.

PG

[Ksharp]

the true value for n=17 is  535168  .

Ksharp

[Ksharp]

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

[PGStats · Accepted solution]

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

[Ksharp]

Very impressive .

Can you explain it more about your logic ?

Ksharp

[FriedEgg]

Excellent work PG.  your answer is a simplified version of my own solution.

data _null_;
 array kp[2,10] _temporary_ (20*1);
 do _n_=2 to &n;
  do j=1 to 10;
   kp[1,j]=kp[2,j];
  end;
  kp[2,1]=kp[1,6]+kp[1,8]; /* 1: 6 8 */
  kp[2,2]=kp[1,7]+kp[1,9]; /* 2: 7 9 */
  kp[2,3]=kp[1,4]+kp[1,8]; /* 3: 4 8 */
  kp[2,4]=kp[1,3]+kp[1,9]+kp[1,10]; /* 4: 3 9 0 */
  kp[2,6]=kp[1,1]+kp[1,7]+kp[1,10]; /* 6: 1 7 0 */
  kp[2,7]=kp[1,2]+kp[1,6]; /* 7: 2 6 */
  kp[2,8]=kp[1,1]+kp[1,3]; /* 8: 1 3 */
  kp[2,9]=kp[1,2]+kp[1,4]; /* 9: 2 4 */
  kp[2,10]=kp[1,4]+kp[1,6]; /* 0: 4 6 */
 end;
 put kp[2,1] comma32.;
run;
341,668,189,630,889,984

The problem is a numeric sequence as I suggested and does not require tracking actual paths as was mentioned in the original posting of the puzzle.

kp[1,n] stores the previous path length for keypad position n

kp[2,n] is the current value for path length from position n

The length of a numbers path is the sum of it's possibilites paths over time.  I think my version is a little more self documenting than PG's.  It is rather late so elequently explaining myself seems harder than normal...

[PGStats]

I might try to add a bit of explanation.

It's one of those Aha! insights (à la Martin Gardner) that seem almost obvious once you see them.

I got on the right track when I noticed that the number of possible keypad walks of a given length depends only on your starting key and not on the sequence that got you there. So, all the walks that get you to key 6 on step 45 of a walk of length 50 (and there are many!) will generate the same number of walks towards the total.

And that number is simple to calculate. If W(m,6) is the number of walks of length m starting on key 6, then W(m,6) = W(m-1,1) + W(m-1,7) + W(m-1,0) because only keys 1, 7 end 0 can follow key 6. This is a simple recurrence relation that you can start with W(1,i) = 1 and iteratively find W(n,1) : the number of walks of length n starting on key 1.

Also note that, by symmetry, W(m,1)=W(m,3), W(m,4)=W(m,6) and W(m,7)=W(m,9). So you can save a bit on those calculations.

Thank you Fried for suggesting that nice challenge. Bravo KSharp for displaying such great programming craftsmanship!

PG

[Ksharp]

PGStats

Yes. I have understood what your code mean . I wonder why I can't realize so simple shortcut.

It seems that Computer is not always better than human's brain.Anyway it is better than mine.

Congratulations!

Regards.

Ksharp