Learn Clojure with Project Euler

Whenever I start learning a new programming language I feel the urge to try someting practical in it - but usually I lack the knowledge in the beginning and get frustrated. Using Project Euler problems as small projects bridges the gap though, because they are usually can be solved with simple language basics yet you can rewrite them in more and more elegant ways as you advance. Also as literally hundreds of solutions are available on the net in various languages you can compare your new language-to-learn’s capabilities and style with other languages you already know. I won’t get into the description of Clojure as this post is focused on solving Project Euler problems but from time to time I will pause and explain small tidbits about the language I find interesting, exceptional or uncommon.

Warning - this post contains spoilers for Project Euler problems.

##Problem #1 - multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

A straightforward solution using apply and filter:

(apply + (filter #(zero? (min (mod % 3) (mod % 5))) (range 1000)))

One trick here is the min function which will return 0 if a number is divisible by either 3 or 5 (because at least one modulus will be 0 then)

Language features used:

• apply - Applies the function to the argument list formed by prepending intervening arguments to args.
• filter - Returns a lazy sequence of the items in the collection for which the predicate function returns true.
• range - Returns a lazy seq of nums from start (inclusive) to end (exclusive).

Or we can use reduce (Clojure’s foldl) and filter:

(reduce + (filter #(or (zero? (mod % 3))
                       (zero? (mod % 5)))
                  (range 1000)))

Language feature used:

• reduce - reduces a collection to a single value iteratively applying the given function to the aggregate and the elements.

Notice how both these solutions use the shorthand for anonymous function declaration (#) as the parameter for filter.

We can use another trick, Clojure’s range accepts a third parameter, step, using which we can generate 3 and 5 multiples as a sequence instead of filtering by divisibility:

(reduce + (set (concat (range 0 1000 3) (range 0 1000 5))))

by using a set, we only include each number once. This is my favorite solution by the way as it’s the closest to the original definition of the problem.

Summary: we’ve seen two approaches: the first two solutions used filtering, the third used exact generation.

##Problem #2 - Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Let’s define the Fibonacci sequence first:

(def fibo (lazy-cat [0 1]
                    (map + fibo (rest fibo))))

A nice and simple recursive definition.

Language feature used:

• lazy-cat - Expands to code which yields a lazy sequence of the concatenation of the supplied colls. Each coll expr is not evaluated until it is needed.

This is exactly what we need as the Fibonacci sequence is infinite so we surely don’t want to automatically realize it’s elements :)

Now we need to add up the even items of the lazy sequence until we reach 4m:

(reduce + (take-while (partial >= 4000000)
                      (filter even? fibo)))

Language features:

• take-while: Returns a lazy sequence of successive items from coll while the predicate (here partial >= 4000000) returns true
• partial: returns a partial of the original function with fewer parameters. We could have also used an anonymous function here: #(even? %)

##Problem #3 - Largest prime factor

What is the largest prime factor of the number 600851475143 ?

The first, naive implementation:

(defn get-largest-prime-factor [num]
  (let [q (long (Math/sqrt num))                ; we don't need to check further than this
        factor? (fn [a b] (zero? (rem a b)))]   ; utility helper fn
    (loop [n num d 2]                           ; starting iteration: n := num d := 2
      (cond
       (> d q) n                                ; we're done if we've reached the limit (sqrt(num))
       (= d n) n                                ; or the two tested numbers are equal (for the inner iteration)
       (factor? n d) (recur (/ n d) d)          ; if n is divisible by d, let's divide it and iterate
       true          (recur n (inc d))))))      ; try with a bigger d

Language features:

• let - for local context bindings
• loop - the most basic and customizable loop in Clojure
• cond - it’s like switch/case
• recur - paired up with loop

I admit it’s quite messy and not really functional Let’s rewrite it:

(defn get-max-prime-factor [num cur]
  (if (= num cur)
    num
    (if (zero? (mod num cur))
      (get-max-prime-factor (/ num cur) cur)
      (get-max-prime-factor num (inc cur)))))

(get-max-prime-factor 600851475143 2)

Much cleaner but a bit less effective and we need to specify the initial iteration (2). Let’s rewrite and wrap it in another function.

(defn get-max-prime-factor [num cur limit]
  (if (> cur limit)
    num
    (if (= num cur)
        num
        (if (zero? (mod num cur))
          (get-max-prime-factor (/ num cur) cur limit)
          (get-max-prime-factor num (inc cur) limit)))))

(defn max-prime-factor [num]
    (let [limit (long (Math/sqrt num))]
        (get-max-prime-factor num 2 limit)))

(max-prime-factor  600851475143)

##Problem #4 - Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

We can reuse all we know so far with a simple extra:

(defn palindrome? [s]
  (= (reverse (str s) ) (seq (str s))))

(apply max
       (filter palindrome?
               (for
                   [a (range 100 1000)
                    b (range 100 1000)]
                 (* a b))))

Language features used:

• for - Takes a vector of collection-expr pairs and yields a lazy sequence of evaluations of expr.

##Problem #5 - Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Well, let’s dust our high school math skills:

(defn gcd [a b] (if (zero? b) a (recur b (mod a b))))  ; greatest common divisor
(defn lcm [a b] (/ (* a b) (gcd a b)))                 ; lowest common multiple 
(reduce #(lcm %1 %2) (range 1 21))

No explanations needed for this, right? Quite straightforward.

I’ll stop now, I think this was a nice intro to Clojure’s capabilities, stay tuned for various Clojure related posts!