Lazy Sequences that "Look Ahead" for Project Euler Problem 14
- by ivar
I'm trying to solve Project Euler Problem 14 in a lazy way. Unfortunately, I may be trying to do the impossible: create a lazy sequence that is both lazy, yet also somehow 'looks ahead' for values it hasn't computed yet.
The non-lazy version I wrote to test correctness was:
(defn chain-length [num]
(loop [len 1
n num]
(cond
(= n 1) len
(odd? n) (recur (inc len) (+ 1 (* 3 n)))
true (recur (inc len) (/ n 2)))))
Which works, but is really slow. Of course I could memoize that:
(def memoized-chain
(memoize
(fn [n]
(cond
(= n 1) 1
(odd? n) (+ 1 (memoized-chain (+ 1 (* 3 n))))
true (+ 1 (memoized-chain (/ n 2)))))))
However, what I really wanted to do was scratch my itch for understanding the limits of lazy sequences, and write a function like this:
(def lazy-chain
(letfn [(chain [n] (lazy-seq
(cons (if (odd? n)
(+ 1 (nth lazy-chain (dec (+ 1 (* 3 n)))))
(+ 1 (nth lazy-chain (dec (/ n 2)))))
(chain (+ n 1)))))]
(chain 1)))
Pulling elements from this will cause a stack overflow for n2, which is understandable if you think about why it needs to look 'into the future' at n=3 to know the value of the tenth element in the lazy list because (+ 1 (* 3 n)) = 10.
Since lazy lists have much less overhead than memoization, I would like to know if this kind of thing is possible somehow via even more delayed evaluation or queuing?
