# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1487788209 0
# Node ID 5edac9efd5205ca35293fa3c35ded51693ad736c
# Parent  793042f215fb102a250f164430156fa9c07e89c5
Problem 31

diff -r 793042f215fb -r 5edac9efd520 src/euler.lisp
--- 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)