Monday, November 08, 2010

Solutions to the first 5 Project Euler problems in Clojure

Recently, I've started learning the Clojure programming language. After reading a great book, Programming Clojure by Stuart Halloway, I decided to get my hands dirty and try something real :) There is a nice site that does precisely what you need in such cases: gives you tasks to solve. In this post I just want to list my solutions to the first five problems written in Clojure and probably make somebody interested in this amazing language.

Let's get started! :)

Problem 1

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.

(defn euler-1 [bound]
  (letfn [(dividends [divider]
    (take (quot (dec bound) divider)
      (map #(* % divider) (iterate inc 1))))]
  (->> (concat (dividends 3) (dividends 5))
       (reduce +))))

(time (euler-1 1000))

;"Elapsed time: 22.45872 msecs"

Problem 2

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, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

(defn euler-2 [bound]
  (letfn [(fib []
    (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))]
  (->> (fib)
       (take-while #(<= % bound))
       (filter even?)
       (reduce +))))

(time (euler-2 4000000))

;"Elapsed time: 5.581436 msecs"

Please note that the function for Fibonacci numbers generation is from the mentioned book.

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

(defn euler-3 [n]
  (letfn [(prime? [n]
    (if (or (not (integer? n)) (< n 2) (and (> n 2) (even? n))) false
      (not-any? true? (map #(zero? (rem n %)) (range 2 n)))))]
  (first (drop-while #(not (prime? %))
    (map #(/ n %) (iterate inc 2))))))

(time (euler-3 600851475143))

;"Elapsed time: 167274.337101 msecs"

Problem 4

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.

(defn euler-4 [digits]
  (let [max (dec (expt 10 digits))]
  (letfn [(palindromic? [n]
            (let [string (str n)]
              (= string (apply str (reverse string)))))
          (product-x-digit? [n]
            (boolean (first (drop-while
              #(not (and (zero? (rem n %)) (= digits (count (str (/ n %))))))
              (range max (quot max 10) -1)))))]
  (first (drop-while #(not (product-x-digit? %))
    (filter palindromic? (iterate dec (* max max))))))))

(time (euler-4 3))

;"Elapsed time: 478.636251 msecs"

Problem 5

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?

(defn euler-5 [bound]
  (letfn [(divisible? [n dividers]
    (reduce #(and %1 (zero? (rem n %2))) true dividers))]
  (first (drop-while #(not (divisible? % (range 1 (inc bound))))
    (range bound Integer/MAX_VALUE bound)))))

(time (euler-5 20))

;"Elapsed time: 106484.829776 msecs"

Having this short experience, I'd say that I really like the language, but it takes some time to get used to the functional way of thinking. It's really not that easy after years of OOP, but it's certainly possible :) My suggestion to the beginners is to read the core API first. Yes, I know that the list of functions is huge, but that's why you just have to go through it. Most probably there's a function for anything you may think of :)

Sometimes the description of a function in the API is not very clear, in this case a good place to go is, where you can find usage examples for most of the functions.

I really enjoyed programming in Clojure, hope you'll have fun as well!

BTW, how long will solutions to these problems be in your favorite programming language? :)


Post a Comment