water-towers.clj

(ns water-towers.core)

(defn- find-deltas
  "Find max possible water between this tower and its tallest left neighbor"
  [xs]
  (:deltas (reduce (fn [m x]
                     (let [left-bound (:max m)
                           delta-so-far (:deltas m)]
                       (if (< x left-bound)
                         {:max left-bound
                          :deltas (conj delta-so-far (- left-bound x))}
                         {:max x
                          :deltas (conj delta-so-far 0)})))
                   {:max 0 :deltas []}
                   xs)))


(defn water-collected
  "Returns total water collected between towers in ts"
  [ts]
  (let [left-deltas (find-deltas ts)
        right-deltas (reverse (find-deltas (reverse ts)))]
    (apply + (map (fn [[l r]] (min l r))
                  (map vector left-deltas right-deltas)))))


(deftest test-monotonic-increasing-seq
  (testing "Has no water"
    (is (= 0 (water-collected (range 10))))))


(deftest test-monotonic-decreasing-seq
  (testing "Has no water"
    (is (= 0 (water-collected (reverse (range 10)))))))


(deftest test-u-shaped-seq
  (testing "Has water in the U"
    (is (= 5 (water-collected [6 3 2 5])))))


(deftest test-multiple-u-shaped-seq
  (testing "Has water in the U's"
    (is (= 13 (water-collected [6 3 2 5 10 6 3 2 5])))))


(deftest test-sequence-with-crests-and-troughs
  (testing "Has water in the U's"
    (is (= 17 (water-collected [1 1 2 4 2 1 2 0 0 4 3 5 6 2 1 2])))))