Problem Statement

In a two-dimensional world, we begin with any bar-chart (or row of close-packed 'towers', each of unit width), and then it rains, completely filling all convex enclosures in the chart with water.

In the example above, a bar chart representing the values [5, 3, 7, 2, 6, 4, 5, 9, 1, 2] has filled, collecting 14 units of water. Write a function, in your language, from a given array of heights, to the number of water units that can be held in this way, by a corresponding bar chart. Calculate the number of water units that could be collected by bar charts representing each of the following seven series:

See, also:

Let's start with the solution:

(*
A solution I'd show to Euclid !!!!.
Nigel Galloway May 4th., 2017
*)
let solve n =
  let (n,_)::(i,e)::g = n|>List.sortBy(fun n->(-(snd n)))
  let rec fn i g e l =
    match e with
    | (n,e)::t when n < i -> fn n g t (l+(i-n-1)*e)
    | (n,e)::t when n > g -> fn i n t (l+(n-g-1)*e)
    | (n,t)::e            -> fn i g e (l-t)
    | _                   -> l
  fn (min n i) (max n i) g (e*(abs(n-i)-1))