;;;
;;; Problem 15: Lattice paths
;;;

;;; https://projecteuler.net/problem=15

(define (memoize proc)
  "Return a memoizing version of PROC."
  (let ((cache (make-hash-table)))
    (lambda args
      (let ((results (hash-ref cache args)))
        (if results
            (apply values results)
            (let ((results (call-with-values (lambda ()
                                               (apply proc args))
                             list)))
              (hash-set! cache args results)
              (apply values results)))))))

(define (lattice-path-count grid-size)
  (define (end? x)
    (= x grid-size))

  (define (out-of-bounds? n)
    (> n grid-size))

  (define count
    (memoize
     (lambda (x y)
       (cond
        ((and (end? x) (end? y))
         1)
        ((or (out-of-bounds? x)
             (out-of-bounds? y))
         0)
        (else
         (+ (count (1+ x) y)
            (count x (1+ y))))))))

  (count 0 0))

(lattice-path-count 20)