Coding challenge

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}

 

About these ads