Saturday, August 27, 2011

More lazy stuff

Nice lazy functions

Last time I explained lazy-when functionand how it helps me in solving euler problems. Now I`ll introduce additional similar functions, and then as always, I`m gonna use them in a couple of euler problems.

First, consider all the times when you need lazy functions that check if the number has more then one property. I wanted to re-write lazy-when to accept a collection of predicates and check the number on all of them:
(defn all? [pred-coll]
  (if (coll? pred-coll) (fn [n] (every? #(% n) pred-coll)) pred-coll))

(defn lazy-when
  ([pred s] (lazy-when pred s inc))
  ([pred n next-n]
    (let [pred-f (all? pred)]
      (if-not (pred-f n)
        (recur pred-f (next-n n) next-n)
        (lazy-seq (cons n (lazy-when pred-f (next-n n) next-n)))))))
I used all?  to transform predicate function. It checks if pred is a collection. If not, it returns pred, but if it is then it returns another function that checks the number on all predicates. The rest of the function is pretty-much same.

Quite often, I need the first number from the lazy seq after some other number:

(defn lazy-next [pred s & next]
  (let [next (if (nil? next) inc (first next))]
    (let [s (if ((all? pred) s) (next s) s)]
      (first (lazy-when pred s next)))))

With next I did the same thing as in lazy-when.  S transformation, however, is interesting. If pred returns true for s, then lazy-next would return that value too. And if you have a loop where you recur on each number from a lazy function, that loop would become infinite, and you usualy don't want that. So s is transformed to the next value that would otherwise be checked only if pred returns false for s.

This function will not serve for prime numbers. If I offer s 2 and next step #(+ % 2), then it would check even numbers and never return. However, if I offer inc for the next step, then my lazy-next becomes much slower. That`s why I created next-prime, as the special case of lazy-next when predicate is prime?
(defn next-prime [prime]
  (if (= prime 2) 3 (lazy-next prime? prime #(+ % 2))))
Finally, euler usually looks for the sum of this-and-that numbers under x. For that reason, I wrote the following functions:

(defn lazy-top [pred s end until? & next]
   (let [next (if (nil? next) inc (first next))]
     (take-while #(until? % end) (lazy-when pred s next))))

(defn lazy-sum [pred s  end until? & next] 
  (let [next (if (nil? next) inc (first next))]
    (reduce + (lazy-top pred s end until? next))))

Little more than one-liners, but the pattern is there often enought so why not have it as a function?

Now, with those, to solve the problem from the last post all it takes is:

(time (println (+ 2 (lazy-sum prime? 3 (reduce * 2 (repeat 6 10)) < #(+ 2 %) ))))

Lets try something else. Problem 046 I only need to discover if the number can be written as the sum of a prime and twice a square, and I have it all:

(defn goldbach? [n]
  (loop [prime 2 root 1]
    (let [goldbach (+ prime (* 2 root root))]
      (cond (= n goldbach) true
            (> prime (dec n)) false
            (> goldbach n) (recur (next-prime prime) 1)
            :else (recur prime (inc root))))))

(time (println (lazy-next [#(not (prime? %)) #(not (goldbach? %))] 33 #(+ % 2))))

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
       :else
   (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))]
          t))
        (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.

Thursday, August 18, 2011

Shortness

When I first watched intro videos for learning clojure, the thing that I was most sceptical about is shortness of a code. Little did I know! I`ve put up a couple of examples to prove it to those that still think the way I did.

Euler Problem 052

(defn digits [big-n]
  (map read-string (re-seq #"\d+" (apply str (interleave (repeat ",") (seq (str big-n)))))))   

I`m certain there is a straightforward way to get digits from a number in clojure, but I haven`t found it. And not for the lack of trying! But this is the best I could come up with.

(defn eligible? [n l]
  (loop [i n c 1]
    (if (= c l) true (if (= (sort (digits n)) (sort (digits (+ n i)))) (recur (+ n i) (inc c)) false))))

The second function checks if the number in question does have the same digits when multiplied l times. L stands for limit, meaning how many times should the number be multiplied. Number digits is sorted, and then compared to the double of its values digits. If they are the same, then double and triple values are compared and so on.

(time (println (#(if (eligible? % %2) % (recur (inc %) %2)) 1 6)))

Finally, I use brute force in the anonymous function to check each number if it fulfills the terms of the assignment. It just increments numbers one by one, nothing fancy.


4Clojure Number maze

(fn [s e]
  (loop [n 1 coll #{s}]s
    (if (contains? coll e) n
      (recur (inc n) (set (flatten (for [p (vec coll)] (map #(% p 2) [+ / *]))))))))
 Function takes the starting number and checks if it matches the end. If it doesn`t, the next iteration takes 3 new values as an arg, one for each operation. So each next iteration has 3 args in a coll for each of the previous args. Perfect example of using higher order function in clojure, imo.

So yes, clojure code is short. And if you`re not convinced, check this. Make sure to read through the comments as well!

There is a naughty saying among Serbian developers saying that..., well, I`m not gonna say that in public, but it means that you have more time on your hands when you type less.

update, 16.09.2011:


Finally, I took some time to find better digits function. Here it is:

(defn digits [big-n]
 (map (Character/getNumericValue %) (str n)))

Euler problem 045

Problem: euler 045

I wanted to build a function that can find numbers that are not only triagonal, pentagonal and hexagonal, but also octagonal or any-gonal kind that you`d like. The first thing I need is a function that checks if number is i-gonal or not:

(defn i-gonal-number? [n i]
  (loop [sum 1 increment (inc i)]
    (cond (= sum n) true
          (> sum n) false
          :else (recur (+ sum increment) (+ increment i)))))

n is for number that is being checked, i for the type of number I want to check. It receives 1 for triagonal, 3 for pentagonal, 4 for hexagonal and so on. The loop checks triagonal numbers and compares them to the one we need. Next, a function that creates a lazy function of all i-gonal numbers:

(defn i-gonal-numbers [i]
  ((fn increment [n incr]
    (lazy-seq (cons n (increment (+ n incr) (+ i incr))))) 1 (inc i)))

Not much to explain here, so I`ll use this opportunity to apologize for my lame literacy. Transition from java coding conventions to clojure ones is still in the process.

Final building brick is a function that compares multiple i-gonal numbers and returns those who match all types of gonals. And there it is:

(defn find-polygonal [coll]
  (let [sorted-coll  (sort > coll)]
    ((fn [max-n rest-n]
      (for [t (i-gonal-numbers max-n)
          :when (not (not-every? #(i-gonal-number? t %) rest-n))]
          t))
        (first sorted-coll) (rest sorted-coll))))

It receives a collection of gonal-types that I want to compare. Let block sorts it in a descending order, for performance sake. The gonal-types with highest increment are checked first. In for block I used i-gonal numbers to produce lazy function of the i-gonal type with the biggest increment. Then it checks the next biggest i-gonal type, to see if it matches. When it finds the number which is all-gonal, it returns it. Finally, to print the result of the problem, I used:

(time (println (take 3 (find-for-all-numbers [1 3 4]))))

To solve euler problem it took 26 secs, so I wouldn`t try this for bigger numbers. Well, that`s it. I used recursion, lazy sequences and closures, all idiomatic for clojure, and I think the functions are readable, so my goal (making elegant code, as described in intro post) has been reached.

Intro

Hi everyone,

Welcome to my clojure blog! I`ve been learning clojure for about a month and a half now, and I`m slowly jumping on the bandwagon. Being a java developer with only a modest experience, I`m not used to juicy uber-cool functional tricks, but I`m getting used to it. And I`m enjoying it!

My reasons for opening this blog are, well, quite common, but I`ll name them anyway. First, I would like to help other clojure novices like me. If anyone finds anything useful here, then all the time I spent writing wasn't for nought. On the other side, if someone smarter or more experienced (or both, of course) accidentally finds this blog and point out what I`m doing wrong in my code, then again, my writing is paying dividends. Finally, most of all I`m doing it because it`s interesting.

Later I might write about something else, but for now I`ll stick to the problems that you can find on learning sites like euler, 4clojure or koans, mostly euler. Yeah, I know, there are countless bloggers who bore people about exactly the same things, but I`m gonna do that anyway.

There is one thing I would like to say regarding euler problems. They are more about speed than elegance. Well, I`m gonna focus at the elegance. I wount neglect speed, of course.  They have "one minute rule", saying that each algorithm should be executed in one minute, and I always try to follow it, or at least to be close to that limit, but I`m not gonna go beyond that. I repeat, the focus is at the elegance.

Well, that`s all I wanted to say here. I hope I wount suck at this,

Panther Tamer