diff options
| -rw-r--r-- | challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj | 28 |
1 files changed, 13 insertions, 15 deletions
diff --git a/challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj b/challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj index 72a4e05269..d7884efb29 100644 --- a/challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj +++ b/challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj @@ -1,27 +1,25 @@ (ns tw.weekly.ch-2 (:require [clojure.edn :as edn])) -; algorithm source: https://stackoverflow.com/a/35931960 -; Answer by Spectral (https://stackoverflow.com/users/2558887/spectral) -; (modified from Python) +; algorithm source: https://github.com/manwar/perlweeklychallenge-club/blob/master/challenge-075/simon-proctor/raku/ch-2.raku +; Challenge answer by Simon Proctor +; (modified from Raku) (defn largest-rectangle-histogram "Compute the area of the largest possible rectangle within a histogram." [hist] - (let [decorated (into [] (concat [-1] hist [-1])) - stack (atom (list [0 (first decorated)])) - max-area (atom 0)] - (reduce-kv (fn [ans k v] - (while (< v (-> @stack peek last)) - (let [head (-> (swap-vals! stack pop) first peek last) - area (* head (- k (-> @stack peek first) 1))] - (swap! max-area max area))) - (swap! stack conj [k v]) - (max ans @max-area)) - 0 decorated))) + (let [hist (vec hist) + n (count hist) + ranges (vec (for [x (range n), y (range n) :when (<= x y)] + [x y]))] + (reduce (fn [ans [s e]] + (let [height (apply min (map hist (range s (inc e)))) + area (* height (inc (- e s)))] + (max ans area))) + 0 ranges))) (defn -main "Run Task 2 with a list of integers, defaulting to the sample given in the task description." [& args] (let [A (if (not-empty args) (map edn/read-string args) [2, 1, 4, 5, 3, 7])] - (prn (largest-rectangle-histogram A)))) + (println (largest-rectangle-histogram A)))) |