diff options
| -rw-r--r-- | problem-15.scm | 42 |
1 files changed, 42 insertions, 0 deletions
diff --git a/problem-15.scm b/problem-15.scm new file mode 100644 index 0000000..37bbfe3 --- /dev/null +++ b/problem-15.scm @@ -0,0 +1,42 @@ +;;; +;;; 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) |