public
Created

  • Download Gist
farmers.clj
Clojure
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
(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))

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.