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)
  ([a b target]
    (if (or (= 1 (check a target)) (= 1 (check b target)) (= (+ a b) target) (= (- a b) target) (= (- b a) target))
  ([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)))
  ([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)))

(defn numberOfWeights [combo]
  (loop [x 1 sum 0]
    (if (> x total)
      (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))
  ([a b c result]
    (let [d (- total (+ a b c))]
      (if (< d 0)
        (run a b c d result))))
  ([a b result]
    (loop [c b r result]
      (if (>= (+ a b c) total)
        (recur (inc c) (run a b c r)))))
  ([a result]
    (loop [b a r result]
      (if (>= (+ a b) (- total 1))
        (recur (inc b) (run a b r)))))
    (loop [a 1 result {}]
      (if (>= a (- total 2))
        (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
{[3 9 27 1] 40}



One comment

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: