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