Sunday, September 11, 2011

Exploring Common Lisp: Project Euler Number 8 in Common Lisp (Neophyte Version)

There isn't really much I can add about this example. The goal is to find the largest product of any consecutive digits given a 1000 digit number. I implemented the first approach that came to mind; I went with a large loop to iterate through the 1000 digits and then an inner loop to extract that digits we are going to use in our calculation. The key built-in lisp functions are "loop" and "reduce". If you are not used to a lisp programming language, a C version of this solution is provided.

;;
;; euler8.lisp (modify to find the "correct" solution)
;; Find the greatest product of five ;; consecutive digits in the 1000-digit number;;
;; [1] http://www.unixuser.org/~euske/doc/cl/loop.html
(defparameter *large-num* 
"73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843")

(defun find-great-product ()
  "Use reduce to find the product of a list of 5 digits out of the
 larger 1000 digit number"
  (let ((n (length *large-num*)) (m 0))
    (loop for i from 0 to (- n 5)
          for x = (let ((vals (loop for z from i to (+ i 4)
                                    for b = (digit-char-p (char *large-num* z))
                                    collect (if b b 1))))
                    (reduce #'* vals))
          do (when (> x m) (setf m x)))
    m))
(defun main ()
  (format t "Start~%")
  (print (find-great-product))
  (format t "Done~%"))
(main)

1 comment:

Scott said...

Run the product until you hit a zero, then compare to x; if product is greater than x then x = product; start again after the zero(es); when you get to the end you're done.

Right?