Monday, August 22, 2011

I`m lazy and I like it!

It occurred to me that a lot of solutions for euler problems have 2 similar building bricks: first, I need a function that questions if a number has some property (is it a prime number, amicable, palindrome or something else) and returns boolean value, and then I need the lazy function that produces a sequence of numbers with this kind of property. So, I thought I might generalize this process, and this is how lazy-when was born:

(defn lazy-when
  ([pred n] (lazy-when pred n #(inc %)))
  ([pred n next-n]
      (if-not (pred n)
        (recur pred (next-n n) next-n)
        (lazy-seq (cons n (lazy-when pred (next-n n) next-n)))))) 
Pred is the function that asks if the number has the property in question. n is the first number that will be checked. next-n is a function that returns the next suitable value of n. If you don`t care about performance, feel free to use its default value, #(inc %). 

Very simple function, but I find it very useful, I already used it several times. Let me show it:

Euler problem 010

Generating prime numbers is probably the most common case on euler, that I had so far. And it fits here beautifully. First, of course, a function that checks if the number is prime:
 (defn prime? [n]
 (cond (= n 1) false
       (= n 2) true
       (even? n) false
   (let [root (int (Math/sqrt n))]
     (loop [tryout 3]
       (if (> tryout root) true
         (if (= 0 (rem n tryout)) false
           (recur (+ 2 tryout))))))))
 Now I only need one line to see the sum of primes:

(time (println (reduce + 2 (take-while #(> 2000000 %) (lazy-when prime? 3 #(+ 2 %))))))

Let me return to the problem 045, described in one of my previous posts.

Same boolean function - lazy function, so lets use lazy-when in find-polygonal:
 (defn find-polygonal [coll]
  (let [sorted-coll  (sort > coll)]
    ((fn [max-n rest-n]
      (for [t (lazy-when #(i-gonal-number? % max-n) 1)
          :when (not (not-every? #(i-gonal-number? t %) rest-n))]
        (first sorted-coll) (rest sorted-coll))))
 As you can see, same problem, but I need only 2 functions
instead of previous 3, and they are of the same length as before.

No comments:

Post a Comment