Closure, coin sums, & number spiral generator

1 files changed, 27 insertions, 0 deletions

diff --git a/coin-sums/cs.scm b/coin-sums/cs.scm
new file mode 100644
index 0000000..1df83e9
--- /dev/null
+++ b/coin-sums/cs.scm
@@ -0,0 +1,27 @@
+(define-module (cs)
+  #:export (cs))
+
+(define (cs limit denominations)
+  "Given DENOMINATIONS of available coins,
+calculates the total number of different coins
+which combine to LIMIT worth."
+
+  (define (count-coins coins ut)
+    "Calculates the total of combinations with
+the lowest coin denomination first, then recursively
+adds coins of increasing worth, indexing previous results.
+This is the dynamic programming approach."
+    (if (null? coins)
+        ut
+        (let ((coin (car coins)))
+          (for-each (lambda (a)
+                      (vector-set! ut a (+ (vector-ref ut a)
+                                           (vector-ref ut (- a coin)))))
+                    (iota (- (1+ limit) coin) coin 1))
+          (count-coins (cdr coins) ut))))
+
+  (let ((ut (make-vector (1+ limit) 0)))
+    (vector-set! ut 0 1)
+    (cdr (vector->list (count-coins
+                        (filter (lambda (x) (>= limit x)) denominations)
+                        ut)))))