; knights on a keypad

(define (sum xs) (apply + xs))

(define (count n from) ; recursive solution
  (let ((graph '((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) (0 4 6))))
    (if (= n 1) 1
      (sum (map (lambda (x) (count (- n 1) x))
                (cdr (assoc from graph)))))))

(display (count 10 1)) (newline)

(define (make-matrix rows columns . value)
  (do ((m (make-vector rows)) (i 0 (+ i 1)))
      ((= i rows) m)
    (if (null? value)
        (vector-set! m i (make-vector columns))
        (vector-set! m i (make-vector columns (car value))))))

(define (matrix-ref m i j) (vector-ref (vector-ref m i) j))

(define (matrix-set! m i j x) (vector-set! (vector-ref m i) j x))

(define (count n) ; memoized solution
  (let ((counts (make-matrix n 9 1))
        (graph (vector '(4 6) '(5 7) '(3 6) '(2 7 8)
                 '(0 5 8) '(1 4) '(0 2) '(1 3) '(3 4))))
    (do ((r 1 (+ r 1))) ((= n r) (matrix-ref counts (- n 1) 0))
      (do ((c 0 (+ c 1))) ((= c 9))
        (matrix-set! counts r c
          (sum (map (lambda (c) (matrix-ref counts (- r 1) c))
                    (vector-ref graph c))))))))

(display (count 10)) (newline)
(time (display (count 1000)) (newline))