Simple Lisp Program Causing Computer To Hang

Question

NOTE: I've closed this question because it turns out that there was nothing wrong with my program that should have caused it to behave as it did, and it was likely a compiler bug or something.

I'm also now using the style that John recommended, it looks much nicer than the code I posted here.

- - -- --- ----- -------- -------------

I've just started playing around with Lisp, and have been using Project Euler as a source of simple activities to practice with. I'm currently working on problem 4:

Find the largest palindrome made from the product of two 3-digit numbers.

I've completed code that should complete the task as requested, but whenever I run it (using the Steel Bank Common Lisp compiler) my computer starts to hang. Here's my code.

(defun isPalindromic (n)
 (let
  ((stringed (format nil "~D" n)))
  (string= stringed (reverse stringed))))

(defun euler004 ()
 (let
  ((start 100) ; all 3-digit numbers...
   (limit 999) ; fall within this range
   (largest 0))

  (do
   ((x start (1+ x)))

   ((> x limit))

   (do
    ((y start (1+ y)))

    ((> y limit))

    (let
     ((product (* x y)))

     (if
      (and
       (> product largest)      ; cheap?
       (isPalindromic product)) ; expensive?

      (setq largest product)))))

  (return-from euler004 largest)))

(print (euler004))

If anyone could help me find the problem I would appreciate it. I would also appreciate any remarks you might have regarding style or best practices for Lisp code as I am largely uninformed about them and have probably made some fairly terrible mistakes.

Thank you.

Answer 1

I just ran your program in clisp and it printed 906609 after about four seconds. As I don't have SBCL on this machine I don't know what the problem is, but it doesn't seem to be in your code.

Oh, and the answer is correct, too - Project Euler accepted it. Bravo!

Answer 2

Works fine here under SBCL 1.0.11.debian.

Answer 3

Well, that's good to know. I'll give clisp a try. Thank you.

Answer 4

One minor lisp styling note: I think you'll find the code easier to read if (unless it makes the line too long), keep the first argument to the function on the same line of the function, and either align the remaining argument with the first arguments or keep them on the same line.

 (if (and (> product 
             largest)      ; cheap?
          (isPalindromic product)) ; expensive?
     (setq largest product)))))

I think your choice of lisp constructs is just fine. :-)

You might consider counting down instead of up in an ordering that would let you stop early if you find a palendrome instead of having to calculate every product, but you probably already knew that and was just writing it the fastest way to solve the problem.

Answer 5

Works for me.

* (time (euler004))

Evaluation took:
  0.753 seconds of real time
  0.752048 seconds of total run time (0.748047 user, 0.004001 system)
  [ Run times consist of 0.044 seconds GC time, and 0.709 seconds non-GC time. ]
  99.87% CPU
  809,527,673 processor cycles
  145,426,336 bytes consed

906609


$ sbcl --version
SBCL 1.0.18.27

Answer 6

Peter Norvig wrote a guide on how to correctly format lisp code, you may want to take a look.

Tutorial on Good Lisp Programming Style (PDF link)

Answer 7

Your version runs fine here also.

Here is a version rewritten in more idiomatic lisp style. There are of course many ways to do this. This one is written for clarity and not speed, and to mostly follow your approach, not for speed. Two versions

(defun palindrome-p (string)  ; idiomatic naming of predicate (-p) function
  (not (mismatch string (reverse string)))) ;; could use your string= approach too

(defun euler004 ()  ;simple nested loop version
  (loop for i from 100 below 1000 maximizing
    (loop for j from 100 below 1000
      for prod = (* i j)
      when (palindrome-p (prin1-to-string prod))
      maximize prod)))

(defun euler004b () ;add test to avoid making strings where unneeded
  (loop with max = 0
     for i from 100 below 1000
     do (loop for j from 100 below 1000
           for prod = (* i j)
           when (and (> prod max) (palindrome-p (prin1-to-string prod)))
           do (setf max prod))
     finally (return max)))

Hope that helps. Noting wrong with do, of course, but your layout is unusual and loop (or iterate or whatever) has some nice support for this sort of thing.