December 24, 2014

Clojure and Project Euler

A few years ago I really enjoyed doing programming contests - practice ones and real ones. It was a really good way for me to get comfortable with both the concepts and the language when I started programming. Nowadays the contests that I frequented are usually too easy to be a challenge but they also present the same type of challenges year after year.

This was when I was in high school so I was using Visual Basic at the time. When I entered university and learned Java and Python I decided to take on Project Euler to become familiar with the languages. Although it's been 4 months since I started working with Clojure and I'm not exactly a beginner anymore, I thought it would still be fun to Project Euler since Clojure is my first FP language.

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.

On a side note, when I first saw the title of this problem I thought it was going to be FizzBuzz :)

A straightforward solution:

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

This generates a vector of numbers up to 1000 and then filter returns a lazy sequence of the elements that satisfy the predicate function. Finally, reduce is used to sum up the remaining numbers.

The beauty of Project Euler problems is that they can be solved with simple language basics but you can usually rewrite them in more elegant ways.

(reduce + (set (concat (range 0 1000 3) (range 0 1000 5))))
=> 233168

By using the third parameter for Clojure's range, you can generate sequences of multiples of 3 and 5. By concatenating these sequences and then turning them into a set, you get rid of the duplicate values.

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.

First, define the Fibonacci Sequence:

(defn fib
  ([] (fib 1 2))
  ([x y] (cons x (lazy-seq (fib y (+ x y))))))

Using lazy-seq allows us to generate an infinite sequence.

Now just add up the even elements under 4m.

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

First, we use filter to get a sequence of the even Fibonacci numbers. Then we use take-while to return a sequence of elements for which the supplied predicate is true. Here, our predicate is (partial >= 4000000). Partial takes a function f and fewer than normal arguments to f and returns a function that takes the additional args.

Problem 3 - Largest prime factor

What is the largest prime factor of the number 600851475143?

Okay there's a few factorization algorithms out there that can requre a sequence of all the prime factors of a number. If you choose to implement one of these algorithms then you could simply take the max for the answer.

Here's how I did it:

(defn largest-prime [num factor]
  (if (or (> factor (int (Math/sqrt num)))     ; Don't need to check further than this
          (= num factor))
    (if (zero? (mod num factor))
      (recur (/ num factor) factor)            ; If the number is divisible by the factor, divide and iterate
      (recur num (inc factor)))))              ; Otherwise try with a bigger factor
(largest-prime 600851475143 2)
=> 6857

Edit: A redditor has kindly informed me that (> (* factor factor) num) is faster than (> factor (int (Math/sqrt num))) since taking a square root is slower than squaring.

I start off with factor = 2 since 2 is the smallest prime. If factor is greater than the square root of num or if they're equal then the search stops there. (The floor of the square root of a number is the upper bound for its largest prime factor.)

Next, if num is divisible by factor then call largest-prime again with (/ num factor) and factor. Otherwise, increment factor and keep trying.

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.

First, a little helper function to determine if a number is a palindrome:

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

Then filter out the palindrome products and find the max:

(apply max
     (filter palindrome?
               [a (range 100 1000)
                b (range 100 1000)]
               (* a b))))
=> 906609

The for structure shown here will iterate through b for each iteration of a. In other words, it's a nested for-loop.

apply is an interesting function. Calling (apply max [1 2 3]) is equivalent to (max 1 2 3).

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?

This problem is pretty straightforward and can be solved with high school math.

The greatest common divisor of two non-zero integers is the largest positive integer that divides the numbers without a remainder.

(defn gcd [a b] 
  (if (zero? a) 
    (recur (mod b a) a)))

The lowest common multiple of two numbers is the smallest number (not zero) that is a multiple of both.

(defn lcm [a b] 
  (/ (* a b) (gcd a b))) 

Finally, use reduce to find the lowest common multiple of all the numbers from 1 to 20 inclusively.

(reduce lcm (range 1 21))
=> 232792560

This will find the LCM of 1 and 2, then the LCM of the result of that and 3 and so on. Thus, the LCM of all the numbers from 1 to 20.

I'll leave off here before this post gets too lengthy. Project Euler (and a lot of other stuff) is a lot more enjoyable when working with Clojure so I'll likely do a part two eventually.

Tags: clojure