40 lines
2.3 KiB
Text
40 lines
2.3 KiB
Text
;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.
|
||
|
||
|
||
<pre>9 ██ 9 ██
|
||
8 ██ 8 ██
|
||
7 ██ ██ 7 ██≈≈≈≈≈≈≈≈██
|
||
6 ██ ██ ██ 6 ██≈≈██≈≈≈≈██
|
||
5 ██ ██ ██ ████ 5 ██≈≈██≈≈██≈≈████
|
||
4 ██ ██ ████████ 4 ██≈≈██≈≈████████
|
||
3 ██████ ████████ 3 ██████≈≈████████
|
||
2 ████████████████ ██ 2 ████████████████≈≈██
|
||
1 ████████████████████ 1 ████████████████████</pre>
|
||
|
||
|
||
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:
|
||
|
||
<pre> [[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]]</pre>
|
||
|
||
|
||
See, also:
|
||
|
||
* [https://youtu.be/ftcIcn8AmSY?t=536 Four Solutions to a Trivial Problem] – a Google Tech Talk by Guy Steele
|
||
* [http://stackoverflow.com/questions/24414700/amazon-water-collected-between-towers/ Water collected between towers] on Stack Overflow, from which the example above is taken)
|
||
* [https://gist.github.com/paf31/9d84ecf6a6a9b69cdb597a390f25764d An interesting Haskell solution], using the Tardis monad, by [https://gist.github.com/paf31 Phil Freeman] in a [https://gist.github.com/paf31/9d84ecf6a6a9b69cdb597a390f25764d Github gist].
|
||
|
||
|
||
<br>
|
||
|