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.


include "cowgol.coh";
include "argv.coh";
 
# Count the amount of water in a given array
sub water(towers: [uint8], length: intptr): (units: uint8) is
    units := 0;
    loop
        var right := towers + length;
        loop
            right := @prev right;
            if right < towers or [right] != 0 then
                break;
            end if;
        end loop;
        if right < towers then break; end if;
 
        var blocks: uint8 := 0;
        var col := towers;
        while col <= right loop
            if [col] != 0 then
                [col] := [col] - 1;
                blocks := blocks + 1;
            elseif blocks != 0 then
                units := units + 1;
            end if;
            col := @next col;
        end loop;
        if blocks < 2 then
            break;
        end if;
    end loop;
end sub;
 
# Read list from the command line and print the answer
ArgvInit();
var towers: uint8[256];
var count: @indexof towers := 0;
var n32: int32;
loop
    var argmt := ArgvNext();
    if argmt == 0 as [uint8] then
        break;
    end if;
    (n32, argmt) := AToI(argmt);
    towers[count] := n32 as uint8;
    count := count + 1;
end loop;
 
if count == 0 then
    print("enter towers on command line\n");
    ExitWithError();
end if;
 
print_i8(water(&towers[0], count as intptr));
print_nl();