Project Euler Problem 14 in Clojure

Question

I recently began learning Clojure. In order to get better acquainted with it, I've been tackling Project Euler challenges.

Problem 14 is not really a difficult one. It asks for the number that results in the longest Collatz sequence.

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even) n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Although my solution does solve the problem, I am not sure if it conforms to the Clojure way of doing things, since it seems to be verbose.

• Does this conform to functional practices?
• Are there any mistakes which result in code being longer than needed?
• Is there a way of omitting the loop/recur and doing the same with list functions such as map and apply
• Any other suggestions in general?

(ns problem14)
(use '[clojure.test :only (is)])
(defn count-collatz
 "Returns a vector [a b] where b is the
 number that initiated the sequence, and
 a is the number of steps taken to reach 1."
 [input-num]
 (loop [num input-num count 1]
 (if (= num 1)
 (vector count input-num)
 (do (if (= (mod num 2) 0)
 (recur (/ num 2) (inc count))
 (recur (+ (* num 3) 1) (inc count)))))))
;; Test case from the project description.
(is (= (count-collatz 13) [10 13]))
(loop [number 1 peak [0 0]]
 (if (>= number 1e6)
 (str "Longest chain is " (last peak))
 (do (let [result (count-collatz number)]
 (do (if (> (first result) (first peak))
 (recur (inc number) result)
 (recur (inc number) peak)))))))

Answer 1

CAVEAT I am not a clojure programmer. (But hopefully you will agree with what I suggest ;))

Put all your code in functions such that all top level forms are defs. Similarly put your tests in deftest forms and run them with run-tests.

In clojure, too, extract meaningful expressions to their own functions and give them names. Then promote baked in magic constants in them to parameters so that they are more testable, in REPL and elswhere.

You can use destructuring let to give meaningful names to a function returning a vector.

Applying these general rules

(defn longest-chain [limit]
 (loop [number 1 peak-len 0 peak-val 0]
 (if (>= number limit)
 peak-val
 (do (let [[curr-len curr-val] (count-collatz number)]
 (do (if (> curr-len peak-len)
 (recur (inc number) curr-len curr-val)
 (recur (inc number) peak-len peak-val))))))))))
(defn -main []
 (println "Longest chain is" (longest-chain 1e6)))

Here is how you can rewrite these functions using core library.

• (= x 0) is (zero? x)
• (zero? (mod num 2)) is (even? x)
• repeatedly applying a function without explicit loop/recur is iterate.
• You can use for comprehension of a range instead of loop/recur with incing a parameter.
• You can also use core library functions that operate on sequences (map, reduce et al) for a more functional style.
• You can use threading macros to reduce nesting levels as necessary; and to make your functions read top-down instead of more counter-intuitive inside-out.
• You can use (apply max-key k coll) to get "the [value] for which (k x), a number, is greatest."

Code after above changes:

(defn count-collatz [n]
 (let [f (fn [n] (if (even? n) (/ n 2) (+ (* n 3) 1)))]
 (->> n
 (iterate f)
 (take-while #(> % 1))
 count
 inc)))
(defn longest-chain [limit]
 (->> limit
 (range 1)
 (map #(vector (count-collatz %) %))
 (apply max-key first)
 second)

Or using the fact that max-key can get arbitrary function as its first parameter, we get:

(defn longest-chain [limit]
 (apply max-key count-collatz (range 1 limit)))

• Dave Yarwood: For a self-professed "non-Clojure programmer," you sure do know your way around writing idiomatic Clojure code! +1