domingo, 26 de fevereiro de 2012

Python, TCO, paradigms, and online classes

I was working on some code for udacity's class and I have been bitten by something interesting, python's lack of TCO.

I know you can do the "same" things without it, but it was pretty
interesting to realize that I am nowadays so used to work with
functional languages that recursion is one of my first tools to
express loops.

Expressing things in imperative ways is taking me more time now, and I
begin to see how different paradigms really leave an impression on
you. Strange and interesting...

quarta-feira, 8 de fevereiro de 2012

Clojure composition and spirit binding

These days I had to craft something that I didn't even knew existed (don't you love when this happens?). Number composition is the name of the spirit this time.

I will paste the algorithm in clojure below, but I guess the most important thing regarding spirits is not the ritual to bind them, but how you find their names so you can research the ritual itself. My favorite source of arcana regarding spirit names is [1]. I advice it to any wizard, be they apprendice or warlock.

Well, here it goes my version of the ritual, hope you enjoy it.




(defn generate-compositions [num]
  "Returns all possible valid partitions of an integer. An useful
references:

* Skiena's The Algorithm Design Manual, section 14.6 Generating Partitions.

* http://code.activestate.com/recipes/218332/

* http://stackoverflow.com/questions/8375439/composition-algorithm-in-javascript-to-return-all-possible-compositions-of-a-num

This will run in O(2^n), so take care with large inputs."
  (defn accumulate-reduced-compositions
    ([composition-set]
       (accumulate-reduced-compositions composition-set 0 [] (count composition-set)))
    ([composition-set index acc set-lenght]
       (let [next-index (inc index)]
         (if (>= next-index set-lenght)
           acc
           (recur composition-set
                  next-index
                  (conj acc (into (conj (subvec composition-set 0 index)
                                        (+ (nth composition-set index)
                                           (nth composition-set next-index)))
                                  (subvec composition-set (inc next-index))))
                  set-lenght)))))
  
  (loop [all-compositions [(vec (repeat num 1))]
         new-compositions (accumulate-reduced-compositions (first all-compositions))]
    (let [first-new-composition (first new-compositions)]
      (if (= 1 (count first-new-composition))
        (set (conj all-compositions first-new-composition))
        (recur (into all-compositions new-compositions)
               (reduce into (map accumulate-reduced-compositions new-compositions)))))))


[1] Steven Skiena: The Algorithm Design Manual