2 files changed, 72 insertions, 0 deletions
diff --git a/coin-sums/cs-test.scm b/coin-sums/cs-test.scm
new file mode 100644
index 0000000..30fe65c
--- /dev/null
+++ b/coin-sums/cs-test.scm
@@ -0,0 +1,45 @@
+;; -*- compile-command: "guile -L . cs-test.scm"; -*-
+(use-modules (srfi srfi-64)
+             (cs))
+
+
+(test-begin "harness")
+
+(define den '(1))
+
+(test-equal "make one from ones"
+  '(1)
+  (cs 1 den))
+
+(test-equal "make two from ones"
+  '(1 1)
+  (cs 2 den))
+
+(set! den '(1 2))
+
+(test-equal "make one from ones, twos"
+  '(1)
+  (cs 1 den))
+
+(test-equal "make two from ones, twos"
+  '(1 2)
+  (cs 2 den))
+
+(set! den '(2 3 5))
+
+(test-equal "make 3 from twos, threes, fives"
+  '(0 1 1)
+  (cs 3 den))
+
+(test-equal "make 5 from twos, threes, fives"
+  '(0 1 1 1 2)
+  (cs 5 den))
+
+(set! den '(1 2 5 10 20 50 100 200))
+
+(test-equal "make 8 from pence"
+  '(1 2 2 3 4 5 6 7 8 11 12 15 16)
+  (cs 13 den))
+
+
+(test-end "harness")
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)))))