Thursday, August 18, 2011

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

No comments:

Post a Comment