# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1487983430 0
# Node ID cf04c88e84dcd4aee765a485bb7a78096155f59b
# Parent  5edac9efd5205ca35293fa3c35ded51693ad736c
Problems 32 and 33

diff -r 5edac9efd520 -r cf04c88e84dc src/euler.lisp
--- a/src/euler.lisp	Wed Feb 22 18:30:09 2017 +0000
+++ b/src/euler.lisp	Sat Feb 25 00:43:50 2017 +0000
@@ -27,6 +27,14 @@
     (values (1+ (truncate (log (abs n) radix))))))
 
 
+(defun digits-to-number (digits)
+  (iterate (with result = 0)
+           (for d :in-whatever digits)
+           (mulf result 10)
+           (incf result d)
+           (finally (return result))))
+
+
 (defun definitely-palindrome-p (n)
   "Return whether `n` is a palindrome (in base 10), the slow-but-sure way."
   (let ((s (format nil "~D" n)))
@@ -717,8 +725,8 @@
   ;; 4, 5, 6, 7, 8 and 9?
   (-<> "0123456789"
     (gathering-vector (:size (factorial (length <>)))
-      (map-permutations #'gather <>))
-    (map-into <> #'parse-integer <>)
+      (map-permutations (compose #'gather #'parse-integer) <>
+                        :copy nil))
     (sort <> #'<)
     (elt <> (1- 1000000))))
 
@@ -900,6 +908,78 @@
       (t (+ (recur (- amount (first coins)) coins)
             (recur amount (rest coins)))))))
 
+(defun problem-32 ()
+  ;; We shall say that an n-digit number is pandigital if it makes use of all
+  ;; the digits 1 to n exactly once; for example, the 5-digit number, 15234, is
+  ;; 1 through 5 pandigital.
+  ;;
+  ;; The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing
+  ;; multiplicand, multiplier, and product is 1 through 9 pandigital.
+  ;;
+  ;; Find the sum of all products whose multiplicand/multiplier/product identity
+  ;; can be written as a 1 through 9 pandigital.
+  ;;
+  ;; HINT: Some products can be obtained in more than one way so be sure to only
+  ;; include it once in your sum.
+  (labels ((split (digits a b)
+             (values (digits-to-number (subseq digits 0 a))
+                     (digits-to-number (subseq digits a (+ a b)))
+                     (digits-to-number (subseq digits (+ a b)))))
+           (check (digits a b)
+             (multiple-value-bind (a b c)
+                 (split digits a b)
+               (when (= (* a b) c)
+                 c))))
+    (-<> (gathering
+           (map-permutations (lambda (digits)
+                               (let ((c1 (check digits 3 2))
+                                     (c2 (check digits 4 1)))
+                                 (when c1 (gather c1))
+                                 (when c2 (gather c2))))
+                             #(1 2 3 4 5 6 7 8 9)
+                             :copy nil))
+      remove-duplicates
+      sum)))
+
+(defun problem-33 ()
+  ;; The fraction 49/98 is a curious fraction, as an inexperienced mathematician
+  ;; in attempting to simplify it may incorrectly believe that 49/98 = 4/8,
+  ;; which is correct, is obtained by cancelling the 9s.
+  ;;
+  ;; We shall consider fractions like, 30/50 = 3/5, to be trivial examples.
+  ;;
+  ;; There are exactly four non-trivial examples of this type of fraction, less
+  ;; than one in value, and containing two digits in the numerator and
+  ;; denominator.
+  ;;
+  ;; If the product of these four fractions is given in its lowest common terms,
+  ;; find the value of the denominator.
+  (labels ((safe/ (a b)
+             (unless (zerop b) (/ a b)))
+           (cancel (digit other digits)
+             (destructuring-bind (x y) digits
+               (remove nil (list (when (= digit x) (safe/ other y))
+                                 (when (= digit y) (safe/ other x))))))
+           (cancellations (numerator denominator)
+             (let ((nd (digits numerator))
+                   (dd (digits denominator)))
+               (append (cancel (first nd) (second nd) dd)
+                       (cancel (second nd) (first nd) dd))))
+           (curiousp (numerator denominator)
+             (member (/ numerator denominator)
+                     (cancellations numerator denominator)))
+           (trivialp (numerator denominator)
+             (and (dividesp numerator 10)
+                  (dividesp denominator 10))))
+    (iterate
+      (with result = 1)
+      (for numerator :from 10 :to 99)
+      (iterate (for denominator :from (1+ numerator) :to 99)
+               (when (and (curiousp numerator denominator)
+                          (not (trivialp numerator denominator)))
+                 (mulf result (/ numerator denominator))))
+      (finally (return (denominator result))))))
+
 
 ;;;; Tests --------------------------------------------------------------------
 (def-suite :euler)
@@ -936,6 +1016,8 @@
 (test p29 (is (= 9183 (problem-29))))
 (test p30 (is (= 443839 (problem-30))))
 (test p31 (is (= 73682 (problem-31))))
+(test p32 (is (= 45228 (problem-32))))
+(test p33 (is (= 100 (problem-33))))
 
 
 ;; (run! :euler)