Clojure solution to the Twitter Waterfall Problem http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/

twitterwater.clj

(defn twitterwater
  ([array] (twitterwater array 0))
  ([array v]
   (let [reducer    (fn [state n] (if (:count? state)
                                    (if (> n 0)
                                      (assoc state :av 0 :v (+ (:v state) (:av state)))
                                      (assoc state :av (inc (:av state))))
                                    (if (> n 0)
                                      (assoc state :count? true)
                                      state)))
         init-state {:v v :av 0 :count? false}
         state      (reduce reducer init-state array)
         new-array  (map dec array)]
     (if (some #(> % 0) new-array)
       (recur new-array (:v state))
       (:v state)))))

(def test-cases
  [{:array [1,0,1] :result 1}
   {:array [5,0,5] :result 5}
   {:array [0,1,0,1,0] :result 1}
   {:array [1,0,1,0] :result 1}
   {:array [1,0,1,2,0,2] :result 3}
   {:array [2,5,1,2,3,4,7,7,6] :result 10}
   {:array [5,1,0,1] :result 1}
   {:array [2,5,1,2,3,4,7,7,6,3,5] :result 12}])

(doseq [test-case test-cases]
  (println (:result test-case) "=" (twitterwater (:array test-case))))

(println "18 =" (twitterwater [2,7,2,7,4,7,1,7,3,7]))
(println "17 =" (twitterwater [2 5 1 3 1 2 1 7 7 6]))
(println "10 =" (twitterwater [2 5 1 2 3 4 7 7 6]))

(defn benchmark [size]
  (let [numbers    (take size (repeatedly #(rand-int size)))
        start-time (System/nanoTime)
        result     (twitterwater numbers)
        end-time   (System/nanoTime)
        diff-time  (/ (- end-time start-time) 10e6)]
    (println "size:" size "time:" diff-time "msec")))

(benchmark 10)
(benchmark 100)
(benchmark 1000)