An Interview Question from Jane Street: Given some topology, assume it rained and settled, return a new map of the collected rain fall.

jane-street-rain-collection.clj

(ns rain-topology)

;; An Interview Question from Jane Street:
;; Given some topology, assume it rained and settled,
;; return a new array of the collected rain fall.
;;      _                         
;;    _| |    _   
;;  _|   |  _| |  
;; |     |_|   |   
;;        
;;  1 2 3 0 1 2  ->  0 0 0 2 1 0

(defn- indexes-of
  "Return indexes of all elements matching item"
  [coll item]
  (filter
   #(= item (nth coll %))
   (range 0 (count coll))))

(defn- pad [n to vn vto]
  (concat (repeat n vn) (repeat (- to n) vto)))

(defn- map->matrix [coll]
  ;; This needs to create a matrix representation of the land [0 0 1 4]
  (let [size (first (sort > coll))
        m1 (map #(pad % size 1 0) coll)]
    (map (fn [i]
           (map (fn [y] (nth (nth m1 y) i)) (range 0 (count m1))))
         (range (dec (count (first m1))) -1 -1))))

(defn- replace-ix [coll idxs v]
  (loop [i 0
         acc coll]
    (cond
     (= i (count idxs)) acc
     :else (recur (inc i) (assoc acc (nth idxs i) 0)))))

(defn- mark-gaps [row]
  (if-not (empty? ( indexes-of row 1))
    (let [idxs (indexes-of row 1)
          nr (concat
              (repeat (count (range 0 (first idxs)))   0)
              (repeat (count (range (first idxs) (inc (last idxs))))   1)
              (repeat (count (range (inc  (last idxs)) (count row)))   0))]
      (replace-ix (vec nr) (vec idxs) 0))
    row))

(defn- reduce-cols [f m]
  (reverse 
   (map (fn [i]
          (reduce f (map (fn [y] (nth (nth m y) i) ) (range 0 (count m)))))
        (range (dec (count (first m))) -1 -1))))

(defn map->rain [coll]
  (reduce-cols +
               (map mark-gaps (map->matrix coll))))

;;
;; EXAMPLE:
;; (map->rain [1 2 3 0 1 2]) => [0 0 0 2 1 0]
;;