; the rat eats the cheese
(define-syntax define-memoized
(syntax-rules ()
((define-memoized (f arg ...) body ...)
(define f
(let ((cache (list)))
(lambda (arg ...)
(cond ((assoc `(,arg ...) cache) => cdr)
(else (let ((val (begin body ...)))
(set! cache (cons (cons `(,arg ...) val) cache))
val)))))))))
(define (make-cheese n fill)
(define (rand-row)
(let ((row (make-vector n 0)))
(do ((k 0 (+ k 1))) ((= k n) row)
(when (< (random 1.0) fill)
(vector-set! row k 1)))))
(set! nrows n) (set! ncols n)
(let ((rows (make-vector n #f)))
(do ((k 0 (+ k 1))) ((= k n))
(vector-set! rows k (rand-row)))
rows))
(define nrows #f) (define ncols #f)
(define cheese (make-cheese 20 0.15))
(for-each
(lambda (row) (display row) (newline))
(vector->list cheese))
(newline)
(define-memoized (rat r c)
(if (or (= r nrows) (= c ncols)) 0
(+ (vector-ref (vector-ref cheese r) c)
(max (rat (+ r 1) c) (rat r (+ c 1))))))
(display (rat 0 0)) (newline)