# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1460249917 0
# Node ID 5dc80bffbeccbee9403ea070e94627c39c3a8ac0
# Parent  a0f4943508965853a7cab0086e983c5266553976
Problem 4

diff -r a0f494350896 -r 5dc80bffbecc euler.lisp
--- a/euler.lisp	Sun Apr 10 00:58:30 2016 +0000
+++ b/euler.lisp	Sun Apr 10 00:58:37 2016 +0000
@@ -1,5 +1,33 @@
 (in-package #:euler)
 
+;;;;
+(defun digits (n)
+  "Return how many digits `n` has in base 10."
+  (values (truncate (1+ (log n 10)))))
+
+(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)))
+    (string= s (reverse s))))
+
+(defun palindrome-p (n)
+  "Return whether `n` is a palindrome (in base 10)."
+  (assert (>= n 0) (n) "~A must be a non-negative integer" n)
+  ;; All even-length base-10 palindromes are divisible by 11, so we can shortcut
+  ;; the awful string comparison. E.g.:
+  ;;
+  ;;   abccba =
+  ;;   100001 * a +
+  ;;   010010 * b +
+  ;;   001100 * c
+  (cond
+    ((zerop n) t)
+    ((and (evenp (digits n))
+          (not (dividesp n 11))) nil)
+    (t (definitely-palindrome-p n))))
+
+
+;;;; Problems
 (defun problem-1 ()
   ;; If we list all the natural numbers below 10 that are multiples of 3 or 5,
   ;; we get 3, 5, 6 and 9. The sum of these multiples is 23.
@@ -30,3 +58,16 @@
   ;;
   ;; What is the largest prime factor of the number 600851475143 ?
   (apply #'max (prime-factorization 600851475143)))
+
+(defun problem-4 ()
+  ;; A palindromic number reads the same both ways. The largest palindrome made
+  ;; from the product of two 2-digit numbers is 9009 = 91 × 99.
+  ;;
+  ;; Find the largest palindrome made from the product of two 3-digit numbers.
+  (let ((result (list)))
+    (loop :for i :from 0 :to 999
+          :do (loop :for j :from 0 :to 999
+                    :for product = (* i j)
+                    :when (palindrome-p product)
+                    :do (push product result)))
+    (apply #'max result)))