Skip to content

Instantly share code, notes, and snippets.

@skuro
Last active September 11, 2017 09:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save skuro/db435e15ceb40404da5598bc0fb92c83 to your computer and use it in GitHub Desktop.
Save skuro/db435e15ceb40404da5598bc0fb92c83 to your computer and use it in GitHub Desktop.
Clojure version of the water trapped between towers problem
(defn trapped-water [towers]
(let [maxes #(reductions max %) ; the seq of increasing max values found in the input seq
maxl (maxes towers) ; the seq of max heights to the left of each tower
maxr (reverse (maxes (reverse towers))) ; the seq of max heights to the right of each tower
mins (map min maxl maxr)] ; minimum highest surrounding tower per position
(reduce + (map - mins towers)))) ; sum up the trapped water per position
;; in the following, # is a tower block and ~ is trapped water:
;;
;; 10|
;; 9| #
;; 8| #
;; 7| # ~ ~ ~ ~ #
;; 6| # ~ # ~ ~ #
;; 5| # ~ # ~ # ~ # #
;; 4| # ~ # ~ # # # #
;; 3| # # # ~ # # # #
;; 2| # # # # # # # # ~ #
;; 1| # # # # # # # # # #
;; ---+---------------------
;; 5 3 7 2 6 4 5 9 1 2
(trapped-water [5 3 7 2 6 4 5 9 1 2]) ;; 14
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment