Last active
September 11, 2017 09:37
-
-
Save skuro/db435e15ceb40404da5598bc0fb92c83 to your computer and use it in GitHub Desktop.
Clojure version of the water trapped between towers problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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