Project:
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 ``` ```; 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)) ```
 ```1 2 3 4 ``` ```1424 1424 115109382558226759578158103787777918965703239507718381740212170851014564315086197613965739567866877377332634181327163141142440318419332531657595880810016039162881799601851712976918057797975890692565692814769008372525555560482873241331236262669881273960882325078328272918117049798864734218218664306890139797247737022400814924823939354135385894667021349644402688 cpu time: 10 real time: 66 gc time: 0 ```