Task

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.



9               ██           9               ██    
8               ██           8               ██    
7     ██        ██           7     ██≈≈≈≈≈≈≈≈██    
6     ██  ██    ██           6     ██≈≈██≈≈≈≈██    
5 ██  ██  ██  ████           5 ██≈≈██≈≈██≈≈████    
4 ██  ██  ████████           4 ██≈≈██≈≈████████    
3 ██████  ████████           3 ██████≈≈████████    
2 ████████████████  ██       2 ████████████████≈≈██
1 ████████████████████       1 ████████████████████


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:

   [[1, 5, 3, 7, 2],
    [5, 3, 7, 2, 6, 4, 5, 9, 1, 2],
    [2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1],
    [5, 5, 5, 5],
    [5, 6, 7, 8],
    [8, 7, 7, 6],
    [6, 7, 10, 7, 6]]


See, also:

 Four Solutions to a Trivial Problem – a Google Tech Talk by Guy Steele
 Water collected between towers on Stack Overflow, from which the example above is taken)
 An interesting Haskell solution, using the Tardis monad, by Phil Freeman in a Github gist.


PROC PrintArray(BYTE ARRAY a BYTE len)
  BYTE i
 
  Put('[)
  FOR i=0 TO len-1
  DO
    IF i>0 THEN
      Put(32)
    FI
    PrintB(a(i))
  OD
  Put('])
RETURN
 
BYTE FUNC Max(BYTE ARRAY a BYTE start,stop)
  BYTE i,res
 
  res=0
  FOR i=start TO stop
  DO
    IF a(i)>res THEN
      res=a(i)
    FI
  OD
RETURN (res)
 
BYTE FUNC CalcWater(BYTE ARRAY a BYTE len)
  BYTE water,i,maxL,maxR,lev
 
  IF len<3 THEN
    RETURN (0)
  FI
  water=0
  FOR i=1 TO len-2
  DO
    maxL=Max(a,0,i-1)
    maxR=Max(a,i+1,len-1)
    IF maxL<maxR THEN
      lev=maxL
    ELSE
      lev=maxR
    FI
    IF a(i)<lev THEN
      water==+lev-a(i)
    FI
  OD
RETURN (water)
 
PROC Test(BYTE ARRAY a BYTE len)
  BYTE water
 
  water=CalcWater(a,len)
  PrintArray(a,len)
  PrintF(" holds %B water units%E%E",water)
RETURN
 
PROC Main()
  DEFINE COUNT="7"
  BYTE ARRAY
    a1=[1 5 3 7 2],
    a2=[5 3 7 2 6 4 5 9 1 2],
    a3=[2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1],
    a4=[5 5 5 5],
    a5=[5 6 7 8],
    a6=[8 7 7 6],
    a7=[6 7 10 7 6]
 
  Test(a1,5)
  Test(a2,10)
  Test(a3,16)
  Test(a4,4)
  Test(a5,4)
  Test(a6,4)
  Test(a7,5)
RETURN