Water collected between towers

From Rosetta Code
Revision as of 16:52, 6 December 2016 by Hout (talk | contribs) (Added link to Stack Overflow discussion)
Water collected between towers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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, filling any 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 would be collected in this way, by a corresponding bar chart.

(See, for example, Water collected between towers on Stack Overflow, from which this example is taken).