To get into the swing of The Lisp Way, I've been working my way
through a few of the problems on the Project Euler website. Here's the
(Scheme) code I wrote for problem 14:
;The following iterative sequence is defined for the set of positive
integers:
;
;n n/2 (n is even)
;n 3n + 1 (n is odd)
;
;Using the rule above and starting with 13, we generate the following
sequence:
;13 40 20 10 5 16 8 4 2 1
;It can be seen that this sequence (starting at 13 and finishing at 1)
contains 10 terms. Although it has not been proved yet (Collatz
Problem), it is ;thought that all starting numbers finish at 1.
;Which starting number, under one million, produces the longest chain?
;
;NOTE: Once the chain starts the terms are allowed to go above one
million.
(define (Collatz n)
(if (odd? n)
(+ (* n 3) 1)
(/ n 2)))
(define (countColl n v)
(if (> (safe-ref v n) 0)(safe-ref v n)
(safe-set! v n (let loop ([count 1] [coll (Collatz n)])
(if (eqv? coll 1)
count
(if (> (safe-ref v coll) 0)
(+ (- count 1) (safe-ref v coll))
(loop (+ count 1) (Collatz coll)))
)))))
(define (safe-ref v k)
(if (>= k (vector-length v)) 0
(vector-ref v k)))
(define (safe-set! v k obj)
(if (< k (vector-length v))
(vector-set! v k obj))obj)
;(countColl 3)
;(countColl 4)
(define (tester n)
(let ([v (make-vector n 0)])
(let loop ([count 1] [maxcount 3] [maxColl 0])
(if (< count n)
(loop (+ count 1) (if (> (countColl count v) maxColl) count
maxcount) (max maxColl (countColl count v)))
(printf "count: ~a maxcount: ~a maxColl: ~a~n" count maxcount
maxColl)))))
(tester 1000000)
Comments welcome. Note: even though this is Scheme code, I post it
here, since I've been lurking here for a while and know the players,
somewhat. And yes, the memoization was probably a premature
optimization, as I didn't run the non-memoized version first.
In article
<····································@y22g2000prd.googlegroups.com>,
mayson <·······@gmail.com> wrote:
> To get into the swing of The Lisp Way, I've been working my way
> through a few of the problems on the Project Euler website. Here's the
> (Scheme) code I wrote for problem 14:
>
> ;The following iterative sequence is defined for the set of positive
> integers:
> ;
> ;n n/2 (n is even)
> ;n 3n + 1 (n is odd)
> ;
> ;Using the rule above and starting with 13, we generate the following
> sequence:
> ;13 40 20 10 5 16 8 4 2 1
>
> ;It can be seen that this sequence (starting at 13 and finishing at 1)
> contains 10 terms. Although it has not been proved yet (Collatz
> Problem), it is ;thought that all starting numbers finish at 1.
>
> ;Which starting number, under one million, produces the longest chain?
> ;
> ;NOTE: Once the chain starts the terms are allowed to go above one
> million.
> (define (Collatz n)
> (if (odd? n)
> (+ (* n 3) 1)
> (/ n 2)))
> (define (countColl n v)
> (if (> (safe-ref v n) 0)(safe-ref v n)
> (safe-set! v n (let loop ([count 1] [coll (Collatz n)])
> (if (eqv? coll 1)
> count
> (if (> (safe-ref v coll) 0)
> (+ (- count 1) (safe-ref v coll))
> (loop (+ count 1) (Collatz coll)))
> )))))
> (define (safe-ref v k)
> (if (>= k (vector-length v)) 0
> (vector-ref v k)))
> (define (safe-set! v k obj)
> (if (< k (vector-length v))
> (vector-set! v k obj))obj)
>
> ;(countColl 3)
> ;(countColl 4)
> (define (tester n)
> (let ([v (make-vector n 0)])
> (let loop ([count 1] [maxcount 3] [maxColl 0])
> (if (< count n)
> (loop (+ count 1) (if (> (countColl count v) maxColl) count
> maxcount) (max maxColl (countColl count v)))
> (printf "count: ~a maxcount: ~a maxColl: ~a~n" count maxcount
> maxColl)))))
> (tester 1000000)
>
> Comments welcome. Note: even though this is Scheme code, I post it
> here, since I've been lurking here for a while and know the players,
> somewhat. And yes, the memoization was probably a premature
> optimization, as I didn't run the non-memoized version first.
If you have been lurking, then you know that you'll get
Common Lisp code back. ;-)
Remarks:
* try to separate the logic from the optimization
* when pasting Lisp code make sure that your newsreader does not
break the lines
First the simple implementation:
(defparameter *max-n* 1000000)
(defun collatz (n)
(if (oddp n)
(+ (* n 3) 1)
(/ n 2)))
(defun collatz-length (n)
(1+ (loop for i = n then (collatz i)
while (> i 1)
count i)))
(defun euler-14 ()
(loop with max = 1 and max-length = 1
for i from 1 upto *max-n*
for length = (collatz-length i)
when (> length max-length)
do (setf max i max-length length)
finally (return (values max max-length))))
;;; ======================================
; now with memoizing
(defparameter *max-n* 1000000)
(defun memoize (f n)
(let* ((n-value-symbol '#:no-value)
(results (make-array (1+ n) :initial-element n-value-symbol)))
(lambda (arg)
(if (<= 0 arg n)
(let ((memoized-result (aref results arg)))
(if (eq memoized-result n-value-symbol)
(setf (aref results arg) (funcall f arg))
memoized-result))
(funcall f arg)))))
(defmacro defmemoize (name function n)
`(setf (symbol-function ',name)
(memoize (function ,function) ,n)))
(defun collatz (n)
(if (oddp n)
(+ (* n 3) 1)
(/ n 2)))
(defmemoize collatz-m collatz *max-n*)
(defun collatz-length (n)
(1+ (loop for i = n then (collatz-m i)
while (> i 1)
count i)))
(defmemoize collatz-length-m collatz-length *max-n*)
(defun euler-14 ()
(loop with max = 1 and max-length = 1
for i from 1 upto *max-n*
for length = (collatz-length-m i)
when (> length max-length)
do (setf max i max-length length)
finally (return (values max max-length))))
--
http://lispm.dyndns.org/
On Jul 2, 3:44 am, mayson <·······@gmail.com> wrote:
> (define (Collatz n)
> (define (countColl n v)
What do "Collatz" and "Coll" mean? I would call these
functions "next-val" for "next value" and "num-iters"
or "count-iters" for "number of iterations" or
"count iterations". The Euler site is down right now,
so I can't check to see if it explains the names.
> (if (> (safe-ref v n) 0)(safe-ref v n)
> (safe-set! v n ...)
I would separate this nonfunctional code from the
functional iteration counting (put it in tester).
> ... (let loop ([count 1] [coll (Collatz n)])
> ...
> (+ (- count 1) (safe-ref v coll))
I don't think you have to backtrack on count:
> ... (let loop ([count 0] [coll n])
> ...
> (+ count (safe-ref v coll))
> (let loop ([count 1] [maxcount 3] [maxColl 0])
The name "count" is confusing here. You're not really
counting initial values:
> (let loop ([n 2] [n-max 1] [max-iters 3])
> (loop (+ count 1)
> (if (> (countColl count v) maxColl) count maxcount)
> (max maxColl (countColl count v)))
^^^^^^^^^^^^^^^^^^^
You definitely don't want to count the iterations twice:
> (let num-iters (count-iters n v)
> (setf (aref v n) num-iters)
> (if (> num-iters max-iters)
> (loop (+ n 1) n num-iters)
> (loop (+ n 1) n-max max-iters)
Also, I know you Schemers are in love with recursion, but I
would update n-max and max-iters (your maxcount and maxColl)
explicitly instead of making them function parameters.
--Dan
------------------------------------------------
http://www.prairienet.org/~dsb/
cl-match: expressive pattern matching in Lisp
http://common-lisp.net/project/cl-match/
------------------------------------------------
;;CL pseudo-Scheme:
(defun next-val (n) (if (oddp n) (+ (* n 3) 1) (/ n 2)))
(defun safe-ref (v k) (if (>= k (length v)) 0 (aref v k)))
(defun num-iters (n0 v)
(labels ((looop (num-iters n)
(if (= n 1)
num-iters
(if (> (safe-ref v n) 0)
(+ num-iters (safe-ref v n))
(looop (+ num-iters 1) (next-val n))))))
(looop 0 n0)))
(defun max-iters (n-total)
(let ((v (make-array n-total :initial-element 0)))
(labels
((looop (n n-max max-iters)
(if (= n n-total)
(format t "n-total: ~a n-max: ~a max iterations: ~a~%"
n n-max max-iters)
(let ((num-iters (num-iters n v)))
(setf (aref v n) num-iters)
(if (> num-iters max-iters)
(looop (+ n 1) n num-iters)
(looop (+ n 1) n-max max-iters))))))
(looop 2 1 3))))
(max-iters 1000000)
Google groups formatting is too smart for its own good.
On Jul 3, 12:12 am, danb <·········@gmail.com> wrote:
> I don't think you have to backtrack on count:
> > ... (let loop ([count 0] [coll n])
> > ...
> > (+ count (safe-ref v coll))
*** new section ***
> > (let loop ([count 1] [maxcount 3] [maxColl 0])
>
> The name "count" is confusing here. You're not really
> counting initial values:
>
> > (let loop ([n 2] [n-max 1] [max-iters 3])
*** new section ***
> > (if (> (countColl count v) maxColl) count maxcount)
> > (max maxColl (countColl count v)))
> ^^^^^^^^^^^^^^^^^^^
>
> You definitely don't want to count the iterations twice
Well, I guess countColl returns immediately on the second
call, so it's not so bad as long as you keep it that way and
you remember how it works. But I would still make countColl
(my count-iters) purely functional and call it only once.
It's less confusing to people who read your code.
--Dan
------------------------------------------------
http://www.prairienet.org/~dsb/
cl-match: expressive pattern matching in Lisp
http://common-lisp.net/project/cl-match/