Thursday, October 9, 2014

Project Euler Problem 4 Common Lisp

Project Euler Problem 4

Solutions I've seen for this problem use 2 loops that will multiply every number in both loops.  For example, 2 loops with numbers from 4 to 1:

   4  3 2 1
4 16 12 8 4
3 12  9 6 3
2  8  6 4 2
1  4  3 2 1

The two loops in the below solution cuts this almost in half.  For example:

   4  3 2 1
4 16 12 8 4
3     9 6 3
2       4 2
1         1

Now the code:

(defun digits-to-list (x &optional (lst nil))
  (multiple-value-bind (a b)
      (truncate x 10)
    (if (zerop a)
      (cons b lst)
      (digits-to-list a (cons b lst)))))

(defun problem4 ()
  (loop for i from 999 downto 100
        maximizing (loop for j from i downto 100
                         for mult = (* i j)
                         for lst = (digits-to-list mult)
                         if (equal lst (reverse lst))
                         maximizing mult)))

No comments:

Post a Comment