Re: Euler 14.

Paul Rubin <no.email@nospam.invalid> writes:

It is problem 14 of projecteuler.net .

Here is my solution, maybe not idiomatic CL since I don't write much of
that these days.  It takes about 0.17 sec of user time on my laptop
using sbcl --script, or 1.1 sec with compiled clisp.  It doesn't work
with interpreted clisp because the clisp interpreter has no TRO and so
the tail recursion overflows the stack.  I could rewrite it iteratively
but nah.  A similar C++ version with gcc -O3 takes about 0.03 sec.  I
haven't experimented with changing the size of the memo table or
anything like that. 
================================================================

(defun collatz (n)
  (cond ((oddp n) (1+ (* 3 n)))
        (t (floor n 2))))

(defvar memo (make-array 1000000 :initial-element nil))

(defun clen (n)
  (cond ((= n 1) 1)
        ((<= n 0) 'crash)
        ((and (< n (length memo)) (aref memo n)) (aref memo n))
        (t (let ((a (1+ (clen (collatz n)))))
             (if (< n (length memo))
                 (setf (aref memo n) a))
             a))))

(defun run (&optional (n 1) (mi 0) (ma 0))
    (if (> n 1000000)
      (list mi ma)
      (let ((a (clen n))
            (nn (1+ n)))
        (if (> a ma)
            (run nn n a)
            (run nn mi ma)))))
(print (run))
(terpri)