4
\$\begingroup\$

I'm working on a Clojure implementation for Project Euler #14, which asks for the initial element, under 106, that produces the longest chain. I'm trying to make use of every optimization I know of, including transients and loop/recur. My code is based on a Lua implementation I wrote which runs in a fraction of a second. My strategy is to record all previously calculated Collatz lengths in a structure, so that I never calculate the same length more than once.

The structure I use is based on a Lua table, with a fixed-length array portion (a transient vector) and a growing dictionary portion (a transient map). Since the table will store lengths (of Collatz chains), I've called it an "ltable". The code to define the structure and its basic operations is:

(def upto 1000000)

(defn ltable-new []
  (transient {:under (transient (into [] (conj (repeat (- upto 2) nil) 1 1)))
              :over (transient {})}))

(defn ltable-contains [b n]
  (let [coll (if (< n upto)
               (b :under)
               (b :over))]
    (coll n)))

(defn ltable-insert! [b n val]
  (let [coll (if (< n upto)
               :under
               :over)]
    (assoc! b coll (assoc! (b coll) n val))))

ltable-new creates a new ltable with the vector initialized with nil values up to the desired length. ltable-contains and ltable-insert! both ensure that any value I provide will be checked for in the correct part of the ltable.

I also need to define a function to get the next Collatz value. It's simply:

(defn nxt-collatz [n] (if (even? n) (quot n 2) (inc (* 3 n))))

To build the ltable for a given value, I use the following code:

(defn ltable-mass-insert! [orig-table orig-lis counter]
  (loop [ltable orig-table lis orig-lis c counter]
    (if (empty? lis)
      ltable
      (let [cur (first lis)
            others (rest lis)]
        (recur (ltable-insert! ltable cur c) others (inc c))))))

(defn iterative-ltable-build! [init-value ltable]
  (loop [cur init-value acc '()]
    (let [nxt (nxt-collatz cur)]
      (if-let [colz-count (ltable-contains ltable nxt)]
        (ltable-mass-insert! (ltable-insert! ltable cur (inc colz-count)) acc (+ colz-count 2))
        (recur nxt (conj acc cur))))))

iterative-ltable-build! takes an initial value and an ltable, and populates the ltable at init-value with the Collatz chain length of that value. It also populates any necessary values that come from calculating the initial value. For example, (iterative-ltable-build! 3 (ltable-new)) will populate the entries for 2, 3, 4, 5, 8, 10, and 16.

To do this iteratively, instead of recursively, I build up a list of uncalculated values. When I encounter a known chain length, I stop iterating and instead insert the chain length (incremented for each member of the list) into each location in the list. This is what ltable-mass-insert! does.

To populate all the values, and to return only the ones below my limit (upto), I use this code:

(defn build-length-ltable []
  (loop [cur 2
         ltable (ltable-new)]
    (if (>= cur upto)
      (persistent! (ltable :under))
      (recur (inc cur) (iterative-ltable-build! cur ltable)))))

This calls iterative-ltable-build! with successive values from 2 to upto, using the same transient ltable throughout. When it's done, I return only the values under upto as a persisted vector.

Finally, to get the value with the longest chain length:

(defn e014 []
  (let [lt (build-length-ltable)
        to-consider (map (fn [a b] [a b]) (range) lt)]
    (first (reduce #(if (< (second %1) (second %2)) %2 %1) to-consider))))

I map the index position to each value, so that a vector of [1 2 8 3 6] becomes [[1 1] [2 2] [3 8] [4 3] [5 6]]. I reduce the collection to the element with the largest length, and return the first value.

When I run it, I usually get a result of 1.5 to 2 seconds.

euler.e014> (time (do (e014) "HIDE THE ANSWER"))
"Elapsed time: 1572.566466 msecs"
"HIDE THE ANSWER"

In Lua, I get a run time below half of a second. How can I improve the run time of this function?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.