project euler problem 4 in clojure

February 5, 2012

I solved a few of the problems on Project Euler in the past, both in Java and Ruby, and thought it would be useful to redo them in Clojure, thus improving my skills on the language’s core functions and libraries. Today I’ll share problem 4.

Go ahead and read it but here’s the meat of it:

“Find the largest palindrome made from the product of two 3-digit numbers."

From this statement we can tell two things: (1) we’ll need a function that can tell whether a number is a palindrome or not and (2) that the largest palindrome is given by the product of two numbers between 100 and 999, inclusive.

Let’s tackle number one first:

(defn palindrome? [n]
  (= (->> n str reverse (apply str))
     (str n)))

With our utility function in hand, one possible solution might be as follows:

(defn largest-palindrome []
  (apply max (filter #(palindrome? %)
                     (for [x (range 100 (inc 999))
                           y (range 100 (inc 999))]
                       (* x y)))))
(time
 (largest-palindrome))
;;"Elapsed time: 1405.358 msecs

While this works, I wasn’t happy with a couple of things in this solution. First, I thought I could do without using filter. Second, we have unnecessary multiplications going on, leading to poor performance - it takes ~1.4secs to finish.

You see, when we begin multiplying the numbers, we’ll see multiplications such as 100 * 100, 100 * 101, 100 * 102 … and then again, after the first loop is exhausted, 102 * 100, 102 * 101, 102 * 102 …

That led me to take a closer look at for, Clojure’s list comprehension macro. It’s a very powerful construct, providing 3 useful modifiers: let, while and when.

With that in mind, I refactored my first solution to look like this:

(defn largest-palindrome-1 []
  (apply max (for [x (range 100 1000)
                   y (range 100 1000)
                   :while (>= x y)
                   :let [z (* x y)]
                   :when (palindrome? z)]
               z)))

(time
 (largest-palindrome-1))
;;"Elapsed time: 689.262 msecs"

Here, the while modifier makes sure we aren’t wasting any time with unnecessary multiplications. The when modifier lets us get rid of the outer filter call. And as you can see, the solution is about twice as fast as its first version.

On top of that, it’s still pretty concise. Not bad.