# 5edac9efd520

`Problem 31`
author Steve Losh Wed, 22 Feb 2017 18:30:09 +0000 793042f215fb cf04c88e84dc (none) src/euler.lisp

## Changes

```--- 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)```