Water collected between towers: Difference between revisions

From Rosetta Code
Content added Content deleted
(Add Erlang solution)
(→‎{{header|AppleScript}}: updated primitives)
Line 44: Line 44:
{{Trans|JavaScript}}
{{Trans|JavaScript}}


<lang AppleScript>-- waterCollected :: [Int] -> Int
<lang AppleScript>-- WATER COLLECTED BETWEEN TOWERS --------------------------------------------

-- waterCollected :: [Int] -> Int
on waterCollected(xs)
on waterCollected(xs)
set leftWalls to scanl1(my max, xs)
set leftWalls to scanl1(my max, xs)
Line 53: Line 55:
-- positive :: Num a => a -> Bool
-- positive :: Num a => a -> Bool
script positive
script positive
on lambda(x)
on |λ|(x)
x > 0
x > 0
end lambda
end |λ|
end script
end script
-- minus :: Num a => a -> a -> a
-- minus :: Num a => a -> a -> a
script minus
script minus
on lambda(a, b)
on |λ|(a, b)
a - b
a - b
end lambda
end |λ|
end script
end script
Line 69: Line 71:




-- TEST ----------------------------------------------------------------------

-- TEST ------------------------------------------------------------------
on run
on run
map(waterCollected, ¬
map(waterCollected, ¬
Line 85: Line 86:




-- GENERIC FUNCTIONS ---------------------------------------------------------


-- filter :: (a -> Bool) -> [a] -> [a]
-- GENERIC FUNCTIONS ------------------------------------------------------
on filter(f, xs)
tell mReturn(f)
set lst to {}
set lng to length of xs
repeat with i from 1 to lng
set v to item i of xs
if |λ|(v, i, xs) then set end of lst to v
end repeat
return lst
end tell
end filter


-- scanl1 :: (a -> a -> a) -> [a] -> [a]
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on scanl1(f, xs)
on foldl(f, startValue, xs)
tell mReturn(f)
if length of xs > 0 then
scanl(f, item 1 of xs, items 2 thru -1 of xs)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl

-- init :: [a] -> [a]
on init(xs)
if length of xs > 1 then
items 1 thru -2 of xs
else
else
{}
{}
end if
end if
end scanl1
end init


-- scanr1 :: (a -> a -> a) -> [a] -> [a]
-- map :: (a -> b) -> [a] -> [b]
on scanr1(f, xs)
on map(f, xs)
tell mReturn(f)
if length of xs > 0 then
scanr(f, item -1 of xs, items 1 thru -2 of xs)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map

-- max :: Ord a => a -> a -> a
on max(x, y)
if x > y then
x
else
else
{}
y
end if
end if
end scanr1
end max

-- min :: Ord a => a -> a -> a
on min(x, y)
if y < x then
y
else
x
end if
end min

-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn


-- scanl :: (b -> a -> b) -> b -> [a] -> [b]
-- scanl :: (b -> a -> b) -> b -> [a] -> [b]
Line 113: Line 171:
set lst to {startValue}
set lst to {startValue}
repeat with i from 1 to lng
repeat with i from 1 to lng
set v to lambda(v, item i of xs, i, xs)
set v to |λ|(v, item i of xs, i, xs)
set end of lst to v
set end of lst to v
end repeat
end repeat
Line 119: Line 177:
end tell
end tell
end scanl
end scanl

-- scanl1 :: (a -> a -> a) -> [a] -> [a]
on scanl1(f, xs)
if length of xs > 0 then
scanl(f, item 1 of xs, items 2 thru -1 of xs)
else
{}
end if
end scanl1


-- scanr :: (b -> a -> b) -> b -> [a] -> [b]
-- scanr :: (b -> a -> b) -> b -> [a] -> [b]
Line 127: Line 194:
set lst to {startValue}
set lst to {startValue}
repeat with i from lng to 1 by -1
repeat with i from lng to 1 by -1
set v to lambda(v, item i of xs, i, xs)
set v to |λ|(v, item i of xs, i, xs)
set end of lst to v
set end of lst to v
end repeat
end repeat
Line 134: Line 201:
end scanr
end scanr


-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
-- scanr1 :: (a -> a -> a) -> [a] -> [a]
on zipWith(f, xs, ys)
on scanr1(f, xs)
set nx to length of xs
if length of xs > 0 then
scanr(f, item -1 of xs, items 1 thru -2 of xs)
set ny to length of ys
else
if nx < 1 or ny < 1 then
{}
{}
else
set lng to cond(nx < ny, nx, ny)
set lst to {}
tell mReturn(f)
repeat with i from 1 to lng
set end of lst to lambda(item i of xs, item i of ys)
end repeat
return lst
end tell
end if
end if
end zipWith
end scanr1

-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to lambda(item i of xs, i, xs)
end repeat
return lst
end tell
end map

-- filter :: (a -> Bool) -> [a] -> [a]
on filter(f, xs)
tell mReturn(f)
set lst to {}
set lng to length of xs
repeat with i from 1 to lng
set v to item i of xs
if lambda(v, i, xs) then set end of lst to v
end repeat
return lst
end tell
end filter


-- sum :: Num a => [a] -> a
-- sum :: Num a => [a] -> a
on sum(xs)
on sum(xs)
script add
script add
on lambda(a, b)
on |λ|(a, b)
a + b
a + b
end lambda
end |λ|
end script
end script
foldl(add, 0, xs)
foldl(add, 0, xs)
end sum
end sum

-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to lambda(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl

-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property lambda : f
end script
end if
end mReturn

-- init :: [a] -> [a]
on init(xs)
if length of xs > 1 then
items 1 thru -2 of xs
else
{}
end if
end init


-- tail :: [a] -> [a]
-- tail :: [a] -> [a]
Line 230: Line 230:
end tail
end tail


-- max :: Ord a => a -> a -> a
-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
on max(x, y)
on zipWith(f, xs, ys)
set lng to min(length of xs, length of ys)
if x > y then
x
set lst to {}
else
tell mReturn(f)
y
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, item i of ys)
end if
end max
end repeat
return lst

end tell
-- min :: Ord a => a -> a -> a
end zipWith</lang>
on min(x, y)
if y < x then
y
else
x
end if
end min

-- cond :: Bool -> a -> a -> a
on cond(bool, f, g)
if bool then
f
else
g
end if
end cond</lang>

{{Out}}
{{Out}}
<lang AppleScript>{2, 14, 35, 0, 0, 0, 0}</lang>
<lang AppleScript>{2, 14, 35, 0, 0, 0, 0}</lang>

=={{header|AWK}}==
=={{header|AWK}}==
<lang AWK>
<lang AWK>

Revision as of 14:54, 20 July 2017

Task
Water collected between towers
You are encouraged to solve this task according to the task description, using any language you may know.
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:



AppleScript

Translation of: JavaScript

<lang AppleScript>-- WATER COLLECTED BETWEEN TOWERS --------------------------------------------

-- waterCollected :: [Int] -> Int on waterCollected(xs) 

   set leftWalls to scanl1(my max, xs)
   set rightWalls to scanr1(my max, xs)
   
   set waterLevels to zipWith(my min, leftWalls, rightWalls)
   
   -- positive :: Num a => a -> Bool
   script positive
       on |λ|(x)
           x > 0
       end |λ|
   end script
   
   -- minus :: Num a => a -> a -> a
   script minus
       on |λ|(a, b)
           a - b
       end |λ|
   end script
   
   sum(filter(positive, zipWith(minus, waterLevels, xs)))

end waterCollected


-- TEST ---------------------------------------------------------------------- on run 

   map(waterCollected, ¬
       [[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]])
   
   --> {2, 14, 35, 0, 0, 0, 0}

end run


-- GENERIC FUNCTIONS ---------------------------------------------------------

-- filter :: (a -> Bool) -> [a] -> [a] on filter(f, xs) 

   tell mReturn(f)
       set lst to {}
       set lng to length of xs
       repeat with i from 1 to lng
           set v to item i of xs
           if |λ|(v, i, xs) then set end of lst to v
       end repeat
       return lst
   end tell

end filter

-- foldl :: (a -> b -> a) -> a -> [b] -> a on foldl(f, startValue, xs) 

   tell mReturn(f)
       set v to startValue
       set lng to length of xs
       repeat with i from 1 to lng
           set v to |λ|(v, item i of xs, i, xs)
       end repeat
       return v
   end tell

end foldl

-- init :: [a] -> [a] on init(xs) 

   if length of xs > 1 then
       items 1 thru -2 of xs
   else
       {}
   end if

end init

-- map :: (a -> b) -> [a] -> [b] on map(f, xs) 

   tell mReturn(f)
       set lng to length of xs
       set lst to {}
       repeat with i from 1 to lng
           set end of lst to |λ|(item i of xs, i, xs)
       end repeat
       return lst
   end tell

end map

-- max :: Ord a => a -> a -> a on max(x, y) 

   if x > y then
       x
   else
       y
   end if

end max

-- min :: Ord a => a -> a -> a on min(x, y) 

   if y < x then
       y
   else
       x
   end if

end min

-- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Script on mReturn(f) 

   if class of f is script then
       f
   else
       script
           property |λ| : f
       end script
   end if

end mReturn

-- scanl :: (b -> a -> b) -> b -> [a] -> [b] on scanl(f, startValue, xs) 

   tell mReturn(f)
       set v to startValue
       set lng to length of xs
       set lst to {startValue}
       repeat with i from 1 to lng
           set v to |λ|(v, item i of xs, i, xs)
           set end of lst to v
       end repeat
       return lst
   end tell

end scanl

-- scanl1 :: (a -> a -> a) -> [a] -> [a] on scanl1(f, xs) 

   if length of xs > 0 then
       scanl(f, item 1 of xs, items 2 thru -1 of xs)
   else
       {}
   end if

end scanl1

-- scanr :: (b -> a -> b) -> b -> [a] -> [b] on scanr(f, startValue, xs) 

   tell mReturn(f)
       set v to startValue
       set lng to length of xs
       set lst to {startValue}
       repeat with i from lng to 1 by -1
           set v to |λ|(v, item i of xs, i, xs)
           set end of lst to v
       end repeat
       return reverse of lst
   end tell

end scanr

-- scanr1 :: (a -> a -> a) -> [a] -> [a] on scanr1(f, xs) 

   if length of xs > 0 then
       scanr(f, item -1 of xs, items 1 thru -2 of xs)
   else
       {}
   end if

end scanr1

-- sum :: Num a => [a] -> a on sum(xs) 

   script add
       on |λ|(a, b)
           a + b
       end |λ|
   end script
   
   foldl(add, 0, xs)

end sum

-- tail :: [a] -> [a] on tail(xs) 

   if length of xs > 1 then
       items 2 thru -1 of xs
   else
       {}
   end if

end tail

-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] on zipWith(f, xs, ys) 

   set lng to min(length of xs, length of ys)
   set lst to {}
   tell mReturn(f)
       repeat with i from 1 to lng
           set end of lst to |λ|(item i of xs, item i of ys)
       end repeat
       return lst
   end tell

end zipWith</lang>

Output:

<lang AppleScript>{2, 14, 35, 0, 0, 0, 0}</lang>

AWK

<lang AWK>

  1. syntax: GAWK -f WATER_COLLECTED_BETWEEN_TOWERS.AWK [-v debug={0|1}]

BEGIN { 

   wcbt("1,5,3,7,2")
   wcbt("5,3,7,2,6,4,5,9,1,2")
   wcbt("2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1")
   wcbt("5,5,5,5")
   wcbt("5,6,7,8")
   wcbt("8,7,7,6")
   wcbt("6,7,10,7,6")
   exit(0)

} function wcbt(str, ans,hl,hr,i,n,tower) { 

   n = split(str,tower,",")
   for (i=n; i>=0; i--) { # scan right to left
     hr[i] = max(tower[i],(i<n)?hr[i+1]:0)
   }
   for (i=0; i<=n; i++) { # scan left to right
     hl[i] = max(tower[i],(i!=0)?hl[i-1]:0)
     ans += min(hl[i],hr[i]) - tower[i]
   }
   printf("%4d : %s\n",ans,str)
   if (debug == 1) {
     for (i=1; i<=n; i++) { printf("%-4s",tower[i]) } ; print("tower")
     for (i=1; i<=n; i++) { printf("%-4s",hl[i]) } ; print("l-r")
     for (i=1; i<=n; i++) { printf("%-4s",hr[i]) } ; print("r-l")
     for (i=1; i<=n; i++) { printf("%-4s",min(hl[i],hr[i])) } ; print("min")
     for (i=1; i<=n; i++) { printf("%-4s",min(hl[i],hr[i])-tower[i]) } ; print("sum\n")
   }

} function max(x,y) { return((x > y) ? x : y) } function min(x,y) { return((x < y) ? x : y) } </lang>

Output:
   2 : 1,5,3,7,2
  14 : 5,3,7,2,6,4,5,9,1,2
  35 : 2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1
   0 : 5,5,5,5
   0 : 5,6,7,8
   0 : 8,7,7,6
   0 : 6,7,10,7,6

C#

Version 1

Translation from Visual Basic .NET. See that version 1 entry for code comments and details. <lang Csharp>using System;</lang> <lang Csharp>static void Main(string[] args) { 

   int[][] wta = {
       new int[] {1, 5, 3, 7, 2},     new int[] { 5, 3, 7, 2, 6, 4, 5, 9, 1, 2 },
       new int[] { 2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1 },
       new int[] { 5, 5, 5, 5 },      new int[] { 5, 6, 7, 8 },
       new int[] { 8, 7, 7, 6 },      new int[] { 6, 7, 10, 7, 6 }};
   string blk = "", lf = "\n"; for (int i = 0; i < wta.Length; i++)
   {
       int bpf; blk = ""; do
       {
           string floor = ""; bpf = 0; for (int j = 0; j < wta[i].Length; j++)
           {
               if (wta[i][j] > 0)
               {    floor += "██"; wta[i][j] -= 1; bpf += 1; }
               else floor += (j > 0 && j < wta[i].Length - 1 ? "≈≈" : "  ");
           }
           if (bpf > 0) blk = floor + lf + blk;
       } while (bpf > 0);
       while (blk.Contains("  ≈≈")) blk = blk.Replace("  ≈≈", "    ");
       while (blk.Contains("≈≈  ")) blk = blk.Replace("≈≈  ", "    ");
       if (args.Length > 0) Console.Write("{0}", blk);
       Console.WriteLine("Block {0} retains {1,2} water units.\n", i + 1,
           (blk.Length - blk.Replace("≈≈", "").Length) / 2);
   }

}

</lang>

Output:

<lang>Block 1 retains 2 water units.

Block 2 retains 14 water units. Block 3 retains 35 water units. Block 4 retains 0 water units. Block 5 retains 0 water units. Block 6 retains 0 water units. Block 7 retains 0 water units.</lang>

Version 2

Conventional "scanning" algorithm, translated from the second version of Visual Basic.NET, but (intentionally tweaked to be) incapable of verbose output. See that version 2 entry for code comments and details. <lang cSharp>// Variable names key: // i Iterator (of the tower block array). // tba Tower block array. // tea Tower elevation array. // rht Right hand tower column number (position). // wu Water units (count). // bof Blocks on floor (count). // col Column number in elevation array (position).

static void Main(string[] args) { 

   int i = 1; int[][] tba = {new int[] { 1, 5, 3, 7, 2 },
   new int[] { 5, 3, 7, 2, 6, 4, 5, 9, 1, 2 },
   new int[] { 2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1 },
   new int[] { 5, 5, 5, 5 },  new int[] { 5, 6, 7, 8 },
   new int[] { 8, 7, 7, 6 },  new int[] { 6, 7, 10, 7, 6 }};
   foreach (var tea in tba)
   {
       int rht, wu = 0, bof; do
       {
           for (rht = tea.Length - 1; rht >= 0; rht--) if (tea[rht] > 0) break;
           if (rht < 0) break;
           bof = 0; for (int col = 0; col <= rht; col++)
           {
               if (tea[col] > 0) { tea[col] -= 1; bof += 1; }
               else if (bof > 0) wu++;
           }
           if (bof < 2) break;
       } while (true);
       System.Console.WriteLine(string.Format("Block {0} {1} water units.", i++,
           wu == 0 ? "does not hold any" : "holds " + wu.ToString()));
   }

}</lang> Output: <lang>Block 1 holds 2 water units. Block 2 holds 14 water units. Block 3 holds 35 water units. Block 4 does not hold any water units. Block 5 does not hold any water units. Block 6 does not hold any water units. Block 7 does not hold any water units.</lang>


Erlang

Implements a version that uses recursion to solve the problem functionally, using two passes without requiring list reversal or modifications. On the list iteration from head to tail, gather the largest element seen so far (being the highest one on the left). Once the list is scanned, each position returns the highest tower to its right as reported by its follower, along with the amount of water seen so far, which can then be used to calculate the value at the current position. Back at the first list element, the final result is gathered.

<lang erlang> -module(watertowers). -export([towers/1, demo/0]).

towers(List) -> element(2, tower(List, 0)).

tower([], _) -> {0,0}; tower([H|T], MaxLPrev) -> 

   MaxL = max(MaxLPrev, H),
   {MaxR, WaterAcc} = tower(T, MaxL),
   {max(MaxR,H), WaterAcc+max(0, min(MaxR,MaxL)-H)}.

demo() -> 

   Cases = [[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]],
   [io:format("~p -> ~p~n", [Case, towers(Case)]) || Case <- Cases],
   ok.

</lang>

Output:
1> watertowers:demo().
[1,5,3,7,2] -> 2
[5,3,7,2,6,4,5,9,1,2] -> 14
[2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1] -> 35
[5,5,5,5] -> 0
[5,6,7,8] -> 0
[8,7,7,6] -> 0
[6,7,10,7,6] -> 0
ok

F#

see http://stackoverflow.com/questions/24414700/water-collected-between-towers/43779936#43779936 for an explanation of this code. It is proportional to the number of towers. Although the examples on stackoverflow claim this, the n they use is actually the distance between the two end towers and not the number of towers. Consider the case of a tower of height 5 at 1, a tower of height 10 at 39, and a tower of height 3 at 101. <lang fsharp> (* A solution I'd show to Euclid !!!!. Nigel Galloway May 4th., 2017

  • )

let solve n = 

 let (n,_)::(i,e)::g = n|>List.sortBy(fun n->(-(snd n)))
 let rec fn i g e l =
   match e with
   | (n,e)::t when n < i -> fn n g t (l+(i-n-1)*e)
   | (n,e)::t when n > g -> fn i n t (l+(n-g-1)*e)
   | (n,t)::e            -> fn i g e (l-t)
   | _                   -> l
 fn (min n i) (max n i) g (e*(abs(n-i)-1))

</lang>

Output:
solve [(1,1);(2,5);(3,3);(4,7);(5,2)] -> 2
solve [(1,5);(2,3);(3,7);(4,2);(5,6);(6,4);(7,5);(8,9);(9,1);(10,2)] -> 14
solve [(1,2);(2,6);(3,3);(4,5);(5,2);(6,8);(7,1);(8,4);(9,2);(10,2);(11,5);(12,3);(13,5);(14,7);(15,4);(16,1)] -> 35
solve [(1,5);(2,5);(3,5);(4,5)] -> 0
solve [(1,5);(2,6);(3,7);(4,8)] -> 0
solve [(1,8);(2,7);(3,7);(4,6)] -> 0
solve [(1,6);(2,7);(3,10);(4,7);(5,6)] -> 0
solve [(1,5);(39,10);(101,3)] -> 368

Go

<lang go> package main

import "fmt"

func maxl(hm []int ) []int{ res := make([]int,len(hm)) max := 1 for i := 0; i < len(hm);i++{ if(hm[i] > max){ max = hm[i] } res[i] = max; } return res } func maxr(hm []int ) []int{ res := make([]int,len(hm)) max := 1 for i := len(hm) - 1 ; i >= 0;i--{ if(hm[i] > max){ max = hm[i] } res[i] = max; } return res } func min(a,b []int) []int { res := make([]int,len(a)) for i := 0; i < len(a);i++{ if a[i] >= b[i]{ res[i] = b[i] }else { res[i] = a[i] } } return res } func diff(hm, min []int) []int { res := make([]int,len(hm)) for i := 0; i < len(hm);i++{ if min[i] > hm[i]{ res[i] = min[i] - hm[i] } } return res } func sum(a []int) int { res := 0 for i := 0; i < len(a);i++{ res += a[i] } return res }

func waterCollected(hm []int) int { maxr := maxr(hm) maxl := maxl(hm) min := min(maxr,maxl) diff := diff(hm,min) sum := sum(diff) return sum }


func main() { fmt.Println(waterCollected([]int{1, 5, 3, 7, 2})) fmt.Println(waterCollected([]int{5, 3, 7, 2, 6, 4, 5, 9, 1, 2})) fmt.Println(waterCollected([]int{2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1})) fmt.Println(waterCollected([]int{5, 5, 5, 5})) fmt.Println(waterCollected([]int{5, 6, 7, 8})) fmt.Println(waterCollected([]int{8, 7, 7, 6})) fmt.Println(waterCollected([]int{6, 7, 10, 7, 6})) }</lang>

Output:
2
14
35
0
0
0
0

Haskell

Following the approach of cdk's Haskell solution at Stack Overflow:

<lang haskell>waterCollected :: [Int] -> Int waterCollected = 

 sum .                 -- Sum of the water depths over each of
 filter (> 0) .        -- the columns that are covered by some water.
 (
   zipWith (-) =<<     -- Where coverages are differences between:
   (                   
     zipWith min .     -- the lower water level in each case of:
     scanl1 max <*>    -- highest wall to left, and
     scanr1 max        -- highest wall to right.
   )
 )

main :: IO () main = 

 mapM_
   (print . waterCollected)
   [ [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]
   ]</lang>
Output:
2
14
35
0
0
0
0

JavaScript

ES5

Translation of: Haskell

<lang JavaScript>(function () { 

   'use strict';

   // waterCollected :: [Int] -> Int
   var waterCollected = function (xs) {
       return sum(                   // water above each bar
           zipWith(function (a, b) {
                   return a - b;     // difference between water level and bar
               },
               zipWith(min,          // lower of two flanking walls
                   scanl1(max, xs),  // highest walls to left
                   scanr1(max, xs)   // highest walls to right
               ), 
               xs                    // tops of bars
           )
           .filter(function (x) {
               return x > 0;         // only bars with water above them
           })
       );
   };

   // GENERIC FUNCTIONS ----------------------------------------

   // zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
   var zipWith = function (f, xs, ys) {
       var ny = ys.length;
       return (xs.length <= ny ? xs : xs.slice(0, ny))
           .map(function (x, i) {
               return f(x, ys[i]);
           });
   };

   // scanl1 is a variant of scanl that has no starting value argument
   // scanl1 :: (a -> a -> a) -> [a] -> [a]
   var scanl1 = function (f, xs) {
       return xs.length > 0 ? scanl(f, xs[0], xs.slice(1)) : [];
   };

   // scanr1 is a variant of scanr that has no starting value argument
   // scanr1 :: (a -> a -> a) -> [a] -> [a]
   var scanr1 = function (f, xs) {
       return xs.length > 0 ? scanr(f, xs.slice(-1)[0], xs.slice(0, -1)) : [];
   };

   // scanl :: (b -> a -> b) -> b -> [a] -> [b]
   var scanl = function (f, startValue, xs) {
       var lst = [startValue];
       return xs.reduce(function (a, x) {
           var v = f(a, x);
           return lst.push(v), v;
       }, startValue), lst;
   };

   // scanr :: (b -> a -> b) -> b -> [a] -> [b]
   var scanr = function (f, startValue, xs) {
       var lst = [startValue];
       return xs.reduceRight(function (a, x) {
           var v = f(a, x);
           return lst.push(v), v;
       }, startValue), lst.reverse();
   };

   // sum :: (Num a) => [a] -> a
   var sum = function (xs) {
       return xs.reduce(function (a, x) {
           return a + x;
       }, 0);
   };

   // max :: Ord a => a -> a -> a
   var max = function (a, b) {
       return a > b ? a : b;
   };

   // min :: Ord a => a -> a -> a
   var min = function (a, b) {
       return b < a ? b : a;
   };

   // TEST ---------------------------------------------------
   return [
       [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]
   ].map(waterCollected);

   //--> [2, 14, 35, 0, 0, 0, 0]

})();</lang>

Output:

<lang JavaScript>[2, 14, 35, 0, 0, 0, 0]</lang>

ES6

Translation of: Haskell

<lang JavaScript>(() => { 

   'use strict';
   
   // waterCollected :: [Int] -> Int
   const waterCollected = xs => {
       const maxToRight = scanr1(max, xs),
           maxToLeft = scanl1(max, xs),
           levels = zipWith(min, maxToLeft, maxToRight);

       return sum(zipWith(difference, levels, xs)
           .filter(x => x > 0));
   };



   // GENERIC FUNCTIONS ----------------------------------------

   // zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
   const zipWith = (f, xs, ys) => {
       const ny = ys.length;
       return (xs.length <= ny ? xs : xs.slice(0, ny))
           .map((x, i) => f(x, ys[i]));
   }

   // scanl1 is a variant of scanl that has no starting value argument
   // scanl1 :: (a -> a -> a) -> [a] -> [a]
   const scanl1 = (f, xs) =>
       xs.length > 0 ? scanl(f, xs[0], xs.slice(1)) : [];

   // scanr1 is a variant of scanr that has no starting value argument
   // scanr1 :: (a -> a -> a) -> [a] -> [a]
   const scanr1 = (f, xs) =>
       xs.length > 0 ? scanr(f, xs.slice(-1)[0], xs.slice(0, -1)) : [];

   // scanl :: (b -> a -> b) -> b -> [a] -> [b]
   const scanl = (f, startValue, xs) => {
       const lst = [startValue];
       return (
           xs.reduce((a, x) => {
               const v = f(a, x);
               return (lst.push(v), v);
           }, startValue),
           lst
       );
   };

   // scanr :: (b -> a -> b) -> b -> [a] -> [b]
   const scanr = (f, startValue, xs) => {
       const lst = [startValue];
       return (
           xs.reduceRight((a, x) => {
               const v = f(a, x);
               return (lst.push(v), v);
           }, startValue),
           lst.reverse()
       );
   };

   // difference :: (Num a) => a -> a -> a
   const difference = (a, b) => a - b;

   // sum :: (Num a) => [a] -> a
   const sum = xs => xs.reduce((a, x) => a + x, 0);

   // max :: Ord a => a -> a -> a
   const max = (a, b) => a > b ? a : b;

   // min :: Ord a => a -> a -> a
   const min = (a, b) => b < a ? b : a;



   // TEST ---------------------------------------------------
   return [
       [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]
   ].map(waterCollected);

   //--> [2, 14, 35, 0, 0, 0, 0]

})();</lang>

Output:

<lang JavaScript>[2, 14, 35, 0, 0, 0, 0]</lang>

Kotlin

Translation of: Python

<lang scala>// version 1.1.2

fun waterCollected(tower: IntArray): Int { 

   val n = tower.size
   val highLeft = listOf(0) + (1 until n).map { tower.slice(0 until it).max()!! }
   val highRight = (1 until n).map { tower.slice(it until n).max()!! } + 0
   return (0 until n).map { maxOf(minOf(highLeft[it], highRight[it]) - tower[it], 0) }.sum()

}

fun main(args: Array<String>) { 

   val towers = listOf(
       intArrayOf(1, 5, 3, 7, 2),
       intArrayOf(5, 3, 7, 2, 6, 4, 5, 9, 1, 2),
       intArrayOf(2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1),
       intArrayOf(5, 5, 5, 5),
       intArrayOf(5, 6, 7, 8),
       intArrayOf(8, 7, 7, 6),
       intArrayOf(6, 7, 10, 7, 6)
   )
   for (tower in towers) { 
       println("${"%2d".format(waterCollected(tower))} from ${tower.contentToString()}")
   }

}</lang>

Output:
 2 from [1, 5, 3, 7, 2]
14 from [5, 3, 7, 2, 6, 4, 5, 9, 1, 2]
35 from [2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1]
 0 from [5, 5, 5, 5]
 0 from [5, 6, 7, 8]
 0 from [8, 7, 7, 6]
 0 from [6, 7, 10, 7, 6]

Perl

<lang perl>use Modern::Perl; use List::Util qw{ min max sum };

sub water_collected { 

   my @t = map { { TOWER => $_, LEFT => 0, RIGHT => 0, LEVEL => 0 } } @_;

   my ( $l, $r ) = ( 0, 0 );
   $_->{LEFT}  = ( $l = max( $l, $_->{TOWER} ) ) for @t;
   $_->{RIGHT} = ( $r = max( $r, $_->{TOWER} ) ) for reverse @t;
   $_->{LEVEL} = min( $_->{LEFT}, $_->{RIGHT} )  for @t;

   return sum map { $_->{LEVEL} > 0 ? $_->{LEVEL} - $_->{TOWER} : 0 } @t;

}

say join ' ', map { water_collected( @{$_} ) } ( 

   [ 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 ],

);</lang>

Output:
2 14 35 0 0 0 0

Perl 6

Translation of: Haskell

<lang perl6>sub max_l ( @a ) { [\max] @a } sub max_r ( @a ) { ([\max] @a.reverse).reverse }

sub water_collected ( @towers ) { 

   return 0 if @towers <= 2;

   my @levels = max_l(@towers) »min« max_r(@towers);

   return ( @levels »-« @towers ).grep( * > 0 ).sum;

}

say map &water_collected, 

   [ 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 ],
</lang>
Output:
(2 14 35 0 0 0 0)

Python

Based on the algorithm explained at Stack Overflow:

<lang python>def water_collected(tower): 

   N = len(tower)
   highest_left = [0] + [max(tower[:n]) for n in range(1,N)]
   highest_right = [max(tower[n:N]) for n in range(1,N)] + [0]
   water_level = [max(min(highest_left[n], highest_right[n]) - tower[n], 0)
       for n in range(N)]
   print("highest_left:  ", highest_left)
   print("highest_right: ", highest_right)
   print("water_level:   ", water_level)
   print("tower_level:   ", tower)
   print("total_water:   ", sum(water_level))
   print("")
   return sum(water_level)

towers = [[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]]

[water_collected(tower) for tower in towers]</lang>

Output:
highest_left:   [0, 1, 5, 5, 7]
highest_right:  [7, 7, 7, 2, 0]
water_level:    [0, 0, 2, 0, 0]
tower_level:    [1, 5, 3, 7, 2]
total_water:    2

highest_left:   [0, 5, 5, 7, 7, 7, 7, 7, 9, 9]
highest_right:  [9, 9, 9, 9, 9, 9, 9, 2, 2, 0]
water_level:    [0, 2, 0, 5, 1, 3, 2, 0, 1, 0]
tower_level:    [5, 3, 7, 2, 6, 4, 5, 9, 1, 2]
total_water:    14

highest_left:   [0, 2, 6, 6, 6, 6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8]
highest_right:  [8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 4, 1, 0]
water_level:    [0, 0, 3, 1, 4, 0, 6, 3, 5, 5, 2, 4, 2, 0, 0, 0]
tower_level:    [2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1]
total_water:    35

highest_left:   [0, 5, 5, 5]
highest_right:  [5, 5, 5, 0]
water_level:    [0, 0, 0, 0]
tower_level:    [5, 5, 5, 5]
total_water:    0

highest_left:   [0, 5, 6, 7]
highest_right:  [8, 8, 8, 0]
water_level:    [0, 0, 0, 0]
tower_level:    [5, 6, 7, 8]
total_water:    0

highest_left:   [0, 8, 8, 8]
highest_right:  [7, 7, 6, 0]
water_level:    [0, 0, 0, 0]
tower_level:    [8, 7, 7, 6]
total_water:    0

highest_left:   [0, 6, 7, 10, 10]
highest_right:  [10, 10, 7, 6, 0]
water_level:    [0, 0, 0, 0, 0]
tower_level:    [6, 7, 10, 7, 6]
total_water:    0

[2, 14, 35, 0, 0, 0, 0]

Racket

<lang racket>#lang racket/base (require racket/match)

(define (water-collected-between-towers towers) 

 (define (build-tallest-left/rev-list t mx/l rv)
   (match t
     [(list) rv]
     [(cons a d)
      (define new-mx/l (max a mx/l))
      (build-tallest-left/rev-list d new-mx/l (cons mx/l rv))]))

 (define (collect-from-right t tallest/l mx/r rv)
   (match t
     [(list) rv]
     [(cons a d)
      (define new-mx/r (max a mx/r))
      (define new-rv (+ rv (max (- (min new-mx/r (car tallest/l)) a) 0)))
      (collect-from-right d (cdr tallest/l) new-mx/r new-rv)]))

 (define reversed-left-list (build-tallest-left/rev-list towers 0 null))  
 (collect-from-right (reverse towers) reversed-left-list 0 0))

(module+ test 

 (require rackunit)
 (check-equal?
  (let ((towerss
         '[[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]]))
    (map water-collected-between-towers towerss))
  (list 2 14 35 0 0 0 0)))</lang>

When run produces no output -- meaning that the tests have run successfully.

REXX

version 1

<lang rexx>/* REXX */ Call bars '1 5 3 7 2' Call bars '5 3 7 2 6 4 5 9 1 2' Call bars '2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1' Call bars '5 5 5 5' Call bars '5 6 7 8' Call bars '8 7 7 6' Call bars '6 7 10 7 6' Exit bars: Parse Arg bars bar.0=words(bars) high=0 box.=' ' Do i=1 To words(bars) 

 bar.i=word(bars,i)
 high=max(high,bar.i)
 Do j=1 To bar.i
   box.i.j='x'
   End
 End

m=1 w=0 Do Forever 

 Do i=m+1 To bar.0
   If bar.i>bar.m Then
     Leave
   End
 If i>bar.0 Then Leave
 n=i
 Do i=m+1 To n-1
   w=w+bar.m-bar.i
   Do j=bar.i+1 To bar.m
     box.i.j='*'
     End
   End
 m=n
 End

m=bar.0 Do Forever 

 Do i=bar.0 To 1 By -1
   If bar.i>bar.m Then
     Leave
   End
 If i<1 Then Leave
 n=i
 Do i=m-1 To n+1 By -1
   w=w+bar.m-bar.i
   Do j=bar.i+1 To bar.m
     box.i.j='*'
     End
   End
 m=n
 End

Say bars '->' w Call show Return show: Do j=high To 1 By -1 

 ol=
 Do i=1 To bar.0
   ol=ol box.i.j
   End
 Say ol
 End

Return</lang>

Output:
1 5 3 7 2 -> 2
       x
       x
   x * x
   x * x
   x x x
   x x x x
 x x x x x
5 3 7 2 6 4 5 9 1 2 -> 14
               x
               x
     x * * * * x
     x * x * * x
 x * x * x * x x
 x * x * x x x x
 x x x * x x x x
 x x x x x x x x * x
 x x x x x x x x x x
2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1 -> 35
           x
           x * * * * * * * x
   x * * * x * * * * * * * x
   x * x * x * * * * x * x x
   x * x * x * x * * x * x x x
   x x x * x * x * * x x x x x
 x x x x x x * x x x x x x x x
 x x x x x x x x x x x x x x x x
5 5 5 5 -> 0
 x x x x
 x x x x
 x x x x
 x x x x
 x x x x
5 6 7 8 -> 0
       x
     x x
   x x x
 x x x x
 x x x x
 x x x x
 x x x x
 x x x x
8 7 7 6 -> 0
 x
 x x x
 x x x x
 x x x x
 x x x x
 x x x x
 x x x x
 x x x x
6 7 10 7 6 -> 0
     x
     x
     x
   x x x
 x x x x x
 x x x x x
 x x x x x
 x x x x x
 x x x x x
 x x x x x

version 2

<lang rexx>/*REXX program calculates and displays the amount of rainwater collected between towers.*/ call tower 1 5 3 7 2 call tower 5 3 7 2 6 4 5 9 1 2 call tower 2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1 call tower 5 5 5 5 call tower 5 6 7 8 call tower 8 7 7 6 call tower 6 7 10 7 6 exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ tower: procedure; arg y; #=words(y); t.=0; L.=0 /*the T. array holds the tower heights.*/ 

           do j=1  for #;   t.j=word(y, j)      /*construct the towers,                */
           _=j-1;           L.j=max(t._, L._)   /*    "      "  left-most tallest tower*/
           end   /*j*/
      R.=0
           do b=#  by -1  for #;  _=b+1;  R.b=max(t._, R._)  /*right-most tallest tower*/
           end   /*b*/
      w.=0                                                       /*rainwater collected.*/
           do f=1  for #;  if t.f>=L.f | t.f>=R.f  then iterate  /*rain between towers?*/
           w.f=min(L.f, R.f) - t.f;      w.00=w.00+w.f           /*rainwater collected.*/
           end   /*f*/
      say right(w.00,9) 'units of rainwater collected for: '  y  /*display water units.*/
      return</lang>

output 

        2 units of rainwater collected for:  1 5 3 7 2
       14 units of rainwater collected for:  5 3 7 2 6 4 5 9 1 2
       35 units of rainwater collected for:  2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1
        0 units of rainwater collected for:  5 5 5 5
        0 units of rainwater collected for:  5 6 7 8
        0 units of rainwater collected for:  8 7 7 6
        0 units of rainwater collected for:  6 7 10 7 6

version 3

This REXX version shows a scale and a representation of the towers and water collected. <lang rexx>/*REXX program calculates and displays the amount of rainwater collected between towers.*/ 

      call tower  1  5  3  7  2
      call tower  5  3  7  2  6  4  5  9  1  2
      call tower  2  6  3  5  2  8  1  4  2  2  5  3  5  7  4  1
      call tower  5  5  5  5
      call tower  5  6  7  8
      call tower  8  7  7  6
      call tower  6  7 10  7  6

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ tower: procedure; arg y; #=words(y); t.=0; L.=0 /*the T. array holds the tower heights.*/ 

           do j=1  for #;  t.j=word(y,j); _=j-1 /*construct the towers;  max height.   */
           L.j=max(t._, L._); t.0=max(t.0, t.j) /*left-most tallest tower; build scale.*/
           end   /*j*/
      R.=0
           do b=#  by -1  for #;  _=b+1;  R.b=max(t._, R._)  /*right-most tallest tower*/
           end   /*b*/
      w.=0                                                       /*rainwater collected.*/
           do f=1  for #;  if t.f>=L.f | t.f>=R.f  then iterate  /*rain between towers?*/
           w.f=min(L.f, R.f) - t.f;      w.00=w.00+w.f           /*rainwater collected.*/
           end   /*f*/
      if w.00==0  then w.00='no'                /*pretty up wording for "no rainwater".*/
      p.=                                       /*P.  stores plot versions of towers.  */
           do c=0  to #                         /*construct the plot+scale for display.*/
             do h=1  for t.c+w.c;     glyph='█' /*maybe show a floor of some tower(s). */
                       if h>t.c  then glyph='≈' /*  "     "  rainwater between towers. */
             if c==0  then p.h=overlay(right(h, 9), p.h,  1  )  /*place the tower scale*/
                      else p.h=overlay(glyph      , p.h, 10+c)  /*build the tower.     */
             end   /*h*/
           end     /*c*/
      p.1=overlay(w.00  'units of rainwater collected', p.1, 15+#)   /*append the text.*/
           do z=t.0  by -1  to 0;     say p.z   /*display various tower floors & water.*/
           end     /*z*/
      return</lang>

output 

        7    █
        6    █
        5  █≈█
        4  █≈█
        3  ███
        2  ████
        1 █████    2 units of rainwater collected

        9        █
        8        █
        7   █≈≈≈≈█
        6   █≈█≈≈█
        5 █≈█≈█≈██
        4 █≈█≈████
        3 ███≈████
        2 ████████≈█
        1 ██████████    14 units of rainwater collected

        8      █
        7      █≈≈≈≈≈≈≈█
        6  █≈≈≈█≈≈≈≈≈≈≈█
        5  █≈█≈█≈≈≈≈█≈██
        4  █≈█≈█≈█≈≈█≈███
        3  ███≈█≈█≈≈█████
        2 ██████≈████████
        1 ████████████████    35 units of rainwater collected

        5 ████
        4 ████
        3 ████
        2 ████
        1 ████    no units of rainwater collected

        8    █
        7   ██
        6  ███
        5 ████
        4 ████
        3 ████
        2 ████
        1 ████    no units of rainwater collected

        8 █
        7 ███
        6 ████
        5 ████
        4 ████
        3 ████
        2 ████
        1 ████    no units of rainwater collected

       10   █
        9   █
        8   █
        7  ███
        6 █████
        5 █████
        4 █████
        3 █████
        2 █████
        1 █████    no units of rainwater collected

Ruby

<lang ruby> def a(array) n=array.length left={} right={} left[0]=array[0] i=1 loop do 

  break if i >=n

left[i]=[left[i-1],array[i]].max 

  i += 1

end right[n-1]=array[n-1] i=n-2 loop do break if i<0 

right[i]=[right[i+1],array[i]].max

i-=1 end i=0 water=0 loop do break if i>=n water+=[left[i],right[i]].min-array[i] i+=1 end puts water end

a([ 5, 3, 7, 2, 6, 4, 5, 9, 1, 2 ]) a([ 2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1 ]) a([ 5, 5, 5, 5 ]) a([ 5, 6, 7, 8 ]) a([ 8, 7, 7, 6 ]) a([ 6, 7, 10, 7, 6 ]) return</lang> output 

14
35
0
0
0
0

Scheme

<lang scheme> (import (scheme base) 

       (scheme write))

(define (total-collected chart) 

 (define (highest-left vals curr)
   (if (null? vals)
     (list curr)
     (cons curr
           (highest-left (cdr vals) (max (car vals) curr)))))
 (define (highest-right vals curr)
   (reverse (highest-left (reverse vals) curr)))
 ;
 (if (< (length chart) 3) ; catch the end cases
   0
   (apply +
          (map (lambda (l c r) 
                 (if (or (<= l c)
                         (<= r c))
                   0
                   (- (min l r) c)))
               (highest-left chart 0)
               chart 
               (highest-right chart 0)))))

(for-each 

 (lambda (chart)
   (display chart) (display " -> ") (display (total-collected chart)) (newline))
 '((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)))

</lang>

Output:
(1 5 3 7 2) -> 2
(5 3 7 2 6 4 5 9 1 2) -> 14
(2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1) -> 35
(5 5 5 5) -> 0
(5 6 7 8) -> 0
(8 7 7 6) -> 0
(6 7 10 7 6) -> 0
(3 1 2) -> 1
(1) -> 0
() -> 0
(1 2) -> 0

Sidef

<lang ruby>func max_l(Array a, m = a[0]) { 

   gather { a.each {|e| take(m = max(m, e)) } }

}

func max_r(Array a) { 

   max_l(a.flip).flip

}

func water_collected(Array towers) { 

   var levels = (max_l(towers) »min« max_r(towers))
   (levels »-« towers).grep{ _ > 0 }.sum

}

[ 

   [ 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 ],

].map { water_collected(_) }.say</lang>

Output:
[2, 14, 35, 0, 0, 0, 0]

Tcl

Tcl makes for a surprisingly short and readable implementation, next to some of the more functional-oriented languages. <lang Tcl>namespace path {::tcl::mathfunc ::tcl::mathop}

proc flood {ground} { 

   set lefts [
       set d 0
       lmap g $ground {
           set d [max $d $g]
       }
   ]
   set ground [lreverse $ground]
   set rights [
       set d 0
       lmap g $ground {
           set d [max $d $g]
       }
   ]
   set rights [lreverse $rights]
   set ground [lreverse $ground]
   set water [lmap l $lefts r $rights {min $l $r}]
   set depths [lmap g $ground w $water {- $w $g}]
   + {*}$depths

}

foreach p { 

   {5 3 7 2 6 4 5 9 1 2}
   {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}

} { 

   puts [flood $p]:\t$p

}</lang>

Output:
14:        5 3 7 2 6 4 5 9 1 2
2:      1 5 3 7 2
14:     5 3 7 2 6 4 5 9 1 2
35:     2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1
0:      5 5 5 5
0:      5 6 7 8
0:      8 7 7 6
0:      6 7 10 7 6

Visual Basic .NET

Version 1

Method: Instead of "scanning" adjoining towers for each column, convert the tower data into a string representation with building blocks, empty spaces, and potential water retention sites. Then "erode" away the water retention sites that are unsupported. This is accomplished with the String Replace() function. The replace operations are unleashed upon the entire "block" of towers, rather than a cell at a time or a line at a time - which perhaps increases the program's execution-time, but reduces program's complexity.

The program can optionally display the interim string representation of each tower block before the final count is completed. I've since modified it to have the same block and wavy characters are the REXX 9.3 output, but used the double-wide columns, as pictured in the task definition area. <lang vbnet>' Convert tower block data into a string representation, then manipulate that. Sub Main() 

   Dim shoTow As Boolean = Environment.GetCommandLineArgs().Count > 1 ' Show towers.
   Dim wta As Integer()() = {                      ' water tower array (input data).
       New Integer() {1, 5, 3, 7, 2}, New Integer() {5, 3, 7, 2, 6, 4, 5, 9, 1, 2},
       New Integer() {2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1},
       New Integer() {5, 5, 5, 5}, New Integer() {5, 6, 7, 8},
       New Integer() {8, 7, 7, 6}, New Integer() {6, 7, 10, 7, 6}}
   Dim blk As String,                   ' String representation of a block of towers.
       lf As String = vbCrLf     ' Line feed to separate floors in a block of towers.
   For i As Integer = 0 To UBound(wta)
       Dim bpf As Integer                    ' Count of tower blocks found per floor.
       blk = ""
       Do
           bpf = 0 : Dim floor As String = ""  ' string representation of each floor.
           For j As Integer = 0 To UBound(wta(i))
               If wta(i)(j) > 0 Then      ' Tower block detected, add block to floor,
                   floor &= "██" : wta(i)(j) -= 1 : bpf += 1   '  reduce tower by one.
               Else  '      Empty space detected, fill when not first or last column.
                   ' "Almost equal to" characters are possible water retention cells.
                   floor &= If(j > 0 AndAlso j < UBound(wta(i)), "≈≈", "  ")
               End If
           Next
           If bpf > 0 Then blk = floor & lf & blk ' Add floors until blocks are gone.
       Loop Until bpf = 0                       ' No tower blocks left, so terminate.
       ' Now erode potential water retention cells from left and right
       While blk.Contains("  ≈≈") : blk = Replace(blk, "  ≈≈", "    ") : End While
       While blk.Contains("≈≈  ") : blk = Replace(blk, "≈≈  ", "    ") : End While
       ' Optionally show towers w/ water marks.
       If shoTow Then Console.Write("{0}{1}", lf, Wide(blk))
       ' Now remove all building blocks and whitespace, leaving only water marks.
       ' Then count the remaining characters with the Len() function.
       Console.Write("Block {0} retains {1,2} water units.{2}", i + 1,
                                    (Len(blk) - Len(Replace(blk, "≈≈", ""))) \ 2, lf)
   Next

End Sub</lang>

Output:

<lang>Block 1 retains 2 water units.

Block 2 retains 14 water units. Block 3 retains 35 water units. Block 4 retains 0 water units. Block 5 retains 0 water units. Block 6 retains 0 water units. Block 7 retains 0 water units.</lang> Verbose output shows towers with water ("Almost equal to" characters) left in the "wells" between towers. Just supply any command-line parameter to see it. Use no command line parameters to see the plain output above. <lang> ██ 

     ██
 ██≈≈██
 ██≈≈██
 ██████
 ████████

██████████ Block 1 retains 2 water units. 

             ██
             ██
   ██≈≈≈≈≈≈≈≈██
   ██≈≈██≈≈≈≈██

██≈≈██≈≈██≈≈████ ██≈≈██≈≈████████ ██████≈≈████████ ████████████████≈≈██ ████████████████████ Block 2 retains 14 water units. 

         ██
         ██≈≈≈≈≈≈≈≈≈≈≈≈≈≈██
 ██≈≈≈≈≈≈██≈≈≈≈≈≈≈≈≈≈≈≈≈≈██
 ██≈≈██≈≈██≈≈≈≈≈≈≈≈██≈≈████
 ██≈≈██≈≈██≈≈██≈≈≈≈██≈≈██████
 ██████≈≈██≈≈██≈≈≈≈██████████

████████████≈≈████████████████ ████████████████████████████████ Block 3 retains 35 water units.

████████ ████████ ████████ ████████ ████████ Block 4 retains 0 water units. 

     ██
   ████
 ██████

████████ ████████ ████████ ████████ ████████ Block 5 retains 0 water units.

██ ██████ ████████ ████████ ████████ ████████ ████████ ████████ Block 6 retains 0 water units. 

   ██
   ██
   ██
 ██████

██████████ ██████████ ██████████ ██████████ ██████████ ██████████ Block 7 retains 0 water units.</lang>

Version 2

Method: More conventional "scanning" method. A Char array is used, but no Replace() statements. Output is similar to version 1, although there is now a left margin of three spaces, the results statement is immediately to the right of the string representation of the tower blocks (instead of underneath), the verb is "hold(s)" instead of "retains", and there is a special string when the results indicate zero.

<lang vbnet> <summary> 

    wide - Widens the aspect ratio of a linefeed separated string.
    </summary>
    <param name="src">A string representing a block of towers.</param>
    <param name="margin">Optional padding for area to the left.</param>
    <returns>A double-wide version of the string.</returns>
   Function wide(src As String, Optional margin As String = "") As String
       Dim res As String = margin : For Each ch As Char In src
           res += If(ch < " ", ch & margin, ch + ch) : Next : Return res
   End Function

    <summary>
    cntChar - Counts characters, also custom formats the output.
    </summary>
    <param name="src">The string to count characters in.</param>
    <param name="ch">The character to be counted.</param>
    <param name="verb">Verb to include in format.  Expecting "hold",
                but can work with "retain" or "have".</param>
    <returns>The count of chars found in a string, and formats a verb.</returns>
   Function cntChar(src As String, ch As Char, verb As String) As String
       Dim cnt As Integer = 0
       For Each c As Char In src : cnt += If(c = ch, 1, 0) : Next
       Return If(cnt = 0, "does not " & verb & " any",
           verb.Substring(0, If(verb = "have", 2, 4)) & "s " & cnt.ToString())
   End Function

    <summary>
    report - Produces a report of the number of rain units found in 
             a block of towers, optionally showing the towers.
             Autoincrements the blkID for each report.
    </summary>
    <param name="tea">An int array with tower elevations.</param>
    <param name="blkID">An int of the block of towers ID.</param>
    <param name="verb">The verb to use in the description.
                       Defaults to "has / have".</param>
    <param name="showIt">When true, the report includes a string representation
                         of the block of towers.</param>
    <returns>A string containing the amount of rain units, optionally preceeded by
             a string representation of the towers holding any water.</returns>
   Function report(tea As Integer(),                             ' Tower elevation array.
                   ByRef blkID As Integer,                ' Block ID for the description.
                   Optional verb As String = "have",    ' Verb to use in the description.
                   Optional showIt As Boolean = False) As String    ' Show representaion.
       Dim block As String = "",                                   ' The block of towers.
           lf As String = vbLf,                           ' The separator between floors.
           rTwrPos As Integer        ' The position of the rightmost tower of this floor.
       Do
           For rTwrPos = tea.Length - 1 To 0 Step -1      ' Determine the rightmost tower
               If tea(rTwrPos) > 0 Then Exit For          '      postition on this floor.
           Next
           If rTwrPos < 0 Then Exit Do         ' When no towers remain, exit the do loop.
           ' init the floor to a space filled Char array, as wide as the block of towers.
           Dim floor As Char() = New String(" ", tea.Length).ToCharArray()
           Dim bpf As Integer = 0                  ' The count of blocks found per floor.
           For column As Integer = 0 To rTwrPos                ' Scan from left to right.
               If tea(column) > 0 Then                     ' If a tower exists here,
                   floor(column) = "█"                     ' mark the floor with a block,
                   tea(column) -= 1                    ' drop the tower elevation by one,
                   bpf += 1                           ' and advance the block count.
               ElseIf bpf > 0 Then    ' Otherwise, see if a tower is present to the left.
                   floor(column) = "≈"                           ' OK to fill with water.
               End If
           Next
           If bpf > If(showIt, 0, 1) Then       ' Continue the building only when needed.
               ' If not showing blocks, discontinue building when a single tower remains.
               ' build tower blocks string with each floor added to top.
               block = New String(floor) & If(block = "", "", lf) & block
           Else
               Exit Do                          ' Ran out of towers, so exit the do loop.
           End If
       Loop While True ' Depending on previous break statements to terminate the do loop.
       blkID += 1                                           ' increment block ID counter.
       ' format report and return it.
       Return If(showIt, String.Format(vbLf & "{0}", wide(block, "   ")), "") &
           String.Format(" Block {0} {1} water units.", blkID, cntChar(block, "≈", verb))
   End Function

    <summary>
    Main routine.
    
    With one command line parameter, it shows tower blocks,
     with no command line parameters, it shows a plain report
   </summary>
   Sub Main()
       Dim shoTow As Boolean = Environment.GetCommandLineArgs().Count > 1  ' Show towers.
       Dim blkCntr As Integer = 0        ' Block ID for reports.
       Dim verb As String = "hold"    ' "retain" or "have" can be used instead of "hold".
       Dim tea As Integer()() = {New Integer() {1, 5, 3, 7, 2},   ' Tower elevation data.
           New Integer() {5, 3, 7, 2, 6, 4, 5, 9, 1, 2},
           New Integer() {2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1},
           New Integer() {5, 5, 5, 5}, New Integer() {5, 6, 7, 8},
           New Integer() {8, 7, 7, 6}, New Integer() {6, 7, 10, 7, 6}}
       For Each block As Integer() In tea
           ' Produce report for each block of towers.
           Console.WriteLine(report(block, blkCntr, verb, shoTow))
       Next
   End Sub</lang>

Regular version 2 output: <lang> Block 1 holds 2 water units. 

Block 2 holds 14 water units.
Block 3 holds 35 water units.
Block 4 does not hold any water units.
Block 5 does not hold any water units.
Block 6 does not hold any water units.
Block 7 does not hold any water units.</lang>

Sample of version 2 verbose output: <lang> ██ 

            ██≈≈≈≈≈≈≈≈≈≈≈≈≈≈██
    ██≈≈≈≈≈≈██≈≈≈≈≈≈≈≈≈≈≈≈≈≈██
    ██≈≈██≈≈██≈≈≈≈≈≈≈≈██≈≈████
    ██≈≈██≈≈██≈≈██≈≈≈≈██≈≈██████
    ██████≈≈██≈≈██≈≈≈≈██████████
  ████████████≈≈████████████████
  ████████████████████████████████ Block 3 holds 35 water units.

  ████████
  ████████
  ████████
  ████████
  ████████ Block 4 does not hold any water units.</lang>

zkl

Translation of: Haskell

<lang zkl>fcn waterCollected(walls){ 

    // compile max wall heights from left to right and right to left
    // then each pair is left/right wall of that cell.
    // Then the min of each wall pair == water height for that cell
  scanl(walls,(0).max)     // scan to right, f is max(0,a,b)
 .zipWith((0).MAX.min,     // f is MAX.min(a,b) == min(a,b)
          scanl(walls.reverse(),(0).max).reverse()) // right to left
    // now subtract the wall height from the water level and add 'em up
  .zipWith('-,walls).filter('>(0)).sum(0);

} fcn scanl(xs,f,i=0){ // aka reduce but save list of results 

  xs.reduce('wrap(s,x,a){ s=f(s,x); a.append(s); s },i,ss:=List()); 
  ss

} // scanl((1,5,3,7,2),max,0) --> (1,5,5,7,7)</lang> <lang zkl>T( T(1, 5, 3, 7, 2), T(5, 3, 7, 2, 6, 4, 5, 9, 1, 2), 

  T(2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1),
  T(5, 5, 5, 5), T(5, 6, 7, 8),T(8, 7, 7, 6),
  T(6, 7, 10, 7, 6) )

.pump(List, waterCollected).println();</lang>

Output:
L(2,14,35,0,0,0,0)
Retrieved from "https://rosettacode.org/wiki/Water_collected_between_towers?oldid=271751"