Problem 52 was too easy, so I took the time to use it’s simplicity and study how lazy sequences are chunked, and how they are grouped when
Because this is such a simple problem, I’ll show you the step-by-step refactoring process as I took as I tried to improve the performance and simplicity of the code.
Our goal in this problem was to find a number that when multiplied by 2,3,4,5, and 6 has the exact same digits, but in a different order.
First, let’s write something that solves the problem.
(defn digs [n] (sort (str n))) (defn euler-52  (first (for [x (iterate inc 1) :when (every? #(= (digs x) %) (map #(digs (* x %)) [2 3 4 5 6]))] x))) (time (euler-52)) ;; "Elapsed time: 563.332529 msecs"
Since that was trivial to write, let’s see if we can’t make it more elegant and faster. First, let’s make it faster by using the short-circuiting behavior of
;; short circuits using and (defn euler-52-b  (loop [n 1 d (digs n)] (if (and (= d (digs (* 2 n))) (= d (digs (* 3 n))) (= d (digs (* 4 n))) (= d (digs (* 5 n))) (= d (digs (* 6 n)))) n (recur (inc n) (digs (inc n)))))) (time (euler-52-b)) ;; "Elapsed time: 159.1435 msecs"
What about if we wanted to improve the brevity? Maybe we can use
= to avoid treating the n case different from the 2n, 3n, …6n, cases.
;; Short circuiting broken because of chunking (defn euler-52-c  (first (filter (fn [n] (apply = (map #(digs (* n %)) [1 2 3 4 5 6]))) (iterate inc 1)))) (time (euler-52-c)) ;; "Elapsed time: 603.714745 msecs"
You may be wondering, “Why did the performance get so bad? Shouldn’t the performance be nearly as good as
The answer to this question is that the chunking behavior of sequences (which takes things in groups of 32) meant that the entire array
[1 2 3 4 5 6] was being evaluated and passed through the map. Also, the behavior of
apply when given a long list is that it will take its arguments in groups of four, which is more than is needed.
If you want to see this chunking behavior visually, try the following two lines of code in your REPL:
(apply = (map #(do (print %) %) (iterate inc 1))) ;; Groups by 4 during apply (apply = (map #(do (print %) %) (range))) ;; Seqs chunk by 32's
Thinking of workarounds for the natural behavior of
apply (it may be instructive to look in clojure.core’s source to see how apply is implemented if you are curious why it acts this way), I tried to use
take-while and count that all the elements were consumed, but the result is a little cumbersome.
;; Short circuits because of take-while (defn euler-52-d  (first (filter (fn [n] (let [d (digs n)] (= 5 (count (take-while #(= d (digs (* n %))) [2 3 4 5 6]))))) (iterate inc 1)))) (time (euler-52-d)) ;; "Elapsed time: 236.771 msecs"
Changing hats once again and thinking once again about brevity, let’s use
recur to shorten our definition…
;; Nice and short (defn euler-52-f [n] (if (apply = (map #(sort (str (* n %))) [1 2 3 4 5 6])) n (recur (inc n)))) (time (euler-52-f 1)) ;; "Elapsed time: 552.148607 msecs"
That worked well and is certainly clearer. Now let’s combine it with our earlier
take-while trick and see if we can improve performance again:
(defn euler-52-g [n] (let [d (sort (str n))] (if (= 5 (count (take-while #(= d (sort (str (* n %)))) [2 3 4 5 6]))) n (recur (inc n))))) (time (euler-52-g 1)) ;; "Elapsed time: 187.475716 msecs"
Great! I think most people would just stop at
euler-52-g in the refactoring process, but let’s do one more just to flex our computer scientist muscles, and then we’ll call it quits for today.
Theoretically, short-circuiting behavior on our sequence processing could improve performance by removing the unnecessary computation invoked by chunking and the take-by-four behavior of
apply. If we had a version of
apply that short-circuited, we could write a function like
euler-52-f that would be as performant as anything else.
Of course, we don’t want to actually rewrite
apply, and nothing in the standard sequence library quite fits. So, let’s take the time to write two functions that may be useful in the future:
(defn reducep "Like reduce, but for use with a predicate. Short-circuits on first false." ([p coll] (if-let [s (seq coll)] (reducep p (first s) (next s)) (p))) ([p val coll] (if-let [s (seq coll)] (if-let [v (p val (first s))] (recur p (first s) (next s)) false) true))) (defn unchunk "Forces a sequence to be evaluated element by element. Modified from code by Stuart Sierra" [s] (when-first [x s] (lazy-seq (cons x (unchunk (next s))))))
With those two functions in hand, we can have our cake and eat it too: brevity and reasonable performance.
unchunk, we can write:
(defn euler-52-h [n] (let [d (sort (str n))] (if (every? #(= d %1) (map #(sort (str (* n %))) (unchunk [2 3 4 5 6]))) n (recur (inc n)))))
Or better yet,
(defn euler-52-z [n] (if (reducep = (map #(sort (str (* n %))) (unchunk [1 2 3 4 5 6]))) n (recur (inc n)))) (time (euler-52-z 1)) ;; "Elapsed time: 336.205473 msecs"
Which version did you like the best? The easy-to-understand
euler-52-b? The brief definition in
euler-52-f or it’s more performant sister
euler-52-g? Or the
reducep abstraction approach of