Lazy Sequences that "Look Ahead" for Project Euler Problem 14

Question

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 n>2, 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?

Answer 1

A seq "looking into the future"

An example of a funky seq looking into the future might look like this:

(def funky-seq
     (let [substrate (atom ())]
       (letfn [(funk [n] (delay (if (odd? n) n @(nth @substrate (inc n)))))]
         (reset! substrate (map funk (range))))
       (map deref @substrate)))

user> (take 10 funky-seq)
(1 1 3 3 5 5 7 7 9 9)

(A cookie to whoever makes this simpler without breaking it. :-))

Of course if determining the value of an element might involve looking at a "future" element which itself depends on a further element which calls for the computation of a still more distant element..., the catastrophe cannot be helped.

Euler 14

The fundamental problem with the scheme of "looking into the future" the code from the question attempts to employ aside, this approach doesn't really solve the problem, because, if you decide to start from 1 and go upwards, you need to take branching into account: a 10 in a Collatz chain might be arrived at through the application of either rule (the n / 2 rule applied to 20 or the 3n + 1 rule starting from 3). Also, if you wish to build your chains upward, you should reverse the rules and either multiply by 2 or subtract 1 and divide by 3 (applying, at each step, that rule which produces an integer -- or possibly both if both do).

Of course you could build a tree, rather than a lazy list, but that wouldn't look anything like the code sketch in the question and I'd expect you to end up ultimately memoizing the thing.

The above is to be qualified with the remark that you might have a conjecture as to which "chain building rule" is likely to generate the longest chain starting from 1 while having the final entry stay below the given limit. If that is the case, you should probably prove it correct and then implement it directly (through loop / recur starting at 1); without a proof, you can't really claim to have solved the problem.

Answer 2

The following gives me a lazy sequence of collatz values. On microbenchmarks on my machine, it mildly beats the memoized solution. On the downside, it also recurses too deeply to find 1 million collatz chain lengths, and the stack overflows somewhere between the 100,000th and 1,000,000th element, but that could be solved with a little work and recur.

 (defn collatz [n cache]
   (if-let [v (cache n)]
     [v cache]
     (let [[p cache] (if (odd? n)
                       (collatz (+ 1 (* 3 n)) cache)
                       (collatz (/ n 2) cache))]
       [(inc p) (assoc cache n (inc p))])))

 (def lazy-collatz
      (map first (iterate (fn [[v cache n]]
                            (concat (collatz n cache) [(inc n)]))
                          [1 {1 1} 2])))

Yet, it's still not what I wanted: this same functionality without the hashmap. Thinking about Michal's excellent comment and the concept of building a recursive tree, I guess what I wanted here was not a lazy sequence, but a lazy recursive datastructure of some sort, probably a tree. Do such dataflow techniques exist?

My original idea was to build chains of 'delays' from the unknown value (n) that continue to recurse until they hit a known number (like 1), and then unwind, populating the lazy datastructure with actual values as the recursion unwinds. If we think of a lazy sequence as being a lazy linked list, what I wanted was a lazy infinite length vector or tree that would find out its data dependencies automatically using the Collatz rule. A hashmap sufficed for this problem, but it is in some sense only an approximation of what I wanted: a lazy dataflow vector with a rule applied over how to populate the elements in the vector.

Extra Hard Challenge: Can anybody think of a way to easily represent such a lazy tree/vector without using a hashmap?

Answer 3

I think iterate and take-while could be of some help (although this code doesn't look into the future):

(defn next-collatz [n]
  (cond
    (= n 1) 1
    (odd? n) (+ 1 (* 3 n))
    true (/ n 2)))

(defn collatz-seq [n]
  (iterate next-collatz n))

(defn collatz [n]
    (take-while #(not (= % 1)) (collatz-seq n)))

user> (collatz 100)
=> (100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2)