Add Problem 15 solution.

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)