Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Solutions to the Twitter rain puzzle
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)
(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))))
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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment