summaryrefslogtreecommitdiff
path: root/problem-15.scm
diff options
context:
space:
mode:
Diffstat (limited to 'problem-15.scm')
-rw-r--r--problem-15.scm42
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)