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

OyB0aGUgcmF0IGVhdHMgdGhlIGNoZWVzZQoKKGRlZmluZS1zeW50YXggZGVmaW5lLW1lbW9pemVkCiAgKHN5bnRheC1ydWxlcyAoKQogICAgKChkZWZpbmUtbWVtb2l6ZWQgKGYgYXJnIC4uLikgYm9keSAuLi4pCiAgICAgIChkZWZpbmUgZgogICAgICAgIChsZXQgKChjYWNoZSAobGlzdCkpKQogICAgICAgICAgKGxhbWJkYSAoYXJnIC4uLikKICAgICAgICAgICAgKGNvbmQgKChhc3NvYyBgKCxhcmcgLi4uKSBjYWNoZSkgPT4gY2RyKQogICAgICAgICAgICAoZWxzZSAobGV0ICgodmFsIChiZWdpbiBib2R5IC4uLikpKQogICAgICAgICAgICAgICAgICAgIChzZXQhIGNhY2hlIChjb25zIChjb25zIGAoLGFyZyAuLi4pIHZhbCkgY2FjaGUpKQogICAgICAgICAgICAgICAgICAgIHZhbCkpKSkpKSkpKQoKKGRlZmluZSAobWFrZS1jaGVlc2UgbiBmaWxsKQogIChkZWZpbmUgKHJhbmQtcm93KQogICAgKGxldCAoKHJvdyAobWFrZS12ZWN0b3IgbiAwKSkpCiAgICAgIChkbyAoKGsgMCAoKyBrIDEpKSkgKCg9IGsgbikgcm93KQogICAgICAgICh3aGVuICg8IChyYW5kb20gMS4wKSBmaWxsKQogICAgICAgICAgKHZlY3Rvci1zZXQhIHJvdyBrIDEpKSkpKQogIChzZXQhIG5yb3dzIG4pIChzZXQhIG5jb2xzIG4pCiAgKGxldCAoKHJvd3MgKG1ha2UtdmVjdG9yIG4gI2YpKSkKICAgIChkbyAoKGsgMCAoKyBrIDEpKSkgKCg9IGsgbikpCiAgICAgICh2ZWN0b3Itc2V0ISByb3dzIGsgKHJhbmQtcm93KSkpCiAgICByb3dzKSkKCihkZWZpbmUgbnJvd3MgI2YpIChkZWZpbmUgbmNvbHMgI2YpCihkZWZpbmUgY2hlZXNlIChtYWtlLWNoZWVzZSAyMCAwLjE1KSkKCihmb3ItZWFjaAogIChsYW1iZGEgKHJvdykgKGRpc3BsYXkgcm93KSAobmV3bGluZSkpCiAgKHZlY3Rvci0+bGlzdCBjaGVlc2UpKQoobmV3bGluZSkKCihkZWZpbmUtbWVtb2l6ZWQgKHJhdCByIGMpCiAgKGlmIChvciAoPSByIG5yb3dzKSAoPSBjIG5jb2xzKSkgMAogICAgKCsgKHZlY3Rvci1yZWYgKHZlY3Rvci1yZWYgY2hlZXNlIHIpIGMpCiAgICAgICAobWF4IChyYXQgKCsgciAxKSBjKSAocmF0IHIgKCsgYyAxKSkpKSkpCgooZGlzcGxheSAocmF0IDAgMCkpIChuZXdsaW5lKQ==