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.


type tower
    hght as uinteger
    posi as uinteger
end type
 
sub shellsort( a() as tower )
    'quick and dirty shellsort, not the focus of this exercise
    dim as uinteger gap = ubound(a), i, j, n=ubound(a)
    dim as tower temp
    do 
        gap = int(gap / 2.2)
        if gap=0 then gap=1
        for i=gap to n
            temp = a(i)
            j=i
            while j>=gap andalso a(j-gap).hght < temp.hght
                a(j) = a(j - gap)
                j -= gap
            wend 
            a(j) = temp
        next i
    loop until gap = 1
end sub
 
'heights of towers in each city prefixed by the number of towers
data 5, 1, 5, 3, 7, 2
data 10, 5, 3, 7, 2, 6, 4, 5, 9, 1, 2
data 16, 2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1
data 4, 5, 5, 5, 5
data 4, 5, 6, 7, 8
data 4, 8, 7, 7, 6
data 5, 6, 7, 10, 7, 6
 
dim as uinteger i, n, j, first, last, water
dim as tower manhattan(0 to 1)
for i = 1 to 7
    read n
    redim manhattan( 0 to n-1 )
    for j = 0 to n-1
        read manhattan(j).hght
        manhattan(j).posi = j
    next j
    shellsort( manhattan() )
    if manhattan(0).posi < manhattan(1).posi then
        first = manhattan(0).posi
        last  = manhattan(1).posi
    else
        first = manhattan(1).posi
        last  = manhattan(0).posi
    end if
    water = manhattan(1).hght * (last-first-1)
    for j = 2 to n-1
        if first<manhattan(j).posi and manhattan(j).posi<last then water -= manhattan(j).hght
        if manhattan(j).posi < first then
             water += manhattan(j).hght * (first-manhattan(j).posi-1)
             first = manhattan(j).posi
        end if
        if manhattan(j).posi > last then
             water += manhattan(j).hght * (manhattan(j).posi-last-1)
             last = manhattan(j).posi
        end if
    next j
    print using "City configuration ## collected #### units of water."; i; water
next i