Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Paul Rubin <no.email@nospam.invalid>
Newsgroups: comp.lang.lisp
Subject: Re: Euler 14.
Date: Thu, 25 Jul 2024 11:28:23 -0700
Organization: A noiseless patient Spider
Lines: 38
Message-ID: <87o76lcomw.fsf@nightsong.com>
References: <v34fp4$iunh$1@dont-email.me> <v7p00g$1b339$3@dont-email.me>
	<87h6cf9711.fsf@nightsong.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Thu, 25 Jul 2024 20:28:24 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="a89df0e331107fdc444e94bb37ae2dd9";
	logging-data="2528263"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+pvXPG737bt6q1LyGBfaC5"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux)
Cancel-Lock: sha1:qUnRcHnl1aDP8wwihn2pBzZx/IY=
	sha1:+JMB9qrp99OJMRL7YK5+ebh2+lA=
Bytes: 2287

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)