Subscribe RSS

Posts Tagged ‘projet Euler’

Project Euler with Clojure (1)

August 26th, 2009 by fmn | No Comments | Filed in Teaching

The first Euler project problem is stated as :

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 first naive solution, can be obtained from a range of integers between 0 and 999, retain only multiples of 3 and 5, and sum the remain ones:

(def sum #(reduce + %))

(defn euler1-a []
  (sum (filter #(or (zero? (rem % 3))
                    (zero? (rem % 5)))
               (range 1000))))

The obtained value is:

user> (euler1a)
233168

which is the good answer.

This solution is quite readable. It is some kind of direct translation of the problem into code. However it is not really effective in terms of computation time. All integers (under 1000) are examined. It would be faster to only examine multiples of 3 or 5.

A second solution comes when considering the sequence of 3-multiples:

(range 0 1000 5)

It is thus only needed to sum the 3-multiples and the 5-multiples :

user> (+ (sum (range 0 1000 3))
         (sum (range 0 1000 5)))
266333

The obtained value is wrong. Indeed, some numbers appear two times, in each sequence : the mutiples of 3 and 5. Here is a list of these multiples (under 100):

user> (intersection (set (range 0 100 3)) (set (range 0 100 5)))
#{0 75 45 15 90 60 30}

Actually, this is the list of the 15-multiples (i.e. 3 * 5). In order to compute the good value, we need to subtract the sum of the 15-multiples from the initial sum:

(defn euler1-b []
  (+ (sum (range 0 1000 3))
     (sum (range 0 1000 5))
     (- (sum (range 0 1000 15)))))

This time the value is ok:

user> (euler1b)
233168

In order to have some fun, here is a solution that only examines different multiples of 3 and 5. The idea is to have two counters, one for the 3-multiples and a second for the 5-multiples. A each iteration, only one counter is incremented (by 3 for the 3-multiples one, and by 5 for the 5-multiples). The value of the counter is added to the final sum:

(defn euler1-c []
  (loop [x3 0
         x5 0
         s 0]
    (let [x3+ (+ 3 x3)
          x5+ (+ 5 x5)]
      (if (or (< x3+ 1000)
              (< x5+ 1000))
        (cond
          (= x3+ x5+) (recur x3+ x5+ (+ x3+ s))
          (< x3+ x5+) (recur x3+ x5 (+ x3+ s))
          :else (recur x3 x5+ (+ x5+ s)))
        s))))

For each iteration, the smallest counter is chosen to be incremented. By example if x3 equals 9 and x5 equals 10, then x3+ equals 12 and x5+ equals 15. In this case, x3 is incremented. If the two counters are equal, there are all incremented to avoid to add two times the same number. The obtained value is good:

user> (euler1c)
233168

Here is a little computation time comparison based 1000 function calls:

user> (defmacro timex [n stuff]
        `(time (dotimes [x# ~n]
                 ~stuff)))
#'user/timex
user> (timex 1000 (euler1-a))
"Elapsed time: 2270.722148 msecs"
nil
user> (timex 1000 (euler1-b))
"Elapsed time: 1337.681488 msecs"
nil
user> (timex 1000 (euler1-c))
"Elapsed time: 534.767148 msecs"
nil

The function euler1-c is clearly the fastest, as it only examines the different multiples of 3 and 5. On the otherside, it is clearly not the more readable. As often, it a tradeoff.

FMN.

Wikio
Wikio

Tags: , ,