Lazy sequences that "look to the future" for Project Euler Problem 14

Question

I am trying to solve Project Euler Problem 14 in a lazy way. Unfortunately, I can try to do the impossible: create a lazy sequence that is lazy, but also somehow "looks to the future" at values ​​that it has not yet calculated.

The non-lazy version that I wrote for validation 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 very slowly. Of course, I could remember 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 the itch to understand 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 items from this will lead to a stack overflow for n> 2, which is understandable if you are thinking about why he needs to look “into the future” with n = 3 in order to find out the value of the tenth item in the lazy list because (+ 1 ( * 3 n)) = 10.

Since lazy lists have far less overhead than memories, I would like to know if this is possible, perhaps through an even later evaluation or queues?

Answer 1

The following is a lazy sequence of collatz values. On micro-objects on my car, he gently beats the memoir solution. On the other hand, it is also recalculated too much to find 1 million chain lengths, and the stack overflows somewhere between 100,000 and 1,000,000th element, but this can 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]))) 

However, this is still not what I wanted: the same functionality without hashmap. Reflecting on Michal’s remark and the concept of constructing a recursive tree, I assume that I wanted here not a lazy sequence, but a lazy recursive data structure, possibly a tree. Are there any data flow methods?

My initial idea was to build chains of “delays” from an unknown value (n) that continue to recurse until they hit a known number (e.g. 1), and then unwind, filling in a lazy data structure with actual values ​​as recursion spins. If we think of a lazy sequence as a lazy linked list, then what I wanted was a lazy vector of infinite length or a tree that would automatically determine its data dependency using the Collatz rule. A hash map is enough for this problem, but in a sense it’s only an approximation of what I wanted: a lazy data stream vector with a rule used to fill elements in a vector.

Extra Hard Challenge . Can anyone think of how easy it is to imagine such a lazy tree / vector without using a hash map?

Answer 2

Seconds "looking to the future"

An example of a funky seq looking to 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) 

(cookie for those who make it easier without breaking it. :-))

Of course, if determining the value of an element can include viewing the "future" element, which itself depends on another element, which requires the calculation of an even more remote element ..., disaster could not help.

Euler 14

The main problem is that he tries to use the "look into the future" scheme on the question code aside, this approach does not really solve the problem, because if you decide to start from 1 and go up, you need to consider the branch: a 10 in the Collatz chain can be obtained through the application of any rule (rule n / 2 applied to 20 or rule 3n + 1 , starting from 3 )), In addition, if you want to build your chains up, you must change the rules and either multiply by 2 , or subtract 1 and divide by 3 (applying at each step this rule, which swarm produces an integer - or maybe both of them).

Of course, you could build a tree, not a lazy list, but that would not look like a code sketch in a question, and I would expect that you would end up being an imaginary thing.

The above should be qualified with the remark that you may have an assumption about which “chain building rule” is likely to generate the longest chain, starting at 1 , while the end position remains below a given limit. If so, you should probably prove it right, and then implement it directly (via loop / recur starting at 1 ); without proof, you really cannot claim to have solved the problem.

Answer 3

I think iterate and take-while might be useful (although this code does not look to 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)