Knights On A Keypad

January 20, 2012

Today’s exercise is an interview question that appeared on Stack Overflow a few years ago:

The numbers on a telephone keypad are arranged thus:

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.

Your task is to write a function that determines the number of paths of length n that a knight can trace on a keyboard starting from digit 1. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

25 Responses to “Knights On A Keypad”

  1. Jussi Piitulainen said

    If one takes “path” to mean a sequence of distinct nodes, the number of different paths is small and plain recursion is well fast enough. One keeps track of visited nodes in order to not step on them again.

    (define (next node)
      (vector-ref '#((4 6  ) (6 8  ) (7 9  ) (4 8  ) (0 3 9)
                     (     ) (0 1 7) (2 6  ) (1 3  ) (2 4  )) node))
    
    (define (count from many)
      (let dive ((from from) (seen (list from)) (many many))
        (if (zero? many) 1
            (apply + (map (lambda (to)
                            (if (memv to seen) 0
                                (dive to (cons to seen) (- many 1))))
                          (next from))))))
    
    (define (count-all from)
      (apply + (map (lambda (many) (count from many))
                    '(0 1 2 3 4 5 6 7 8 9))))
    

    The total numbers of paths of any length from each node are as follows.

    guile> (map count-all '(0 1 2 3 4 5 6 7 8 9))
    (31 29 29 29 25 1 25 29 29 29)
    

    There is no way out of (or in to) 5, and 0 stands out as its own kind, and 4 and 6 are symmetric to each other. Counting paths of length 8 or 9 is already overkill: there can be none.

  2. programmingpraxis said

    Jussi: A path may visit the same digit more than once. That’s explicitly stated in the last sentence of the problem.

  3. Jussi Piitulainen said

    Somehow I managed to miss that statement. I see it now. Sorry about the noise. (Though I like to think of variations.)

  4. j2kun said

    Construct an adjacency matrix that represents the possible destinations from each square on the keypad. This is a 10×10 matrix of ones and zeros, where the i,j entry contains a 1 if and only if there is a knight’s move from square i to square j (let’s index from zero just for fun). Taking powers of this matrix gives a matrix containing in each i,j entry the number of distinct paths (walks, if you want to use the graph-theoretic term) from the ith square to the jth square. Since we’re only multiplying 10×10 matrices, I’d expect this to be relatively fast, even for some large n. However, if you want to get fancy with the cheese-whiz, we could diagonalize the adjacency matrix (it is symmetric by construction, so by the spectral theorem it is diagonalizable), take powers of that, and then revert it to its original form using the change of basis we got from our diagonalization process. The fact that this works is simple matrix algebra. Taking powers of an nxn diagonal matrix is linear in n, so the speed of the algorithm boils down to the speed of the decomposition, which is essentially constant (it’s only a 10×10 matrix).

    Unfortunately I don’t have the time to code this up right now, but it’d be a 5 minute affair in Mathematica or any language that has the diagonalization thing built in.

  5. j2kun said

    Here’s my mathematica solution, using the idea from my previous comment, and Mathematica’s JordanDecomposition routine (which anyone could implement as an exercise, I’m sure).

    matrix = {{0, 0, 0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0, 1, 
        0}, {0, 0, 0, 0, 0, 0, 0, 1, 0, 1}, {0, 0, 0, 0, 1, 0, 0, 0, 1, 
        0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 
        0}, {1, 1, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 1, 0, 0, 0, 1, 0, 0, 
        0}, {0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0, 0, 
        0}} ;
    
    numPaths[n_] :=
      Module[{changeOfBasis, diagonalMatrix, diagonalPower, originalPower},
       {changeOfBasis, diagonalMatrix} = JordanDecomposition[N[matrix, 20]];
       diagonalPower = DiagonalMatrix[Diagonal[diagonalMatrix]^(n-1)];
       originalPower = changeOfBasis.diagonalPower.Inverse[changeOfBasis];
       Return[Map[Apply[Plus, #] &, Round[originalPower]][[2]]]
       ];
    

    And running it on n=10 gives the 9th matrix power (to agree with your definition of path length), and provides the correct answer:

    Timing[numPaths[10]]
    {0.044003, 1424}
    
    Timing[numPaths[1000000]]
    {0.076004, 411651680085467700452...}
    

    So we can compute the right value for n=1,000,000, but the number has 359,503 digits, so it won’t fit in this comment. The nice thing is, while the dynamic approach is O(n^2), this approach is O(n)! The first result of the Timing call gives the CPU time spent on the function, which is a mere 0.076 seconds. Beat that :)

  6. programmingpraxis said

    J2kun: Well, why don’t you implement JordanDecomposition as an exercise. If you like, email me privately, and I’ll help you write it as a guest author for a future exercise.

    By the way, the dynamic programming solution is O(n), not O(n2); the matrix is n along one dimension but 9 on the other dimension. Your matrix algorithm does require much less space, however, O(1) compared to O(n).

  7. j2kun said

    Yes of course, it’s O(n). I just saw a big table in your solution and had that knee-jerk, witch-hunting reaction, but I was mistaken.

    At the risk of sounding pretentious, here are a few more notes on why my algorithm is neat: First, it counts all paths between all pairs of squares on the keypad, so it gives us much more information; and second, the same algorithm applies to counting paths in any graph. All we need to do to generalize the algorithm is change the input matrix, and we still have the lightning-fast implementation.

    I’ll get back to you about writing JordanDecomposition. It’s significantly less interesting than what you can use it for, and if I remember correctly it basically reduces to row-reduction. Plus, for a general matrix, JordanDecomposition is frowned upon because it’s numerically unstable. So people usually avoid it.

  8. Jan Van lent said

    You can use the matrix approach to get a closed-form expression (Maple code below).
    This formula involves the golden ratio (just as for the Fibonacci numbers).

    phi := (sqrt(5)+1)/2; # golden ratio
    q := ;
    H := ;
    Phi := ;
    c := 2^(n/2)/40 * q^+ . H . Phi;
    simplify(eval(c, n=9)); # => 1424

  9. Jan Van lent said

    You can use the matrix approach to get a closed-form expression (Maple code below).
    This formula involves the golden ratio (just as for the Fibonacci numbers).

    phi := (sqrt(5)+1)/2; # golden ratio
    q := < 10, 4*sqrt(5), 5*sqrt(2), 3*sqrt(2)*sqrt(5) >;
    H := < 1,  1,  1,  1; 
           1,  1, -1, -1; 
           1, -1, -1,  1; 
           1, -1,  1, -1 >;
    Phi := < phi^n, (-phi)^n, phi^(-n), (-phi)^(-n) >;
    c := 2^(n/2)/40 * q^+ . H . Phi;
    simplify(eval(c, n=9)); # => 1424
    
  10. ardnew said

    I took the brute force matrix approach:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define NUM_KEYS 10
    #define POWER     9
    
    typedef unsigned short key;
    
    key map[NUM_KEYS] = {
       40, // 0000101000
       10, // 0000001010
        5, // 0000000101
       34, // 0000100010
      577, // 1001000001
        0, // 0000000000
      772, // 1100000100
      136, // 0010001000
      320, // 0101000000
      160  // 0010100000
    };
    
    int adj(key i, key j, int n)
    {
      return map[i] >> (n - j - 1) & 1;
    }
    
    // dot product
    int dot(int **p, key i, key j, int n)
    {
      int m, s = 0;
       
      for (m = 0; m < n; ++m)
        s += adj(m, i, n) * p[j][m];
        
      return s;
    }
    
    // multiplies matrix p by map
    void matmult(int **p, int **q, int n)
    {
      int i, j;
    
      for (i = n; i--;)
        for (j = n; j--;)
          q[i][j] = dot(p, i, j, n);
        
      for (i = n; i--;) 
        for (j = n; j--;)
          p[i][j] = q[i][j];
    }
    
    int main(void)
    { 
      // result matrix 
      int **p = malloc(NUM_KEYS * sizeof(p));
      
      // scratch matrix for storing inner products
      int **q = malloc(NUM_KEYS * sizeof(p)); 
      
      int i, j, k = 0;
      
      // initialize the matrices
      for (i = 0; i < NUM_KEYS; ++i)
      {
        p[i] = malloc(NUM_KEYS * sizeof(*p));
        q[i] = malloc(NUM_KEYS * sizeof(*p));    
        
        // scratch matrix
        memset(q[i], 0, NUM_KEYS);
        
        // result matrix
        for (j = NUM_KEYS; j--;)
          p[i][j] = adj(i, j, NUM_KEYS);    
      } 
      
      // perform matrix multiplication
      for (i = POWER; --i;) 
        matmult(p, q, NUM_KEYS);
      
      // sum the 1 key's components
      for (i = NUM_KEYS; --i;)
        k += p[1][i];
        
      printf("num paths = %d\n", k);
        
      return 0;
    }
    

    it appears to run relatively quickly:

    $ time r
    num paths = 1424
    
    real  0m0.029s
    user  0m0.030s
    sys   0m0.015s
    
  11. My solution that requires constant memory although it does not seem to be as fast as the others above.

    from collections import defaultdict
    
    def count_knight_paths(maxlevel):
        jump = {0: [6, 4], 1: [6, 8], 2: [9, 7],
                3: [4, 8], 4: [9, 3, 0], 6: [7, 1, 0],
                7: [6, 2], 8: [3, 1], 9: [4, 2]}
        c = { 1 : 1 }
        for level in range(maxlevel):
            cprim = defaultdict(int)
            for key in c:
                for jumped in jump[key]:
                    cprim[jumped] += c[key]
            c = cprim
        return sum(c.values())
    
    if __name__ == "__main__":
        for i in range(10):
            print(i + 1, count_knight_paths(i))
    

    or here:

    http://codepad.org/VY2TvQjU

  12. […] a perfect brain teaser for a Friday night. Let’s find how many paths of a certain length a chess knight on a phone […]

  13. Axio said

    Simple, with memoization.

    (define (nexts n)
      (case n ((0) '(4 6)) ((1) '(6 8)) ((2) '(7 9))
        ((3) '(4 8)) ((4) '(3 9 0)) ((6) '(1 7 0)) ((7) '(2 6))
        ((8) '(1 3)) ((9) '(2 4)) (else (error "impossiburu!"))))
    
    (define (count-memo from len memo)
      (let ((r (table-ref memo (cons from len) #f)))
        (or r (let ((r (if (zero? len)
                         1
                         (fold-left
                           + 0 (map
                                 (lambda (new-from) (count-memo new-from (1- len) memo))
                                 (nexts from))))))
                (table-set! memo (cons from len) r)
                r))))
    
    (define (test-memo n) (count-memo 1 n (make-table test: equal?)))
    

    P!

  14. Axio said

    In CL, more idiomatic.

    (defvar nexts '#((4 6) (6 8) (7 9) (4 8) (3 9 0) () (1 7 0) (2 6) (1 3) (2 4)))
    (defun nexts (n) (aref nexts n))
    
    (defun count-memo (from len memo)
      (or (and (zerop len) 1)
          (gethash (cons from len) memo)
          (setf (gethash (cons from len) memo)
                (apply #'+ (mapcar
                           (lambda (new-from) (count-memo new-from (1- len) memo))
                           (nexts from))))))
    
    (defun test-memo (n) (count-memo 1 n (make-hash-table :test #'equal)))
    
  15. Tante Hedwig said
    import Data.Map as Mknights      = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],[1,7,0],[2,6],[1,3],[2,4]]knightsTable = M.fromList $ zip [0..] knightsnextMove     = concatMap ((\x -> case x of (Just x) -> x) . flip M.lookup knightsTable)count n s    = length $ foldl (\acc f -> f acc) s (replicate (n-1) nextMove)
  16. Tante Hedwig said

    A solution in Haskell:

    > import Data.Map as M
    > knights      = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],[1,7,0],[2,6],[1,3],[2,4]]
    > knightsTable = M.fromList $ zip [0..] knights
    > nextMove     = concatMap ((\x -> case x of (Just x) -> x) . flip M.lookup knightsTable)
    > count n s    = length $ foldl (\acc f -> f acc) s (replicate (n-1) nextMove)
    
  17. dmitru said

    Here is my DP solution. It uses constant memory and takes linear time:

    moves = [[4, 6], [8, 6], [7, 9], 
             [4, 8], [3, 0, 9], [], 
             [1, 7, 0], [2, 6], [1, 3], 
             [2, 4]]
    
    def solve(n, pos):
        row = [1 for p in range(10)]
        for l in range(n - 1):
            for p in range(10):
                new_row = [0 for p in range(10)]
                for np in moves[p]:
                    new_row[p] += row[np]
                row = new_row
        return row[pos]
    
  18. dmitru said

    Here is my DP solution. It uses constant memory and is pretty fast:

    def solve(n, pos):
        table = [[0 for p in range(10)] for l in range(n + 1)]
        for p in range(10):
            table[1][p] = 1
        for l in range(2, n + 1):
            for p in range(10):
                table[l][p] = 0
                for np in moves[p]:
                    table[l][p] += table[l - 1][np]
        return table[n][pos]
    
    for length in (1000, 5000, 10000):
        print(runtime(solve, length, 1))
    
    0.015690088272094727
    0.1218729019165039
    0.3139920234680176
    
  19. Jeff said

    Am I missing something or is the solution posted at the top of page 2 really counting the number of unique digits of length n starting at 1? I’m just going by the ‘graph’ data structure. I’d imagine that a path of length=1 would include two digits and so there should be 4 unique paths of length=1 from the number 1 (1 to 6 via 2, 1 to 6 via 4, 1 to 8 via 2, 1 to 8 via 4).

    If I’m reading it correctly, to solve the problem as written I’d imagine the graph array would need to look more like this:


    $movesA = array(
    0=>array(4,6),
    1=>array(6,6,8,8),
    2=>array(7,7,9,9),
    3=>array(4,4,8,8),
    4=>array(3,3,9,0),
    5=>NULL,
    6=>array(1,1,7,7,0),
    7=>array(2,2,6,6),
    8=>array(1,1,3,3),
    9=>array(4,4,2,2),
    );

    Then, instead of returning 1 if n==1 it should be modified to return 1 if n==0. Counting this way the number of unique 10-segment paths that can be drawn starting from the 1 key is 1267976.

    Does that seem right?

  20. programmingpraxis said

    Jeff: No, that’s not right.

    First, a path with two digits has length 2, not length 1.

    Second, there are two paths of length 2 starting from digit 1: 16 and 18.

    Third, your successor array is incorrect. There are only two successors of 1 — 6 and 8 — not four successors. Your successor lists for 2, 3, 4, 6, 7, 8 and 9 are similarly incorrect.

  21. Jeff said

    @programmingpraxis And that’s certainly the problem that most of the solutions are solving, and where I would have gone if the problem had been stated something like, “determine how many different numbers can be formed of length n.”

    Either way, they’re both great puzzles. Thanks for the fun excercise!

  22. Raphael Fuchs said

    My solution in Scala, time and space in O(n):

    val neighbours = Map(
      0 -> List(4,6),
      1 -> List(6,8),
      2 -> List(7,9),
      3 -> List(4,8),
      4 -> List(0,3,9),
      5 -> List(),
      6 -> List(0,1,7),
      7 -> List(2,6),
      8 -> List(1,3),
      9 -> List(2,4)
    )

    def count(n: Int): Int = {
      // memoization table (DP)
      val T = Array.ofDim[Int](n+1, 10)

      // initialize first row
      for (key <- 0 to 9)
        T(0)(key) = 1

      // fill in other rows
      for (n <- 1 to n; k <- 0 to 9) {
        T(n)(k) = neighbours(k) map { T(n-1)(_) } sum
      }

      T(n)(1)
    }

  23. sathish said

    Am a M.C.A Student i cant understand the problem will you please help me to understand the problem?
    My doubt is how to find length and the value 1424 is been calculated?
    please help me awaiting for your reply
    by sathish

  24. A did one for a couple other pieces as well just to see what it looked like:

    my %pieces_moves = (
       knight => [
          [4, 6], 
          [8, 6], 
          [7, 9], 
          [4, 8], 
          [3, 0, 9], 
          [],
          [1, 7, 0], 
          [2, 6], 
          [1, 3], 
          [2, 4]
       ],
       pawn => [
          [8], 
          [2, 4], 
          [1, 3, 5], 
          [2, 6], 
          [1, 5, 7], 
          [2, 4, 6, 8], 
          [3, 5, 9], 
          [4, 8], 
          [0, 5, 7, 9], 
          [6, 8]
       ],
       queen => [
          [2, 5, 7, 8, 9], 
          [2, 3, 4, 5, 7], 
          [0, 1, 3, 4, 5, 6, 8], 
          [1, 2, 5, 6, 9], 
          [1, 2, 5, 6, 7, 8], 
          [0, 1, 2, 3, 4, 6, 7, 8, 9], 
          [2, 3, 4, 5, 8, 9], 
          [0, 1, 4, 5, 8, 9], 
          [0, 2, 4, 5, 6, 7, 9], 
          [0, 3, 5, 6, 7, 8]
       ],
    );
    
    memoize 'count_ways';
    sub count_ways {
       my ($piece, $n, $pos) = @_;
       $pos //= 0;
    
       return 1 
          if $n == 1;
       
       my $sum = 0; 
       foreach my $move ( @{$pieces_moves{$piece}->[$pos]} ) {
          $sum += count_ways($piece, $n - 1, $move);
       }
    
       return $sum; 
    }
    
    foreach my $piece ( qw(knight queen pawn) ) {
       print "$piece\n";
       print "----------\n";
       print 'Memoized solution: ' . count_ways($piece, 10, 1)    . "\n";
       print "\n";
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 637 other followers

%d bloggers like this: