cbeust new coding challenge (october 2011) http://beust.com/weblog/2011/10/30/a-new-coding-challenge/

gistfile1.clj

(ns challenge.weights
  (:require [clojure.contrib.combinatorics :as c]))

(defn weigh? [i l r]
  (let [l-weight (apply + i l)]
    (some #(when (= l-weight (apply + %)) [l %]) (set (c/subsets r)))))

(defn diff [l1 l2] 
  (reduce (fn [l i] 
            (let [[b [f & r]] (split-with (complement #{i}) l)]
              (if f (concat b r) l)))
          l1
          l2))

(defn permutations [n m]
  (->> (apply c/cartesian-product (repeat n (range 1 (inc m))))
       (keep #(when (= m (apply + %)) (sort %)))
       set))

(defn solve [n m]
  (keep (fn [p] (let [subsets (set (c/subsets p))
                        weigh? (fn [i] (some (fn [s] (weigh? i s (diff p s)))
                                             subsets)) 
                        weighings (map weigh? (range 1 (inc m)))]
                    (when (every? identity weighings)
                      [p weighings])))
          (permutations n m)))

(defn print-solution [[stones weighings]]
  (println (str "Found solution : part weights=" stones))
  (dotimes [n (apply + stones)]
    (println "To mesure" (inc n) "pounds, place it on the left, with stones of weight:" (-> weighings (nth n) first)
             " and on the right, place stones of weight:" (-> weighings (nth n) second))))

(defn print-solutions [n m]
  (doseq [s (solve n m)] (print-solution s)))

(comment (print-solutions 4 40))

;;;; output for (print-solutions 4 40) :
=> (print-solutions 4 40)
Found solution : part weights=(1 3 9 27)
To mesure 1 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (1)
To mesure 2 pounds, place it on the left, with stones of weight: (1)  and on the right, place stones of weight: (3)
To mesure 3 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (3)
To mesure 4 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (1 3)
To mesure 5 pounds, place it on the left, with stones of weight: (1 3)  and on the right, place stones of weight: (9)
To mesure 6 pounds, place it on the left, with stones of weight: (3)  and on the right, place stones of weight: (9)
To mesure 7 pounds, place it on the left, with stones of weight: (3)  and on the right, place stones of weight: (1 9)
To mesure 8 pounds, place it on the left, with stones of weight: (1)  and on the right, place stones of weight: (9)
To mesure 9 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (9)
To mesure 10 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (1 9)
To mesure 11 pounds, place it on the left, with stones of weight: (1)  and on the right, place stones of weight: (3 9)
To mesure 12 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (3 9)
To mesure 13 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (1 3 9)
To mesure 14 pounds, place it on the left, with stones of weight: (1 3 9)  and on the right, place stones of weight: (27)
To mesure 15 pounds, place it on the left, with stones of weight: (3 9)  and on the right, place stones of weight: (27)
To mesure 16 pounds, place it on the left, with stones of weight: (3 9)  and on the right, place stones of weight: (1 27)
To mesure 17 pounds, place it on the left, with stones of weight: (1 9)  and on the right, place stones of weight: (27)
To mesure 18 pounds, place it on the left, with stones of weight: (9)  and on the right, place stones of weight: (27)
To mesure 19 pounds, place it on the left, with stones of weight: (9)  and on the right, place stones of weight: (1 27)
To mesure 20 pounds, place it on the left, with stones of weight: (1 9)  and on the right, place stones of weight: (3 27)
To mesure 21 pounds, place it on the left, with stones of weight: (9)  and on the right, place stones of weight: (3 27)
To mesure 22 pounds, place it on the left, with stones of weight: (9)  and on the right, place stones of weight: (1 3 27)
To mesure 23 pounds, place it on the left, with stones of weight: (1 3)  and on the right, place stones of weight: (27)
To mesure 24 pounds, place it on the left, with stones of weight: (3)  and on the right, place stones of weight: (27)
To mesure 25 pounds, place it on the left, with stones of weight: (3)  and on the right, place stones of weight: (1 27)
To mesure 26 pounds, place it on the left, with stones of weight: (1)  and on the right, place stones of weight: (27)
To mesure 27 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (27)
To mesure 28 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (1 27)
To mesure 29 pounds, place it on the left, with stones of weight: (1)  and on the right, place stones of weight: (3 27)
To mesure 30 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (3 27)
To mesure 31 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (1 3 27)
To mesure 32 pounds, place it on the left, with stones of weight: (1 3)  and on the right, place stones of weight: (9 27)
To mesure 33 pounds, place it on the left, with stones of weight: (3)  and on the right, place stones of weight: (9 27)
To mesure 34 pounds, place it on the left, with stones of weight: (3)  and on the right, place stones of weight: (1 9 27)
To mesure 35 pounds, place it on the left, with stones of weight: (1)  and on the right, place stones of weight: (9 27)
To mesure 36 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (9 27)
To mesure 37 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (1 9 27)
To mesure 38 pounds, place it on the left, with stones of weight: (1)  and on the right, place stones of weight: (3 9 27)
To mesure 39 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (3 9 27)
To mesure 40 pounds, place it on the left, with stones of weight: ()  and on the right, place stones of weight: (1 3 9 27)
nil