Project Euler Problem 1

Ivar Thorson bio photo By Ivar Thorson

As part of my efforts to learn Clojure, I am starting to work through the Project Euler a little bit each day to sharpen my programming skills without the pressure of having to get any real work done. I’ll post my notes here as I go along for everyone to enjoy, critique, or just laugh at.

For reference, here is the description of Project Euler Problem #1.

My first solution was:

(defn multiple-of-3-or-5? 
   (or (= 0 (mod n 3))
       (= 0 (mod n 5))))

(apply + (filter multiple-of-3-or-5? (range 1000)))

But, after looking at other people’s solutions, I noticed that:

  1. Using reduce instead of apply would probably be more idiomatic, although I don’t notice any real performance difference.
  2. Using rem instead of mod is clearer.
  3. Using zero? instead of (= 0 ...) is also more idiomatic.

So my revised solution is:

(defn multiple-of-3-or-5? [n]
      (or (zero? (rem n 3))
          (zero? (rem n 5))))
    (reduce + (filter multiple-of-3-or-5? (range 1000)))

Solving this problem in lazy style with a clojure set is also an intriguing problem:

    (defn by-ns [n] (iterate #(+ n %) n))
    (reduce + (-> #{}
                  (into (take-while #(< % 1000) (by-ns 3)))
                  (into (take-while #(< % 1000) (by-ns 5)))))

Performance for the lazy method isn’t as good as the naive remainder method for small numbers like 3 or 5, but this approach might yield some improvement for bigger divisors like 103 or 117.

Now for some obfuscation…er, I mean beautification. Looking at the above, I wish there was a way to get ride of the arrow operator…if only into supported multiple collections…maybe we could call it all-into?

(defmacro all-into [to & froms]
      "Returns a new coll consisting of to-coll with all items of all from-colls
      conjoined. See also: clojure.core/into"
      `(-> ~to ~@(map #(list into %) froms)))
    (reduce + (all-into #{}
                        (take-while #(< % 1000) (by-ns 3))
                        (take-while #(< % 1000) (by-ns 5))))

That’s a bit better, but didn’t really solve the problem. Since we’re already having fun with unnecessary macros, what we really need to do is remove the duplication in the take-whiles.

(defmacro multi-take-while [pred & colls]
      "Applies pred to each lazy coll, and takes elements lazily from the first
      coll while pred is true, then from the second coll while pred is true,
      and so on until all possible elements from all colls have been taken.
      See also: clojure.core/take-while"
      `(lazy-cat ~@(map #(list take-while pred %) colls)))
    (reduce + (into #{} (multi-take-while #(< % 1000) (by-ns 3) (by-ns 5))))

There! A single line expressing the problem without any redundancy.

Finally, we can check that multi-take-while is probably still lazy by running:

user> (time (take 10 (multi-take-while #(< % 100000000) (by-ns 3) (by-ns 5))))
    "Elapsed time: 0.296369 msecs"
    (3 6 9 12 15 18 21 24 27 30)

This code was sponsored by the Association for No Code Duplication, a group of OCD sufferers who use macros to turn any readable, multi-line program into a single line of incomprehensibility.