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.


with Ada.Text_IO;
 
procedure Water_Collected is
 
   type Bar_Index     is new Positive;
   type Natural_Array is array (Bar_Index range <>) of Natural;
 
   subtype Bar_Array   is Natural_Array;
   subtype Water_Array is Natural_Array;
 
   function Flood (Bars : Bar_Array; Forward : Boolean) return Water_Array is
      R : Water_Array (Bars'Range);
      H : Natural := 0;
   begin
      if Forward then
         for A in R'Range loop
            H     := Natural'Max (H, Bars (A));
            R (A) := H - Bars (A);
         end loop;
      else
         for A in reverse R'Range loop
            H     := Natural'Max (H, Bars (A));
            R (A) := H - Bars (A);
         end loop;
      end if;
      return R;
   end Flood;
 
   function Fold (Left, Right : Water_Array) return Water_Array is
      R : Water_Array (Left'Range);
   begin
      for A in R'Range loop
         R (A) := Natural'Min (Left (A), Right (A));
      end loop;
      return R;
   end Fold;
 
   function Fill (Bars : Bar_Array) return Water_Array
   is (Fold (Flood (Bars, Forward => True),
             Flood (Bars, Forward => False)));
 
   function Sum_Of (Bars : Natural_Array) return Natural is
      Sum : Natural := 0;
   begin
      for Bar of Bars loop
         Sum := Sum + Bar;
      end loop;
      return Sum;
   end Sum_Of;
 
   procedure Show (Bars : Bar_Array) is
      use Ada.Text_IO;
      Water : constant Water_Array := Fill (Bars);
   begin
      Put ("The series: [");
      for Bar of Bars loop
         Put (Bar'Image);
         Put (" ");
      end loop;
      Put ("] holds ");
      Put (Sum_Of (Water)'Image);
      Put (" units of water.");
      New_Line;
   end Show;
 
begin
   Show ((1, 5, 3, 7, 2));
   Show ((5, 3, 7, 2, 6, 4, 5, 9, 1, 2));
   Show ((2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1));
   Show ((5, 5, 5, 5));
   Show ((5, 6, 7, 8));
   Show ((8, 7, 7, 6));
   Show ((6, 7, 10, 7, 6));
end Water_Collected;