blob: 37bbfe329ed531b75b8bdf636411ecd7e639ee99 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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)
|
