[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>