# [racket] First try with hashes in Racket

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/