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