## Coding challenge

November 2, 2011Here’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}

Advertisements

Here’s my solution in clojure: https://gist.github.com/1338927

by pyritschard November 4, 2011 at 8:39 am