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