; 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))