Water collected between towers: Difference between revisions
m (The character chosen for the "water" in the wells between the towers looked like it was overflowing. I changed it from "░" to the character ("Almost equal to") used by the REXX 9.3 output charts. My apologies if it was fine on other browsers or systems.) |
m (→{{header|Visual Basic .NET}}: changed the name of Rexx 9.3 to Rexx version 3.) |
||
| Line 1,230: | Line 1,230: | ||
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 |
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 |
||
[[{{FULLPAGENAME}}#version_3|REXX |
[[{{FULLPAGENAME}}#version_3|REXX version 3]] output. |
||
<lang vbnet>' Convert tower block data into a string representation, then manipulate that. |
<lang vbnet>' Convert tower block data into a string representation, then manipulate that. |
||
Sub Main() |
Sub Main() |
||
Revision as of 00:32, 3 May 2017
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:
- 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.
AppleScript
<lang AppleScript>-- 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 lambda(x)
x > 0
end lambda
end script
-- minus :: Num a => a -> a -> a
script minus
on lambda(a, b)
a - b
end lambda
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 ------------------------------------------------------
-- 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
-- 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
-- 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 lambda(v, item i of xs, i, xs)
set end of lst to v
end repeat
return lst
end tell
end scanl
-- 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 lambda(v, item i of xs, i, xs)
set end of lst to v
end repeat
return reverse of lst
end tell
end scanr
-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] on zipWith(f, xs, ys)
set nx to length of xs
set ny to length of ys
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 zipWith
-- 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 on sum(xs)
script add
on lambda(a, b)
a + b
end lambda
end script
foldl(add, 0, xs)
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] on tail(xs)
if length of xs > 1 then
items 2 thru -1 of xs
else
{}
end if
end tail
-- 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
-- cond :: Bool -> a -> a -> a on cond(bool, f, g)
if bool then
f
else
g
end if
end cond</lang>
- Output:
<lang AppleScript>{2, 14, 35, 0, 0, 0, 0}</lang>
AWK
<lang AWK>
- 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#
Translation from Visual Basic .NET. See that 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.Replace(lf, "").Replace("B", "").Replace(" ", "")).Length);
}
}
</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>
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 xs =
sum $ -- Sum of water depths over each of:
filter (> 0) $ -- the columns that are covered by some water.
zipWith
(-) -- Where coverages are differences between
(zipWith
min -- water levels, (lower in each case of:
(scanl1 max xs) -- highest wall to left, and
(scanr1 max xs) -- highest wall to right)
)
xs -- and column tops.
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
<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
<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>
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
<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]
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
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 version 3 output. <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, 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(Replace(Replace(Replace(blk, lf, ""), "█", ""), " ", "")), 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>
zkl
<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)