Skip to content

Instantly share code, notes, and snippets.

@cosmin
Created February 24, 2012 00:53
Show Gist options
  • Save cosmin/1896379 to your computer and use it in GitHub Desktop.
Save cosmin/1896379 to your computer and use it in GitHub Desktop.
(in-ns 'user)
;;; for convenience, code from clojure.contrib.combinatorics
(defn- index-combinations
[n cnt]
(lazy-seq
(let [c (vec (cons nil (for [j (range 1 (inc n))] (+ j cnt (- (inc n)))))),
iter-comb
(fn iter-comb [c j]
(if (> j n) nil
(let [c (assoc c j (dec (c j)))]
(if (< (c j) j) [c (inc j)]
(loop [c c, j j]
(if (= j 1) [c j]
(recur (assoc c (dec j) (dec (c j))) (dec j)))))))),
step
(fn step [c j]
(cons (rseq (subvec c 1 (inc n)))
(lazy-seq (let [next-step (iter-comb c j)]
(when next-step (step (next-step 0) (next-step 1)))))))]
(step c 1))))
(defn combinations
"All the unique ways of taking n different elements from items"
[items n]
(let [v-items (vec (reverse items))]
(if (zero? n) (list ())
(let [cnt (count items)]
(cond (> n cnt) nil
(= n cnt) (list (seq items))
:else
(map #(map v-items %) (index-combinations n cnt)))))))
(defn subsets
"All the subsets of items"
[items]
(mapcat (fn [n] (combinations items n))
(range (inc (count items)))))
;;; code to solve the problem
(defn sum [coll]
(reduce + coll))
(defn all-weight-possibilities [stones]
(let [stone-set (set stones)]
(for [left (subsets stones)
right (subsets (apply disj stone-set left))]
(list left right))))
(defn can-weigh? [weight stones]
(first (filter #(not (nil? %))
(for [[left, right] (all-weight-possibilities stones)]
(if (= (sum left) (+ weight (sum right)))
[left right]
nil)))))
(defn possible-stones []
(filter #(= 40 (sum %1)) (combinations (range 1 40) 4)))
(defn solution? [stones]
(every? #(not (nil? %1))
(map #(can-weigh? %1 stones) (range 1 41))))
(defn solve-farmer-problem []
(first (filter solution? (possible-stones))))
(println (solve-farmer-problem))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment