Hi Neil,<div><br></div><div>Thanks for the educational code. �I had to remove the error line in your code as there are more than one number < 1000000 with the same collatz length... in fact it happens right away:</div><div>
<br></div><div><div>> (define ht (make-hash (list '(1 . 1))))</div><div>> (collatz-length ht 999999)</div><div>259</div><div>> (collatz-length ht 999998)</div><div>259</div><div><br></div><div>-Joe</div><div>
<br></div><br><div class="gmail_quote">On Mon, Apr 2, 2012 at 9:40 PM, Neil Van Dyke <span dir="ltr"><<a href="mailto:neil@neilvandyke.org">neil@neilvandyke.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Joe Gilray wrote at 04/03/2012 12:00 AM:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
*The bad news*: it still feels a little clunky. �It has a lot of imperative statements and the memoization in the hash table feels too much like a side-effect to me.<br>
<br>
Any more help?<br>
</blockquote>
<br>
Here's an implementation without mutations. �It's simple brute-force with memoization (I'm not aware of an algorithmic or numeric shortcut).<br>
<br>
Note that it uses immutable hashes functionally, passing "memo" hashes into and out of every place that we would want to update the memoization.<br>
<br>
Note also that I originally had "answer-n-list" to record multiple "n" having the same term-count, but then I added the "error" form to verify that this algorithm never has more than one "n" in "answer-n-list".<br>
<br>
#lang racket/base<br>
<br>
(define (f n)<br>
�(if (even? n)<br>
� � �(/ n 2)<br>
� � �(+ 1 (* 3 n))))<br>
<br>
(define (get-terms-count memo n)<br>
�;; Note: We don't have to detect cycles, at least not for max-n 999,999<br>
�(cond ((hash-ref memo n #f) => (lambda (n-steps)<br>
� � � � � � � � � � � � � � � � � (values memo n-steps)))<br>
� � � �(else (let*-values (((next-n) � � � � � �(f n))<br>
� � � � � � � � � � � � � �((memo next-n-steps) (get-terms-count memo next-n))<br>
� � � � � � � � � � � � � �((n-steps) � � � � � (+ 1 next-n-steps)))<br>
� � � � � � � �(values (hash-set memo n n-steps)<br>
� � � � � � � � � � � �n-steps)))))<br>
<br>
(define (euler-14 (max-n (- #e1e6 1)))<br>
�(let loop ((answer-n-list � � �'(1))<br>
� � � � � � (answer-terms-count 1)<br>
� � � � � � (n � � � � � � � � �max-n)<br>
� � � � � � (memo � � � � � � � #hash((1 . 1))))<br>
� �(if (= 1 n)<br>
� � � �(values answer-n-list answer-terms-count)<br>
� � � �(let-values (((memo n-terms-count) (get-terms-count memo n)))<br>
� � � � �(cond ((< n-terms-count answer-terms-count)<br>
� � � � � � � � (loop answer-n-list<br>
� � � � � � � � � � � answer-terms-count<br>
� � � � � � � � � � � (- n 1)<br>
� � � � � � � � � � � memo))<br>
� � � � � � � �((> n-terms-count answer-terms-count)<br>
� � � � � � � � (loop (cons n '())<br>
� � � � � � � � � � � n-terms-count<br>
� � � � � � � � � � � (- n 1)<br>
� � � � � � � � � � � memo))<br>
� � � � � � � �(else ; (= n-terms-count answer-terms-count)<br>
� � � � � � � � (error 'euler-14 "seems to be unreachable for max-n 999,999")<br>
� � � � � � � � (loop (cons n answer-n-list)<br>
� � � � � � � � � � � answer-terms-count<br>
� � � � � � � � � � � (- n 1)<br>
� � � � � � � � � � � memo)))))))<br>
<br>
(euler-14)<div class="HOEnZb"><div class="h5"><br>
<br>
Neil V.<br>
<br>
-- <br>
<a href="http://www.neilvandyke.org/" target="_blank">http://www.neilvandyke.org/</a><br>
____________________<br>
�Racket Users list:<br>
�<a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/<u></u>users</a><br>
</div></div></blockquote></div><br></div>