Lotsa advocaat

advocaat.clj

(ns advocaat.core)

(def barrels [50 44 11 49 42 46 18 32 26 40 21 7 18 43 10 47 36 24 22 40])
(def advocaat-amount 150)

;; imagine there are only two barrels: [50 44]
;; with these two barrels the complete list of all possible combinations is:
;;   50*0 + 44*0 =>  0
;;   50*0 + 44*1 => 44
;;   50*1 + 44*0 => 50
;;   50*1 + 44*1 => 94
;; the combinations can be derived from these bitmaps:
;;   00 = 0
;;   01 = 1
;;   10 = 2
;;   11 = 3
;; an easy way to generate these bitmaps is: (range 4)

;; (range 4) works for 2 bits
;; the generic expression is (range (bit-shift-left 1 nr-of-bits))
;; we have 20 barrels, so, we need all possible bitmaps with 20 bits
;; we need (range (bit-shift-left 1 20)) => 0 .. 1.048.575

;; exercise 1

(defn select
  "(select 2) => (false true false false ..)"
  [n]
  (map #(bit-test n %) (range (count barrels))))

(defn sum-of-barrels
  "(sum-of-barrels 5) => 61 => (+ 50 11)"
  [n]
  (let [bits (select n)
        b (map vector barrels bits)
        f (filter second b)]
    (reduce + (map first f))))

(defn permutations
  "(permutations) => 654"
  []
  (let [i (range (bit-shift-left 1 20))
        sum (map sum-of-barrels i)]
    (count (filter #(= advocaat-amount %) sum))))


;; exercise 2

(defn barrel-combo
  "(barrel-combo 5) => [50 11]"
  [n]
  (->> (select n)
       (map vector barrels)
       (filter second)
       (map first)))

(defn permutations2
  "(permutations2) => [4 57]"
  []
  (->> (bit-shift-left 1 (count barrels))
       range
       (map barrel-combo)
       (filter #(= advocaat-amount (apply + %)))
       (map count)
       frequencies
       (sort-by first <)
       first))