--- a/src/euler.lisp Wed Feb 22 18:23:39 2017 +0000
+++ b/src/euler.lisp Wed Feb 22 18:30:09 2017 +0000
@@ -880,6 +880,26 @@
(when (= i (digit-power-sum i))
(summing i)))))
+(defun problem-31 ()
+ ;; In England the currency is made up of pound, £, and pence, p, and there are
+ ;; eight coins in general circulation:
+ ;;
+ ;; 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
+ ;;
+ ;; It is possible to make £2 in the following way:
+ ;;
+ ;; 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
+ ;;
+ ;; How many different ways can £2 be made using any number of coins?
+ (recursively ((amount 200)
+ (coins '(200 100 50 20 10 5 2 1)))
+ (cond
+ ((zerop amount) 1)
+ ((minusp amount) 0)
+ ((null coins) 0)
+ (t (+ (recur (- amount (first coins)) coins)
+ (recur amount (rest coins)))))))
+
;;;; Tests --------------------------------------------------------------------
(def-suite :euler)
@@ -915,6 +935,7 @@
(test p28 (is (= 669171001 (problem-28))))
(test p29 (is (= 9183 (problem-29))))
(test p30 (is (= 443839 (problem-30))))
+(test p31 (is (= 73682 (problem-31))))
;; (run! :euler)