Solutions to the Twitter rain puzzle

README.md

Concise recursive O(n) solutions to the Twitter rain puzzle in:

• Haskell,
• Clojure,
• Scala.

Puzzle description | Other solutions

Additional links (Russian): Puzzle description | Other solutions

rain-1.hs

volume = fst . f 0
    where f _ [] = (0, 0)
          f l (x:xs) = let (s, r) = f (max l x) xs in (s + max 0 (min l r - x), max x r)

rain-2.clj

(def volume 
  (letfn [(f [l xs]
    (if (seq xs)
      (let [x (first xs) [s r] (f (max l x) (rest xs))]
        [(+ s (max 0 (- (min l r) x))) (max x r)])
      [0 0]))]
    (comp first (partial f 0))))

rain-3.scala

val volume = {
  lazy val f: (Int) => List[Int] => (Int, Int) = l => {
    case Nil => (0, 0)
    case x :: xs => 
      val (s, r) = f(l max x)(xs)
      (s + (0 max ((l min r) - x)), x max r)
  }
  f(0).andThen(_._1)
}

у нас дана функция, которая принимает максимальную высоту стенки слева от произвольного рельефа и сам рельеф, и возвращает площадь, заполненную водой на x:xs, и максимальную высоту стенки на x:xs.
Тогда если к рельефу x:xs приставить слева стенку высоты l, то имея эту функцию, можно вычислить площадь, залитую водой на x:xs, как площадь того, что залито в xs, при условии, что слева от xs будет стенка высотой max l x, + то, что будет залито водой в столбце x, что будет 0, если x выше обоих стенок слева и справа, или разница между более низкой из стенок слева l и справа r и x. При этом максимальная высота стенки справа для x:xs будет максимум из высоты стенки на xs и самим x.