Archive for November, 2011 Coding challenge

November 2, 2011

Here’s my brute-force clojure solution to Cedric Beust’s latest coding challenge. The code maintains a count of how many weights each combination can measure before iterating through the map and returning the maximum – which of course turns out to be all 40!

```(def total 40)

(defn check
([a target]
(if (= a target)
1
0))
([a b target]
(if (or (= 1 (check a target)) (= 1 (check b target)) (= (+ a b) target) (= (- a b) target) (= (- b a) target))
1
0))
([a b c target]
(if (= 0 (+ (check a b target) (check a c target) (check b c target) (check (+ a b) c target) (check (+ a c) b target) (check (+ b c) a target)))
0
1))
([a b c d target]
(if (= 0 (+ (check a b c target) (check a b d target) (check b c d target) (check (+ a b) c d target) (check (+ a c) b d target) (check (+ a d) b c target) (check (+ b c) a d target) (check (+ b d) a c target) (check (+ c d) a b target)))
0
1)))

(defn numberOfWeights [combo]
(loop [x 1 sum 0]
(if (> x total)
sum
(recur (inc x) (+ sum (check (first combo) (second combo) (nth combo 2) (nth combo 3) x))))))

(defn run
([a b c d result]
(let [combo [a b c d]]
(if (= total (+ a b c d))
(assoc result combo (numberOfWeights combo))
result)))
([a b c result]
(let [d (- total (+ a b c))]
(if (< d 0)
result
(run a b c d result))))
([a b result]
(loop [c b r result]
(if (>= (+ a b c) total)
r
(recur (inc c) (run a b c r)))))
([a result]
(loop [b a r result]
(if (>= (+ a b) (- total 1))
r
(recur (inc b) (run a b r)))))
([]
(loop [a 1 result {}]
(if (>= a (- total 2))
result
(recur (inc a) (run a result))))))

(def main
(let [result (run)]
(loop [resultKeys (keys result) maxKey nil maxValue 0]
(let [candidate (first resultKeys)]
(if (nil? candidate)
{maxKey maxValue}
(if (or (nil? maxKey) (> (get result candidate) maxValue))
(recur (next resultKeys) candidate (get result candidate))
(recur (next resultKeys) maxKey maxValue)))))))```

Running it on the clojure console gives me:

```user=> (load-file "/home/raghav/spikes/clojure/weights.clj")
#'user/main
user=> main
{[3 9 27 1] 40}```