# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1486992022 0
# Node ID 4a9353c06f2950fa44d0bc7506a94aea474c4d9c
# Parent  04c938e27ef5353199ac76f1c9f8a9a1a2d53314
Problems 15 and 16

diff -r 04c938e27ef5 -r 4a9353c06f29 src/euler.lisp
--- a/src/euler.lisp	Sun Feb 12 13:40:26 2017 +0000
+++ b/src/euler.lisp	Mon Feb 13 13:20:22 2017 +0000
@@ -1,9 +1,31 @@
 (in-package :euler)
 
 ;;;; Utils --------------------------------------------------------------------
-(defun digits (n)
-  "Return how many digits `n` has in base 10."
-  (values (truncate (1+ (log n 10)))))
+(defmacro-driver (FOR var IN-DIGITS-OF integer &optional RADIX (radix 10))
+  "Iterate `var` through the digits of `integer` in base `radix`, low-order first."
+  (let ((kwd (if generate 'generate 'for)))
+    (with-gensyms (i r remaining digit)
+      `(progn
+         (with ,r = ,radix)
+         (with ,i = (abs ,integer))
+         (,kwd ,var :next (if (zerop ,i)
+                            (terminate)
+                            (multiple-value-bind (,remaining ,digit)
+                                (truncate ,i ,r)
+                              (setf ,i ,remaining)
+                              ,digit)))))))
+
+(defun digits (n &optional (radix 10))
+  "Return a fresh list of the digits of `n` in base `radix`."
+  (iterate (for d :in-digits-of n :radix radix)
+           (collect d :at :beginning)))
+
+(defun digits-length (n &optional (radix 10))
+  "Return how many digits `n` has in base `radix`."
+  (if (zerop n)
+    1
+    (values (1+ (truncate (log (abs n) radix))))))
+
 
 (defun definitely-palindrome-p (n)
   "Return whether `n` is a palindrome (in base 10), the slow-but-sure way."
@@ -22,7 +44,7 @@
   ;;   001100 * c
   (cond
     ((zerop n) t)
-    ((and (evenp (digits n))
+    ((and (evenp (digits-length n))
           (not (dividesp n 11))) nil)
     (t (definitely-palindrome-p n))))
 
@@ -59,6 +81,14 @@
            (counting t)))
 
 
+(defun binomial-coefficient (n k)
+  "Return `n` choose `k`."
+  ;; https://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula
+  (iterate (for i :from 1 :to k)
+           (multiply (/ (+ n 1 (- i))
+                        i))))
+
+
 ;;;; Problems -----------------------------------------------------------------
 (defun problem-1 ()
   ;; If we list all the natural numbers below 10 that are multiples of 3 or 5,
@@ -405,6 +435,21 @@
   (iterate (for i :from 1 :below 1000000)
            (finding i :maximizing #'collatz-length)))
 
+(defun problem-15 ()
+  ;; Starting in the top left corner of a 2×2 grid, and only being able to move
+  ;; to the right and down, there are exactly 6 routes to the bottom right
+  ;; corner.
+  ;;
+  ;; How many such routes are there through a 20×20 grid?
+  (binomial-coefficient 40 20))
+
+(defun problem-16 ()
+  ;; 2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
+  ;;
+  ;; What is the sum of the digits of the number 2^1000?
+  (sum (digits (expt 2 1000))))
+
+
 ;;;; Tests --------------------------------------------------------------------
 (def-suite :euler)
 (in-suite :euler)
@@ -423,6 +468,8 @@
 (test p12 (is (= 76576500 (problem-12))))
 (test p13 (is (= 5537376230 (problem-13))))
 (test p14 (is (= 837799 (problem-14))))
+(test p15 (is (= 137846528820 (problem-15))))
+(test p16 (is (= 1366 (problem-16))))
 
 
-; (run! :euler)
+;; (run! :euler)