[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/k8lxMxUC    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Jan 17:
; 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))


Output:
1
2
3
4
1424
1424
115109382558226759578158103787777918965703239507718381740212170851014564315086197613965739567866877377332634181327163141142440318419332531657595880810016039162881799601851712976918057797975890692565692814769008372525555560482873241331236262669881273960882325078328272918117049798864734218218664306890139797247737022400814924823939354135385894667021349644402688
cpu time: 10 real time: 66 gc time: 0


Create a new paste based on this one


Comments: