[racket] First try with hashes in Racket
Hi Neil,
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:
> (define ht (make-hash (list '(1 . 1))))
> (collatz-length ht 999999)
259
> (collatz-length ht 999998)
259
-Joe
On Mon, Apr 2, 2012 at 9:40 PM, Neil Van Dyke <neil at neilvandyke.org> wrote:
> Joe Gilray wrote at 04/03/2012 12:00 AM:
>
>> *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.
>>
>> Any more help?
>>
>
> Here's an implementation without mutations. It's simple brute-force with
> memoization (I'm not aware of an algorithmic or numeric shortcut).
>
> Note that it uses immutable hashes functionally, passing "memo" hashes
> into and out of every place that we would want to update the memoization.
>
> 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".
>
> #lang racket/base
>
> (define (f n)
> (if (even? n)
> (/ n 2)
> (+ 1 (* 3 n))))
>
> (define (get-terms-count memo n)
> ;; Note: We don't have to detect cycles, at least not for max-n 999,999
> (cond ((hash-ref memo n #f) => (lambda (n-steps)
> (values memo n-steps)))
> (else (let*-values (((next-n) (f n))
> ((memo next-n-steps) (get-terms-count memo
> next-n))
> ((n-steps) (+ 1 next-n-steps)))
> (values (hash-set memo n n-steps)
> n-steps)))))
>
> (define (euler-14 (max-n (- #e1e6 1)))
> (let loop ((answer-n-list '(1))
> (answer-terms-count 1)
> (n max-n)
> (memo #hash((1 . 1))))
> (if (= 1 n)
> (values answer-n-list answer-terms-count)
> (let-values (((memo n-terms-count) (get-terms-count memo n)))
> (cond ((< n-terms-count answer-terms-count)
> (loop answer-n-list
> answer-terms-count
> (- n 1)
> memo))
> ((> n-terms-count answer-terms-count)
> (loop (cons n '())
> n-terms-count
> (- n 1)
> memo))
> (else ; (= n-terms-count answer-terms-count)
> (error 'euler-14 "seems to be unreachable for max-n
> 999,999")
> (loop (cons n answer-n-list)
> answer-terms-count
> (- n 1)
> memo)))))))
>
> (euler-14)
>
>
> Neil V.
>
> --
> http://www.neilvandyke.org/
> ____________________
> Racket Users list:
> http://lists.racket-lang.org/**users <http://lists.racket-lang.org/users>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120403/2c7592c4/attachment.html>