Osmos problem from Google Code Jam used as a programming kata for the FP community of TID.

osmos.core.clj

(ns osmos.core)

(defn absorb [[size additions] mote]
  (loop [size      size
         additions additions]
    (cond
      (< size 2)    [size Double/POSITIVE_INFINITY]
      (< mote size) [(+ size mote) additions]
      :else         (recur (+ size (dec size))
                           (inc additions)))))

(defn absorb-changes [size motes]
  (map second (reductions absorb [size 0] motes)))

(defn delete-changes [motes] (range (count motes) -1 -1))

(defn changes [size motes]
  (let [sorted-motes (sort motes)]
    (mapv + (absorb-changes size sorted-motes)
            (delete-changes sorted-motes))))

(defn min-fix [size motes]
  (apply min (changes size motes)))

;; I/O

(defn parse-nums [line]
  (map read-string (re-seq #"\d+" line)))

(defn parse-input [input]
  (let [[header & lines] (clojure.string/split-lines input)]
    (map
     (fn [[line1 line2]]
       [(-> line1 parse-nums first)
        (-> line2 parse-nums vec)])
     (partition 2 lines))))

(defn format-output [solutions]
  (clojure.string/join
    (map-indexed
       (fn [idx sol] (format "Case #%d: %d\n" (inc idx) sol))
       solutions)))

(defn solve [in out]
  (->> (slurp in)
       parse-input
       (map #(apply min-fix %))
       format-output
       (spit out)))

(comment
  (solve "/Users/sortega/Downloads/A-small-practice.in" "/Users/sortega/Downloads/A-small-practice.out")
  (solve "/Users/sortega/Downloads/A-large-practice.in" "/Users/sortega/Downloads/A-large-practice.out")
)

osmos.test.core.clj

(ns osmos.test.core
  (:use midje.sweet
        osmos.core))

(fact "A mote of size 1 cannot absorb anything"
  (second (absorb [1 0] 1)) => Double/POSITIVE_INFINITY
  (second (absorb [1 0] 10)) => Double/POSITIVE_INFINITY)

(fact "A mote can absorb any smaller one without help"
  (absorb [2 0] 1) => [3 0])

(fact "A mote can absorb bigger or equal motes by adding
       intermediate motes"
  (absorb [4 10]   4) => [(+ 4 3                  4) 11]
  (absorb [4 20]  10) => [(+ 4 3 6               10) 22]
  (absorb [4 30] 100) => [(+ 4 3 6 12 24 48 96  100) 36])

(fact "Absorb a mote and discard one less in each step"
  (absorb-changes 2 [1 1 2 4]) => [0 0 0 0 0]
  (absorb-changes 2 [1 1 10 10]) => [0 0 0 2 2]
  (delete-changes [1 1 10 10]) => [4 3 2 1 0])

(fact "Additions and deletes are changes"
  (changes 2 [1 10 1 10]) => [(+ 0 4)
                              (+ 0 3)
                              (+ 0 2)
                              (+ 2 1)
                              (+ 2 0)])

(fact "Fix by adding or deleting as few motes as possible"
  (fix 2 [1 1 2 4]) => 0
  (fix 2 [1 1 2 6]) => 1
  (fix 1 [1 1 2 6]) => 4
  (fix 2 [1 1 2 20]) => 1
  (fix 2 [1 10 50 100]) => 3
  (fix 2 [10 1 50 100]) => 3
  (fix 2 [1 1 1 5 6 100 100]) => 3
  (fix  2 [2 1]) => 0
  (fix  2 [2 1 1 6]) => 1
  (fix 10 [25 20 9 100]) => 2
  (fix  1 [1 1 1 1]) => 4)

(fact "Parse a line of numbers"
  (parse-nums "1 2 3") => [1 2 3])

(fact "Parse a complete input"
  (parse-input "2
                2 4
                1 1 1 6
                3 5
                1 1 10 3 1") =>
      [[2 [1 1 1 6]]
       [3 [1 1 10 3 1]]])

(fact "Format output"
  (format-output [0 1]) => "Case #1: 0\nCase #2: 1\n")