PE5.lisp

;;Largest palindrome product
;;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.
;;

(defun number-palindrome-p (x)
  (string-palindrome-p (write-to-string x)))

(defun string-palindrome-p (x)
  (let* ((x-length (length x))
        (head (elt x 0))
        (tail (elt x (1- x-length))))
    (if
      (and
          (eq head tail)
          (> x-length 2))
      (is-palindrome (subseq x 1 (1- x-length)))
      (cond ((eq x-length 1) t)
            ((eq head tail) t)
            (t nil)))))

(defun next-lower-palindrome (x)
  (do ((x (1- x) (1- x)))
      ((number-palindrome-p x) x)))

(defun find-factors (x)
  (loop for n from 1 to (1- x)
        if (zerop (mod x n))
          collect n into f-list
        finally (return (nreverse (remove-if (lambda (x) (or (< x 100) (> x 999))) f-list)))))

(defun product-factors-p (lst x)
  (if (null (member x (mapcan (lambda (y) (mapcar (lambda (z) (* y z)) lst)) lst))) nil t))

(defun answer ()
  (do ((x (next-lower-palindrome (* 999 999)) (next-lower-palindrome x)))
    ((product-factors-p (find-factors x) x) x))) ; 906609


;; Freaky Fast

(defun euler4 (&optional (n 999))
  (let ((largest 0))
    (do ((i 1 (+ i 1))) ((> i n) largest)
      (do ((j 1 (+ j 1))) ((> j n) 'done)
        (if (and (> (* i j) largest)
                 (string= (format nil "~A" (* i j))
                          (reverse (format nil "~A" (* i j)))))
          (setf largest (* i j)))))))