I wasn’t happy with the last one. At least this one is lazier and in increasing cardinality order.

(defn subsets-by-card [s]
  (reduce (fn [ssbc x]
           (map (fn [a b] (concat a (map #(conj % x) b)))
             (concat ssbc [nil]) (concat [nil] ssbc)))
    [[#{}]] s))

Decreasing order:

(defn subsets-by-card-reverse [s]
  (reduce (fn [ssbc x]
            (map (fn [a b] (concat a (map #(<ins>disj</ins> % x) b)))
              (concat ssbc [nil]) (concat [nil] ssbc)))
    [[<ins>(set s)</ins>]] s))

(defn subsets-by-card [s]
  (reduce (fn [ssbc x] 
            (concat
              (map (fn [a b] (concat a (map #(conj % x) b)))
                (cons nil ssbc) ssbc)
              [[#{}]]))
    [[#{}]] s))

(a tough one)

Six weeks since last post… Relocating to my hometown and a trip to Corsica caused me to stay offline for too long.

I’ll be back online soon (as soon as I get a working DSL link and a nearly empty inbox).

BTW, I’m available for contract work from September on.

A friend of mine asked me how I solved the fourth question of Google Treasure Hunt 2008 using Clojure. I didn’t keep the original code around, so below is how I could have done it.

First, define a primes seq.

Second, define a function which returns the sequence of sums of N consecutive primes:

(defn sum-primes [n] (map #(apply + %) (partition n 1 primes)))

Third, define a function which, taking a list of increasing sequences, returns the first common value.

(defn find= [seqs]
  (if (apply == (map first seqs))
    (ffirst seqs)
    (let [[s1 & etc] (sort #(- (first %1) (first %2)) seqs)]
      (recur (cons (rest s1) etc)))))

Last, use them! Here is a sample question:

Find the smallest number that can be expressed as
the sum of 3 consecutive prime numbers,
the sum of 5 consecutive prime numbers,
the sum of 11 consecutive prime numbers,
the sum of 1493 consecutive prime numbers,
and is itself a prime number.

And here is how to compute the answer:

(find= (cons primes (map sum-primes [3, 5, 11, 1493])))

returns 9174901 in twenty seconds or so.

(Right now this code may throw a StackOverflow exception, please use one of those definition of partition.)

Last night on #clojure Lau_of_DK asked for a way to define the sequence of prime numbers.

Having helped Lou Franco in his effort to parallelize primes computation and solved the fourth question of Google Treasure Hunt using Clojure, I thought I knew pretty well how to produce primes in Clojure but I stumbled accross some Haskell code that was far smarter. Here it is, now ported to Clojure:

(def primes (lazy-cons 2 ((fn this[n]
  (let [potential-divisors (take-while #(<= (* % %) n) primes)]
    (if (some #(zero? (rem n %)) potential-divisors) 
      (recur (inc n))
      (lazy-cons n (this (inc n)))))) 3)))

It’s interesting to note that the seq is seeded with 1 and 2 because Clojure’s lazy seqs have a off by one evaluation (when one asks for the nth value, the nth+1 is computed — to know if the end of the seq is reached). No, no, no! I was plain wrong: if I need to seed with [1 2] 2 it’s because of the take-while whose predicate must return at least one false.

Update: In comments, Cale Gibbard points out that my definition of prime numbers is loose: 1 isn’t a prime. I fixed the code.