Water collected between towers: Difference between revisions
(→{{header|Wren}}: Now uses new core library method.) |
imported>Thebeez (uBasic/4tH - eliminated a global) |
||
(27 intermediate revisions by 15 users not shown) | |||
Line 44: | Line 44: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">F water_collected(tower) |
||
V l = tower.len |
V l = tower.len |
||
V highest_left = [0] [+] (1 .< l).map(n -> max(@tower[0 .< n])) |
V highest_left = [0] [+] (1 .< l).map(n -> max(@tower[0 .< n])) |
||
Line 66: | Line 66: | ||
[6, 7, 10, 7, 6]] |
[6, 7, 10, 7, 6]] |
||
print(towers.map(tower -> water_collected(tower)))</ |
print(towers.map(tower -> water_collected(tower)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 94: | Line 94: | ||
=={{header|8080 Assembly}}== |
=={{header|8080 Assembly}}== |
||
< |
<syntaxhighlight lang="8080asm"> org 100h |
||
jmp demo |
jmp demo |
||
;;; Calculate the amount of water a row of towers will hold |
;;; Calculate the amount of water a row of towers will hold |
||
Line 198: | Line 198: | ||
dw t6,t7-t6 |
dw t6,t7-t6 |
||
dw t7,t_end-t7 |
dw t7,t_end-t7 |
||
dw 0</ |
dw 0</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 205: | Line 205: | ||
=={{header|8086 Assembly}}== |
=={{header|8086 Assembly}}== |
||
< |
<syntaxhighlight lang="asm"> cpu 8086 |
||
org 100h |
org 100h |
||
section .text |
section .text |
||
Line 286: | Line 286: | ||
dw t6,t7-t6 |
dw t6,t7-t6 |
||
dw t7,t_end-t7 |
dw t7,t_end-t7 |
||
dw 0</ |
dw 0</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 293: | Line 293: | ||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
< |
<syntaxhighlight lang="action!">PROC PrintArray(BYTE ARRAY a BYTE len) |
||
BYTE i |
BYTE i |
||
Line 367: | Line 367: | ||
Test(a6,4) |
Test(a6,4) |
||
Test(a7,5) |
Test(a7,5) |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Water_collected_between_towers.png Screenshot from Atari 8-bit computer] |
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Water_collected_between_towers.png Screenshot from Atari 8-bit computer] |
||
Line 384: | Line 384: | ||
[6 7 10 7 6] holds 0 water units |
[6 7 10 7 6] holds 0 water units |
||
</pre> |
|||
=={{header|Ada}}== |
|||
<syntaxhighlight lang="ada">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;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The series: [ 1 5 3 7 2 ] holds 2 units of water. |
|||
The series: [ 5 3 7 2 6 4 5 9 1 2 ] holds 14 units of water. |
|||
The series: [ 2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1 ] holds 35 units of water. |
|||
The series: [ 5 5 5 5 ] holds 0 units of water. |
|||
The series: [ 5 6 7 8 ] holds 0 units of water. |
|||
The series: [ 8 7 7 6 ] holds 0 units of water. |
|||
The series: [ 6 7 10 7 6 ] holds 0 units of water. |
|||
</pre> |
</pre> |
||
Line 389: | Line 477: | ||
{{Trans|JavaScript}} |
{{Trans|JavaScript}} |
||
< |
<syntaxhighlight lang="applescript">--------------- WATER COLLECTED BETWEEN TOWERS ------------- |
||
-- waterCollected :: [Int] -> Int |
-- waterCollected :: [Int] -> Int |
||
Line 585: | Line 673: | ||
return lst |
return lst |
||
end tell |
end tell |
||
end zipWith</ |
end zipWith</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang="applescript">{2, 14, 35, 0, 0, 0, 0}</syntaxhighlight> |
||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="arturo">cmax: function => [ |
|||
m: neg ∞ |
|||
map & 'x -> m:<=max @[m x] |
|||
] |
|||
vmin: $ => [map couple & & => min] |
|||
vsub: $ => [map couple & & 'p -> p\0 - p\1] |
|||
water: function [a][ |
|||
sum vsub vmin reverse cmax reverse a cmax a a |
|||
] |
|||
loop [ |
|||
[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] |
|||
] 'a -> print [a "->" water a]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[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</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">WCBT(oTwr){ |
||
topL := Max(oTwr*), l := num := 0, barCh := lbarCh := "", oLvl := [] |
topL := Max(oTwr*), l := num := 0, barCh := lbarCh := "", oLvl := [] |
||
while (++l <= topL) |
while (++l <= topL) |
||
Line 605: | Line 728: | ||
} |
} |
||
return [num, barCh] |
return [num, barCh] |
||
}</ |
}</syntaxhighlight> |
||
Examples:< |
Examples:<syntaxhighlight lang="autohotkey">data := [[1, 5, 3, 7, 2] |
||
,[5, 3, 7, 2, 6, 4, 5, 9, 1, 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] |
,[2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1] |
||
Line 623: | Line 746: | ||
result .= "Chart " inp " has " x.1 " water units`n" x.2 "------------------------`n" |
result .= "Chart " inp " has " x.1 " water units`n" x.2 "------------------------`n" |
||
} |
} |
||
MsgBox % result</ |
MsgBox % result</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Chart [1, 5, 3, 7, 2] has 2 water units |
<pre>Chart [1, 5, 3, 7, 2] has 2 water units |
||
Line 696: | Line 819: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f WATER_COLLECTED_BETWEEN_TOWERS.AWK [-v debug={0|1}] |
# syntax: GAWK -f WATER_COLLECTED_BETWEEN_TOWERS.AWK [-v debug={0|1}] |
||
BEGIN { |
BEGIN { |
||
Line 728: | Line 851: | ||
function max(x,y) { return((x > y) ? x : y) } |
function max(x,y) { return((x > y) ? x : y) } |
||
function min(x,y) { return((x < y) ? x : y) } |
function min(x,y) { return((x < y) ? x : y) } |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 741: | Line 864: | ||
=={{header|BASIC}}== |
=={{header|BASIC}}== |
||
==={{header|FreeBASIC}}=== |
|||
<lang BASIC>10 DEFINT A-Z: DIM T(20): K=0 |
|||
Uses Nigel Galloway's very elegant idea, expressed verbosely so you can really see what's going on. |
|||
<syntaxhighlight lang="freebasic">type tower |
|||
hght as uinteger |
|||
posi as uinteger |
|||
end type |
|||
sub shellsort( a() as tower ) |
|||
'quick and dirty shellsort, not the focus of this exercise |
|||
dim as uinteger gap = ubound(a), i, j, n=ubound(a) |
|||
dim as tower temp |
|||
do |
|||
gap = int(gap / 2.2) |
|||
if gap=0 then gap=1 |
|||
for i=gap to n |
|||
temp = a(i) |
|||
j=i |
|||
while j>=gap andalso a(j-gap).hght < temp.hght |
|||
a(j) = a(j - gap) |
|||
j -= gap |
|||
wend |
|||
a(j) = temp |
|||
next i |
|||
loop until gap = 1 |
|||
end sub |
|||
'heights of towers in each city prefixed by the number of towers |
|||
data 5, 1, 5, 3, 7, 2 |
|||
data 10, 5, 3, 7, 2, 6, 4, 5, 9, 1, 2 |
|||
data 16, 2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1 |
|||
data 4, 5, 5, 5, 5 |
|||
data 4, 5, 6, 7, 8 |
|||
data 4, 8, 7, 7, 6 |
|||
data 5, 6, 7, 10, 7, 6 |
|||
dim as uinteger i, n, j, first, last, water |
|||
dim as tower manhattan(0 to 1) |
|||
for i = 1 to 7 |
|||
read n |
|||
redim manhattan( 0 to n-1 ) |
|||
for j = 0 to n-1 |
|||
read manhattan(j).hght |
|||
manhattan(j).posi = j |
|||
next j |
|||
shellsort( manhattan() ) |
|||
if manhattan(0).posi < manhattan(1).posi then |
|||
first = manhattan(0).posi |
|||
last = manhattan(1).posi |
|||
else |
|||
first = manhattan(1).posi |
|||
last = manhattan(0).posi |
|||
end if |
|||
water = manhattan(1).hght * (last-first-1) |
|||
for j = 2 to n-1 |
|||
if first<manhattan(j).posi and manhattan(j).posi<last then water -= manhattan(j).hght |
|||
if manhattan(j).posi < first then |
|||
water += manhattan(j).hght * (first-manhattan(j).posi-1) |
|||
first = manhattan(j).posi |
|||
end if |
|||
if manhattan(j).posi > last then |
|||
water += manhattan(j).hght * (manhattan(j).posi-last-1) |
|||
last = manhattan(j).posi |
|||
end if |
|||
next j |
|||
print using "City configuration ## collected #### units of water."; i; water |
|||
next i</syntaxhighlight> |
|||
{{out}} |
|||
<pre>City configuration 1 collected 2 units of water. |
|||
City configuration 2 collected 14 units of water. |
|||
City configuration 3 collected 35 units of water. |
|||
City configuration 4 collected 0 units of water. |
|||
City configuration 5 collected 0 units of water. |
|||
City configuration 6 collected 0 units of water. |
|||
City configuration 7 collected 0 units of water.</pre> |
|||
==={{header|GW-BASIC}}=== |
|||
{{works with|BASICA}} |
|||
<syntaxhighlight lang="gwbasic">10 DEFINT A-Z: DIM T(20): K=0 |
|||
20 K=K+1: READ N: IF N=0 THEN END |
20 K=K+1: READ N: IF N=0 THEN END |
||
30 FOR I=0 TO N-1: READ T(I): NEXT |
30 FOR I=0 TO N-1: READ T(I): NEXT |
||
Line 760: | Line 960: | ||
180 DATA 4, 8,7,7,6 |
180 DATA 4, 8,7,7,6 |
||
190 DATA 5, 6,7,10,7,6 |
190 DATA 5, 6,7,10,7,6 |
||
200 DATA 0</ |
200 DATA 0</syntaxhighlight> |
||
{{out}} |
|||
<pre>Block 1 holds 2 water units. |
|||
Block 2 holds 14 water units. |
|||
Block 3 holds 35 water units. |
|||
Block 4 holds 0 water units. |
|||
Block 5 holds 0 water units. |
|||
Block 6 holds 0 water units. |
|||
Block 7 holds 0 water units.</pre> |
|||
==={{header|Nascom BASIC}}=== |
|||
{{trans|FreeBasic}} |
|||
{{works with|Nascom ROM BASIC|4.7}} |
|||
<syntaxhighlight lang="basic"> |
|||
10 REM Water collected between towers |
|||
20 MXN=19 |
|||
30 REM Heights of towers in each city |
|||
40 REM prefixed by the number of towers |
|||
50 DATA 5,1,5,3,7,2 |
|||
60 DATA 10,5,3,7,2,6,4,5,9,1,2 |
|||
70 DATA 16,2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1 |
|||
80 DATA 4,5,5,5,5 |
|||
90 DATA 4,5,6,7,8 |
|||
100 DATA 4,8,7,7,6 |
|||
110 DATA 5,6,7,10,7,6 |
|||
120 DIM A(MXN,1) |
|||
130 FOR I=1 TO 7 |
|||
140 READ N |
|||
150 FOR J=0 TO N-1 |
|||
160 READ A(J,0) |
|||
170 A(J,1)=J |
|||
180 NEXT J |
|||
190 GOSUB 390 |
|||
200 IF A(0,1)>=A(1,1) THEN 220 |
|||
210 FRST=A(0,1):LST=A(1,1):GOTO 230 |
|||
220 FRST=A(1,1):LST=A(0,1) |
|||
230 WTR=A(1,0)*(LST-FRST-1) |
|||
240 FOR J=2 TO N-1 |
|||
250 IF FRST>=A(J,1) OR A(J,1)>=LST THEN 270 |
|||
260 WTR=WTR-A(J,0) |
|||
270 IF A(J,1)>=FRST THEN 300 |
|||
280 WTR=WTR+A(J,0)*(FRST-A(J,1)-1) |
|||
290 FRST=A(J,1) |
|||
300 IF A(J,1)<=LST THEN 330 |
|||
310 WTR=WTR+A(J,0)*(A(J,1)-LST-1) |
|||
320 LST=A(J,1) |
|||
330 NEXT J |
|||
340 PRINT "Bar chart";I;"collected"; |
|||
350 PRINT WTR;"units of water." |
|||
360 NEXT I |
|||
370 END |
|||
380 REM ** ShellSort |
|||
390 GAP=N-1 |
|||
400 GAP=INT(GAP/2.2) |
|||
410 IF GAP=0 THEN GAP=1 |
|||
420 FOR K=GAP TO N-1 |
|||
430 TH=A(K,0):TP=A(K,1) |
|||
440 L=K |
|||
450 IF L<GAP THEN 500 |
|||
460 IF A(L-GAP,0)>=TH THEN 500 |
|||
470 A(L,0)=A(L-GAP,0):A(L,1)=A(L-GAP,1) |
|||
480 L=L-GAP |
|||
490 GOTO 450 |
|||
500 A(L,0)=TH:A(L,1)=TP |
|||
510 NEXT K |
|||
520 IF GAP<>1 THEN 400 |
|||
530 RETURN |
|||
</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
|||
Bar chart 1 collected 2 units of water. |
|||
Bar chart 2 collected 14 units of water. |
|||
Bar chart 3 collected 35 units of water. |
|||
Bar chart 4 collected 0 units of water. |
|||
Bar chart 5 collected 0 units of water. |
|||
Bar chart 6 collected 0 units of water. |
|||
Bar chart 7 collected 0 units of water. |
|||
</pre> |
|||
==={{header|QuickBASIC}}=== |
|||
{{trans|FreeBasic}} |
|||
<syntaxhighlight lang="qbasic"> |
|||
' Water collected between towers |
|||
DECLARE SUB ShellSort (A() AS ANY) |
|||
TYPE TTowerRec |
|||
Hght AS INTEGER |
|||
Posi AS INTEGER |
|||
END TYPE |
|||
'heights of towers in each city prefixed by the number of towers |
|||
DATA 5, 1, 5, 3, 7, 2 |
|||
DATA 10, 5, 3, 7, 2, 6, 4, 5, 9, 1, 2 |
|||
DATA 16, 2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1 |
|||
DATA 4, 5, 5, 5, 5 |
|||
DATA 4, 5, 6, 7, 8 |
|||
DATA 4, 8, 7, 7, 6 |
|||
DATA 5, 6, 7, 10, 7, 6 |
|||
REM $DYNAMIC |
|||
DIM Manhattan(0 TO 1) AS TTowerRec |
|||
FOR I% = 1 TO 7 |
|||
READ N% |
|||
ERASE Manhattan |
|||
REDIM Manhattan(0 TO N% - 1) AS TTowerRec |
|||
FOR J% = 0 TO N% - 1 |
|||
READ Manhattan(J%).Hght |
|||
Manhattan(J%).Posi = J% |
|||
NEXT J% |
|||
ShellSort Manhattan() |
|||
IF Manhattan(0).Posi < Manhattan(1).Posi THEN |
|||
First% = Manhattan(0).Posi |
|||
Last% = Manhattan(1).Posi |
|||
ELSE |
|||
First% = Manhattan(1).Posi |
|||
Last% = Manhattan(0).Posi |
|||
END IF |
|||
Water% = Manhattan(1).Hght * (Last% - First% - 1) |
|||
FOR J% = 2 TO N% - 1 |
|||
IF First% < Manhattan(J%).Posi AND Manhattan(J%).Posi < Last% THEN Water% = Water% - Manhattan(J%).Hght |
|||
IF Manhattan(J%).Posi < First% THEN |
|||
Water% = Water% + Manhattan(J%).Hght * (First% - Manhattan(J%).Posi - 1) |
|||
First% = Manhattan(J%).Posi |
|||
END IF |
|||
IF Manhattan(J%).Posi > Last% THEN |
|||
Water% = Water% + Manhattan(J%).Hght * (Manhattan(J%).Posi - Last% - 1) |
|||
Last% = Manhattan(J%).Posi |
|||
END IF |
|||
NEXT J% |
|||
PRINT USING "City configuration ## collected #### units of water."; I%; Water% |
|||
NEXT I% |
|||
END |
|||
REM $STATIC |
|||
SUB ShellSort (A() AS TTowerRec) |
|||
'quick and dirty shellsort, not the focus of this exercise |
|||
Gap% = UBOUND(A): N% = UBOUND(A) |
|||
DIM Temp AS TTowerRec |
|||
DO |
|||
Gap% = INT(Gap% / 2.2) |
|||
IF Gap% = 0 THEN Gap% = 1 |
|||
FOR I% = Gap% TO N% |
|||
Temp = A(I%) |
|||
J% = I% |
|||
' Simulated WHILE J% >= Gap% ANDALSO A(J% - Gap%).Hght < Temp.Hght |
|||
DO |
|||
IF J% < Gap% THEN EXIT DO |
|||
IF A(J% - Gap%).Hght >= Temp.Hght THEN EXIT DO |
|||
A(J%) = A(J% - Gap%) |
|||
J% = J% - Gap% |
|||
LOOP |
|||
A(J%) = Temp |
|||
NEXT I% |
|||
LOOP UNTIL Gap% = 1 |
|||
END SUB |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
City configuration 1 collected 2 units of water. |
|||
City configuration 2 collected 14 units of water. |
|||
City configuration 3 collected 35 units of water. |
|||
City configuration 4 collected 0 units of water. |
|||
City configuration 5 collected 0 units of water. |
|||
City configuration 6 collected 0 units of water. |
|||
City configuration 7 collected 0 units of water. |
|||
</pre> |
|||
==={{header|uBasic/4tH}}=== |
|||
{{Trans|GW-BASIC}} |
|||
<syntaxhighlight lang="basic">Dim @t(20) |
|||
k = FUNC (_getWater (1, 5, 3, 7, 2, 1)) |
|||
k = FUNC (_getWater (5, 3, 7, 2, 6, 4, 5, 9, 1, 2, k)) |
|||
k = FUNC (_getWater (2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1, k)) |
|||
k = FUNC (_getWater (5, 5, 5, 5, k)) |
|||
k = FUNC (_getWater (5, 6, 7, 8, k)) |
|||
k = FUNC (_getWater (8, 7, 7, 6, k)) |
|||
k = FUNC (_getWater (6, 7, 10, 7, 6, k)) |
|||
End |
|||
_getWater |
|||
Param (1) |
|||
Local (2) |
|||
w = 0 |
|||
c@ = Used() |
|||
For b@ = c@ - 1 To 0 Step -1 |
|||
@t(b@) = Pop() |
|||
Next |
|||
Do While FUNC(_netWater (c@)) > 1 : Loop |
|||
Print "Block ";a@;" holds ";w;" water units." |
|||
Return (a@ + 1) |
|||
_netWater |
|||
Param (1) |
|||
Local (3) |
|||
For d@ = a@-1 To 0 Step -1 |
|||
If @t(d@) Then |
|||
If d@ = 0 Then Unloop : Return (0) : fi |
|||
Else |
|||
Continue |
|||
EndIf |
|||
b@ = 0 |
|||
For c@ = 0 To d@ |
|||
If @t(c@) > 0 Then |
|||
@t(c@) = @t(c@) - 1 |
|||
b@ = b@ + 1 |
|||
Else |
|||
If b@ > 0 Then w = w + 1 : fi |
|||
EndIf |
|||
Next |
|||
Unloop : Return (b@) |
|||
Next |
|||
Return (0)</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>Block 1 holds 2 water units. |
<pre>Block 1 holds 2 water units. |
||
Block 2 holds 14 water units. |
Block 2 holds 14 water units. |
||
Line 770: | Line 1,188: | ||
Block 5 holds 0 water units. |
Block 5 holds 0 water units. |
||
Block 6 holds 0 water units. |
Block 6 holds 0 water units. |
||
Block 7 holds 0 water units. |
Block 7 holds 0 water units. |
||
0 OK, 0:409</pre> |
|||
==={{header|Visual Basic .NET}}=== |
|||
====Version 1==== |
|||
'''Method:''' Instead of "scanning" adjoining towers for each column, this routine converts the tower data into a string representation with building blocks, empty spaces, and potential water retention sites. The potential water retention sites are then "eroded" away where they are found to be unsupported. This is accomplished with the '''.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 |
|||
[[{{FULLPAGENAME}}#version_3|REXX 9.3]] output, but used the double-wide columns, as pictured in the task definition area. |
|||
<syntaxhighlight lang="vbnet">' Convert tower block data into a string representation, then manipulate that. |
|||
Module Module1 |
|||
Sub Main(Args() As String) |
|||
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 = vbLf, ' Line feed to separate floors in a block of towers. |
|||
tb = "██", wr = "≈≈", mt = " " ' Tower Block, Water Retained, eMpTy space. |
|||
For i As Integer = 0 To wta.Length - 1 |
|||
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 wta(i).Length - 1 |
|||
If wta(i)(j) > 0 Then ' Tower block detected, add block to floor, |
|||
floor &= tb : wta(i)(j) -= 1 : bpf += 1 ' reduce tower by one. |
|||
Else ' Empty space detected, fill when not first or last column. |
|||
floor &= If(j > 0 AndAlso j < wta(i).Length - 1, wr, mt) |
|||
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. |
|||
' Erode potential water retention cells from left and right. |
|||
While blk.Contains(mt & wr) : blk = blk.Replace(mt & wr, mt & mt) : End While |
|||
While blk.Contains(wr & mt) : blk = blk.Replace(wr & mt, mt & mt) : End While |
|||
' Optionaly show towers w/ water marks. |
|||
If shoTow Then Console.Write("{0}{1}", lf, blk) |
|||
' Subtract the amount of non-water mark characters from the total char amount. |
|||
Console.Write("Block {0} retains {1,2} water units.{2}", i + 1, |
|||
(blk.Length - blk.Replace(wr, "").Length) \ 2, lf) |
|||
Next |
|||
End Sub |
|||
End Module</syntaxhighlight> |
|||
{{out}}<syntaxhighlight lang="text">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.</syntaxhighlight> |
|||
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. |
|||
<syntaxhighlight lang="text"> ██ |
|||
██ |
|||
██≈≈██ |
|||
██≈≈██ |
|||
██████ |
|||
████████ |
|||
██████████ |
|||
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.</syntaxhighlight> |
|||
====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. |
|||
<syntaxhighlight lang="vbnet">Module Module1 |
|||
''' <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 |
|||
End Module</syntaxhighlight> |
|||
Regular version 2 output: |
|||
<syntaxhighlight lang="text"> 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.</syntaxhighlight> |
|||
Sample of version 2 verbose output: |
|||
<syntaxhighlight lang="text"> ██ |
|||
██≈≈≈≈≈≈≈≈≈≈≈≈≈≈██ |
|||
██≈≈≈≈≈≈██≈≈≈≈≈≈≈≈≈≈≈≈≈≈██ |
|||
██≈≈██≈≈██≈≈≈≈≈≈≈≈██≈≈████ |
|||
██≈≈██≈≈██≈≈██≈≈≈≈██≈≈██████ |
|||
██████≈≈██≈≈██≈≈≈≈██████████ |
|||
████████████≈≈████████████████ |
|||
████████████████████████████████ Block 3 holds 35 water units. |
|||
████████ |
|||
████████ |
|||
████████ |
|||
████████ |
|||
████████ Block 4 does not hold any water units.</syntaxhighlight> |
|||
==={{header|Yabasic}}=== |
|||
{{trans|AWK}} |
|||
<syntaxhighlight lang="yabasic">data 7 |
|||
data "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" |
|||
data "5,5,5,5", "5,6,7,8", "8,7,7,6", "6,7,10,7,6" |
|||
read n |
|||
for i = 1 to n |
|||
read n$ |
|||
wcbt(n$) |
|||
next i |
|||
sub wcbt(s$) |
|||
local tower$(1), hr(1), hl(1), n, i, ans, k |
|||
n = token(s$, tower$(), ",") |
|||
redim hr(n) |
|||
redim hl(n) |
|||
for i = n to 1 step -1 |
|||
if i < n then |
|||
k = hr(i + 1) |
|||
else |
|||
k = 0 |
|||
end if |
|||
hr(i) = max(val(tower$(i)), k) |
|||
next i |
|||
for i = 1 to n |
|||
if i then |
|||
k = hl(i - 1) |
|||
else |
|||
k = 0 |
|||
end if |
|||
hl(i) = max(val(tower$(i)), k) |
|||
ans = ans + min(hl(i), hr(i)) - val(tower$(i)) |
|||
next i |
|||
print ans," ",n$ |
|||
end sub</syntaxhighlight> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
Takes the integers as input from command line, prints out usage on incorrect invocation. |
Takes the integers as input from command line, prints out usage on incorrect invocation. |
||
<syntaxhighlight lang="c"> |
|||
<lang C> |
|||
#include<stdlib.h> |
#include<stdlib.h> |
||
#include<stdio.h> |
#include<stdio.h> |
||
Line 846: | Line 1,552: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output : |
Output : |
||
<pre> |
<pre> |
||
Line 866: | Line 1,572: | ||
===Version 1=== |
===Version 1=== |
||
Translation from [[{{FULLPAGENAME}}#Visual_Basic_.NET|Visual Basic .NET]]. See that version 1 entry for code comment details and more sample output. |
Translation from [[{{FULLPAGENAME}}#Visual_Basic_.NET|Visual Basic .NET]]. See that version 1 entry for code comment details and more sample output. |
||
< |
<syntaxhighlight lang="csharp">class Program |
||
{ |
{ |
||
static void Main(string[] args) |
static void Main(string[] args) |
||
Line 895: | Line 1,601: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight>{{out}}<syntaxhighlight lang="text">Block 1 retains 2 water units. |
||
Block 2 retains 14 water units. |
Block 2 retains 14 water units. |
||
Block 3 retains 35 water units. |
Block 3 retains 35 water units. |
||
Line 901: | Line 1,607: | ||
Block 5 retains 0 water units. |
Block 5 retains 0 water units. |
||
Block 6 retains 0 water units. |
Block 6 retains 0 water units. |
||
Block 7 retains 0 water units.</ |
Block 7 retains 0 water units.</syntaxhighlight> |
||
===Version 2=== |
===Version 2=== |
||
Conventional "scanning" algorithm, translated from [[{{FULLPAGENAME}}#Version_2_2|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. |
Conventional "scanning" algorithm, translated from [[{{FULLPAGENAME}}#Version_2_2|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. |
||
< |
<syntaxhighlight lang="csharp">class Program |
||
{ |
{ |
||
// Variable names key: |
// Variable names key: |
||
Line 940: | Line 1,646: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
'''Output:''' |
'''Output:''' |
||
<pre>Block 1 holds 2 water units. |
<pre>Block 1 holds 2 water units. |
||
Line 951: | Line 1,657: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp"> |
||
#include <iostream> |
#include <iostream> |
||
#include <vector> |
#include <vector> |
||
Line 1,015: | Line 1,721: | ||
std::cin.get(); |
std::cin.get(); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,029: | Line 1,735: | ||
Similar two passes algorithm as many solutions here. First traverse left to right to find the highest tower on the left of each position, inclusive of the tower at the current position, than do the same to find the highest tower to the right of each position. Finally, compute the total water units held at any position as the difference of those two heights. |
Similar two passes algorithm as many solutions here. First traverse left to right to find the highest tower on the left of each position, inclusive of the tower at the current position, than do the same to find the highest tower to the right of each position. Finally, compute the total water units held at any position as the difference of those two heights. |
||
< |
<syntaxhighlight lang="clojure"> |
||
(defn trapped-water [towers] |
(defn trapped-water [towers] |
||
(let [maxes #(reductions max %) ; the seq of increasing max values found in the input seq |
(let [maxes #(reductions max %) ; the seq of increasing max values found in the input seq |
||
Line 1,036: | Line 1,742: | ||
mins (map min maxl maxr)] ; minimum highest surrounding tower per position |
mins (map min maxl maxr)] ; minimum highest surrounding tower per position |
||
(reduce + (map - mins towers)))) ; sum up the trapped water per position |
(reduce + (map - mins towers)))) ; sum up the trapped water per position |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="clojure"> |
||
;; in the following, # is a tower block and ~ is trapped water: |
;; in the following, # is a tower block and ~ is trapped water: |
||
;; |
;; |
||
Line 1,054: | Line 1,760: | ||
;; 5 3 7 2 6 4 5 9 1 2 |
;; 5 3 7 2 6 4 5 9 1 2 |
||
(trapped-water [5 3 7 2 6 4 5 9 1 2]) ;; 14 |
(trapped-water [5 3 7 2 6 4 5 9 1 2]) ;; 14 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|CLU}}== |
=={{header|CLU}}== |
||
< |
<syntaxhighlight lang="clu">max = proc [T: type] (a,b: T) returns (T) |
||
where T has lt: proctype (T,T) returns (bool) |
where T has lt: proctype (T,T) returns (bool) |
||
if a<b then return(b) |
if a<b then return(b) |
||
Line 1,107: | Line 1,813: | ||
stream$puts(po, int$unparse(water(test)) || " ") |
stream$puts(po, int$unparse(water(test)) || " ") |
||
end |
end |
||
end start_up</ |
end start_up</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>2 14 35 0 0 0 0</pre> |
<pre>2 14 35 0 0 0 0</pre> |
||
=={{header|Cowgol}}== |
=={{header|Cowgol}}== |
||
< |
<syntaxhighlight lang="cowgol">include "cowgol.coh"; |
||
include "argv.coh"; |
include "argv.coh"; |
||
Line 1,166: | Line 1,872: | ||
print_i8(water(&towers[0], count as intptr)); |
print_i8(water(&towers[0], count as intptr)); |
||
print_nl();</ |
print_nl();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,187: | Line 1,893: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{Trans|C#}} |
{{Trans|C#}} |
||
< |
<syntaxhighlight lang="d">import std.stdio; |
||
void main() { |
void main() { |
||
Line 1,235: | Line 1,941: | ||
writeln(" water units."); |
writeln(" water units."); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,245: | Line 1,951: | ||
Block 6 does not hold any water units. |
Block 6 does not hold any water units. |
||
Block 7 does not hold any water units.</pre> |
Block 7 does not hold any water units.</pre> |
||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
The program builds a matrix of the towers and scans each line looking for pairs of towers that trap water. |
|||
<syntaxhighlight lang="Delphi"> |
|||
var Towers1: array [0..4] of integer = (1, 5, 3, 7, 2); |
|||
var Towers2: array [0..9] of integer = (5, 3, 7, 2, 6, 4, 5, 9, 1, 2); |
|||
var Towers3: array [0..15] of integer = (2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1); |
|||
var Towers4: array [0..3] of integer = (5, 5, 5, 5); |
|||
var Towers5: array [0..3] of integer = (5, 6, 7, 8); |
|||
var Towers6: array [0..3] of integer = (8, 7, 7, 6); |
|||
var Towers7: array [0..4] of integer = (6, 7, 10, 7, 6); |
|||
type TMatrix = array of array of boolean; |
|||
function ArrayToMatrix(Towers: array of integer): TMatrix; |
|||
{Convert Tower Array to Matrix for analysis} |
|||
var Max,I,X,Y: integer; |
|||
begin |
|||
Max:=0; |
|||
for I:=0 to High(Towers) do if Towers[I]>=Max then Max:=Towers[I]; |
|||
SetLength(Result,Length(Towers),Max); |
|||
for Y:=0 to High(Result[0]) do |
|||
for X:=0 to High(Result) do Result[X,Y]:=Towers[X]>(Max-Y); |
|||
end; |
|||
procedure DisplayMatrix(Memo: TMemo; Matrix: TMatrix); |
|||
{Display a matrix} |
|||
var X,Y: integer; |
|||
var S: string; |
|||
begin |
|||
for Y:=0 to High(Matrix[0]) do |
|||
begin |
|||
S:='['; |
|||
for X:=0 to High(Matrix) do |
|||
begin |
|||
if Matrix[X,Y] then S:=S+'#' |
|||
else S:=S+' '; |
|||
end; |
|||
S:=S+']'; |
|||
Memo.Lines.Add(S); |
|||
end; |
|||
end; |
|||
function GetWaterStorage(Matrix: TMatrix): integer; |
|||
{Analyze matrix to get water storage amount} |
|||
var X,Y,Cnt: integer; |
|||
var Inside: boolean; |
|||
begin |
|||
Result:=0; |
|||
{Scan each row of matrix to see if it is storing water} |
|||
for Y:=0 to High(Matrix[0]) do |
|||
begin |
|||
Inside:=False; |
|||
Cnt:=0; |
|||
for X:=0 to High(Matrix) do |
|||
begin |
|||
{Test if this is a tower} |
|||
if Matrix[X,Y] then |
|||
begin |
|||
{if so, we may be inside trough} |
|||
Inside:=True; |
|||
{If Cnt>0 there was a previous tower} |
|||
{And we've impounded water } |
|||
Result:=Result+Cnt; |
|||
{Start new count with new tower} |
|||
Cnt:=0; |
|||
end |
|||
else if Inside then Inc(Cnt); {Count potential impounded water} |
|||
end; |
|||
end; |
|||
end; |
|||
procedure ShowWaterLevels(Memo: TMemo; Towers: array of integer); |
|||
{Analyze the water storage of towers and display result} |
|||
var Water: integer; |
|||
var Matrix: TMatrix; |
|||
begin |
|||
Matrix:=ArrayToMatrix(Towers); |
|||
DisplayMatrix(Memo,Matrix); |
|||
Water:=GetWaterStorage(Matrix); |
|||
Memo.Lines.Add('Storage: '+IntToStr(Water)+CRLF); |
|||
end; |
|||
procedure WaterLevel(Memo: TMemo); |
|||
begin |
|||
ShowWaterLevels(Memo,Towers1); |
|||
ShowWaterLevels(Memo,Towers2); |
|||
ShowWaterLevels(Memo,Towers3); |
|||
ShowWaterLevels(Memo,Towers4); |
|||
ShowWaterLevels(Memo,Towers5); |
|||
ShowWaterLevels(Memo,Towers6); |
|||
ShowWaterLevels(Memo,Towers7); |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[ ] |
|||
[ # ] |
|||
[ # ] |
|||
[ # # ] |
|||
[ # # ] |
|||
[ ### ] |
|||
[ ####] |
|||
Storage: 2 |
|||
[ ] |
|||
[ # ] |
|||
[ # ] |
|||
[ # # ] |
|||
[ # # # ] |
|||
[# # # ## ] |
|||
[# # #### ] |
|||
[### #### ] |
|||
[######## #] |
|||
Storage: 14 |
|||
[ ] |
|||
[ # ] |
|||
[ # # ] |
|||
[ # # # ] |
|||
[ # # # # ## ] |
|||
[ # # # # # ### ] |
|||
[ ### # # ##### ] |
|||
[###### ######## ] |
|||
Storage: 35 |
|||
[ ] |
|||
[####] |
|||
[####] |
|||
[####] |
|||
[####] |
|||
Storage: 0 |
|||
[ ] |
|||
[ #] |
|||
[ ##] |
|||
[ ###] |
|||
[####] |
|||
[####] |
|||
[####] |
|||
[####] |
|||
Storage: 0 |
|||
[ ] |
|||
[# ] |
|||
[### ] |
|||
[####] |
|||
[####] |
|||
[####] |
|||
[####] |
|||
[####] |
|||
Storage: 0 |
|||
[ ] |
|||
[ # ] |
|||
[ # ] |
|||
[ # ] |
|||
[ ### ] |
|||
[#####] |
|||
[#####] |
|||
[#####] |
|||
[#####] |
|||
[#####] |
|||
Storage: 0 |
|||
Elapsed Time: 171.444 ms. |
|||
</pre> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight lang="easylang"> |
|||
proc water h[] . . |
|||
n = len h[] |
|||
len left[] n |
|||
len right[] n |
|||
for i = 1 to n |
|||
max = higher max h[i] |
|||
left[i] = max |
|||
. |
|||
max = 0 |
|||
for i = n downto 1 |
|||
max = higher max h[i] |
|||
right[i] = max |
|||
. |
|||
for i = 1 to n |
|||
sum += (lower left[i] right[i]) - h[i] |
|||
. |
|||
print sum |
|||
. |
|||
repeat |
|||
s$ = input |
|||
until s$ = "" |
|||
water number strsplit s$ " " |
|||
. |
|||
# |
|||
input_data |
|||
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 |
|||
</syntaxhighlight> |
|||
=={{header|Erlang}}== |
=={{header|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. |
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. |
||
< |
<syntaxhighlight lang="erlang"> |
||
-module(watertowers). |
-module(watertowers). |
||
-export([towers/1, demo/0]). |
-export([towers/1, demo/0]). |
||
Line 1,271: | Line 2,197: | ||
[io:format("~p -> ~p~n", [Case, towers(Case)]) || Case <- Cases], |
[io:format("~p -> ~p~n", [Case, towers(Case)]) || Case <- Cases], |
||
ok. |
ok. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,288: | Line 2,214: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|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. |
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. |
||
< |
<syntaxhighlight lang="fsharp"> |
||
(* |
(* |
||
A solution I'd show to Euclid !!!!. |
A solution I'd show to Euclid !!!!. |
||
Line 1,302: | Line 2,228: | ||
| _ -> l |
| _ -> l |
||
fn (min n i) (max n i) g (e*(abs(n-i)-1)) |
fn (min n i) (max n i) g (e*(abs(n-i)-1)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,316: | Line 2,242: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: formatting kernel math.statistics math.vectors sequences ; |
||
: area ( seq -- n ) |
: area ( seq -- n ) |
||
Line 1,329: | Line 2,255: | ||
{ 8 7 7 6 } |
{ 8 7 7 6 } |
||
{ 6 7 10 7 6 } |
{ 6 7 10 7 6 } |
||
} [ dup area "%[%d, %] -> %d\n" printf ] each</ |
} [ dup area "%[%d, %] -> %d\n" printf ] each</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,340: | Line 2,266: | ||
{ 6, 7, 10, 7, 6 } -> 0 |
{ 6, 7, 10, 7, 6 } -> 0 |
||
</pre> |
</pre> |
||
=={{header|FreeBASIC}}== |
|||
Uses Nigel Galloway's very elegant idea, expressed verbosely so you can really see what's going on. |
|||
<lang freebasic>type tower |
|||
hght as uinteger |
|||
posi as uinteger |
|||
end type |
|||
sub shellsort( a() as tower ) |
|||
'quick and dirty shellsort, not the focus of this exercise |
|||
dim as uinteger gap = ubound(a), i, j, n=ubound(a) |
|||
dim as tower temp |
|||
do |
|||
gap = int(gap / 2.2) |
|||
if gap=0 then gap=1 |
|||
for i=gap to n |
|||
temp = a(i) |
|||
j=i |
|||
while j>=gap andalso a(j-gap).hght < temp.hght |
|||
a(j) = a(j - gap) |
|||
j -= gap |
|||
wend |
|||
a(j) = temp |
|||
next i |
|||
loop until gap = 1 |
|||
end sub |
|||
'heights of towers in each city prefixed by the number of towers |
|||
data 5, 1, 5, 3, 7, 2 |
|||
data 10, 5, 3, 7, 2, 6, 4, 5, 9, 1, 2 |
|||
data 16, 2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1 |
|||
data 4, 5, 5, 5, 5 |
|||
data 4, 5, 6, 7, 8 |
|||
data 4, 8, 7, 7, 6 |
|||
data 5, 6, 7, 10, 7, 6 |
|||
dim as uinteger i, n, j, first, last, water |
|||
dim as tower manhattan(0 to 1) |
|||
for i = 1 to 7 |
|||
read n |
|||
redim manhattan( 0 to n-1 ) |
|||
for j = 0 to n-1 |
|||
read manhattan(j).hght |
|||
manhattan(j).posi = j |
|||
next j |
|||
shellsort( manhattan() ) |
|||
if manhattan(0).posi < manhattan(1).posi then |
|||
first = manhattan(0).posi |
|||
last = manhattan(1).posi |
|||
else |
|||
first = manhattan(1).posi |
|||
last = manhattan(0).posi |
|||
end if |
|||
water = manhattan(1).hght * (last-first-1) |
|||
for j = 2 to n-1 |
|||
if first<manhattan(j).posi and manhattan(j).posi<last then water -= manhattan(j).hght |
|||
if manhattan(j).posi < first then |
|||
water += manhattan(j).hght * (first-manhattan(j).posi-1) |
|||
first = manhattan(j).posi |
|||
end if |
|||
if manhattan(j).posi > last then |
|||
water += manhattan(j).hght * (manhattan(j).posi-last-1) |
|||
last = manhattan(j).posi |
|||
end if |
|||
next j |
|||
print using "City configuration ## collected #### units of water."; i; water |
|||
next i</lang> |
|||
{{out}} |
|||
<pre>City configuration 1 collected 2 units of water. |
|||
City configuration 2 collected 14 units of water. |
|||
City configuration 3 collected 35 units of water. |
|||
City configuration 4 collected 0 units of water. |
|||
City configuration 5 collected 0 units of water. |
|||
City configuration 6 collected 0 units of water. |
|||
City configuration 7 collected 0 units of water.</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
<syntaxhighlight lang="go"> |
|||
<lang go> |
|||
package main |
package main |
||
Line 1,490: | Line 2,341: | ||
fmt.Println(waterCollected([]int{8, 7, 7, 6})) |
fmt.Println(waterCollected([]int{8, 7, 7, 6})) |
||
fmt.Println(waterCollected([]int{6, 7, 10, 7, 6})) |
fmt.Println(waterCollected([]int{6, 7, 10, 7, 6})) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,505: | Line 2,356: | ||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
<syntaxhighlight lang="groovy"> |
|||
<lang Groovy> |
|||
Integer waterBetweenTowers(List<Integer> towers) { |
Integer waterBetweenTowers(List<Integer> towers) { |
||
// iterate over the vertical axis. There the amount of water each row can hold is |
// iterate over the vertical axis. There the amount of water each row can hold is |
||
Line 1,529: | Line 2,380: | ||
println "$it => total water: ${waterBetweenTowers it}" |
println "$it => total water: ${waterBetweenTowers it}" |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,546: | Line 2,397: | ||
Following the approach of slightly modified [http://stackoverflow.com/users/1416525/cdk cdk]'s Haskell solution at [http://stackoverflow.com/questions/24414700/amazon-water-collected-between-towers/ Stack Overflow]. As recommended in [http://h2.jaguarpaw.co.uk/posts/data-structures-matter/ Programming as if the Correct Data Structure (and Performance) Mattered] it uses [http://hackage.haskell.org/package/vector-0.12.0.1/docs/Data-Vector-Unboxed.html Vector] instead of Array: |
Following the approach of slightly modified [http://stackoverflow.com/users/1416525/cdk cdk]'s Haskell solution at [http://stackoverflow.com/questions/24414700/amazon-water-collected-between-towers/ Stack Overflow]. As recommended in [http://h2.jaguarpaw.co.uk/posts/data-structures-matter/ Programming as if the Correct Data Structure (and Performance) Mattered] it uses [http://hackage.haskell.org/package/vector-0.12.0.1/docs/Data-Vector-Unboxed.html Vector] instead of Array: |
||
< |
<syntaxhighlight lang="haskell">import Data.Vector.Unboxed (Vector) |
||
import qualified Data.Vector.Unboxed as V |
import qualified Data.Vector.Unboxed as V |
||
Line 1,569: | Line 2,420: | ||
, [8, 7, 7, 6] |
, [8, 7, 7, 6] |
||
, [6, 7, 10, 7, 6] |
, [6, 7, 10, 7, 6] |
||
]</ |
]</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>2 |
<pre>2 |
||
Line 1,582: | Line 2,433: | ||
Or, using Data.List for simplicity - no need to prioritize performance here - and adding diagrams: |
Or, using Data.List for simplicity - no need to prioritize performance here - and adding diagrams: |
||
< |
<syntaxhighlight lang="haskell">import Data.List (replicate, transpose) |
||
-------------- WATER COLLECTED BETWEEN TOWERS ------------ |
-------------- WATER COLLECTED BETWEEN TOWERS ------------ |
||
Line 1,630: | Line 2,481: | ||
showLegend = |
showLegend = |
||
((<>) . show . fmap fst) |
((<>) . show . fmap fst) |
||
<*> ((" -> " <>) . show . foldr ((+) . snd) 0)</ |
<*> ((" -> " <>) . show . foldr ((+) . snd) 0)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 1,713: | Line 2,564: | ||
'''Solution:''' |
'''Solution:''' |
||
< |
<syntaxhighlight lang="j">collectLevels =: >./\ <. >./\. NB. collect levels after filling |
||
waterLevels=: collectLevels - ] NB. water levels for each tower |
waterLevels=: collectLevels - ] NB. water levels for each tower |
||
collectedWater=: +/@waterLevels NB. sum the units of water collected |
collectedWater=: +/@waterLevels NB. sum the units of water collected |
||
printTowers =: ' ' , [: |.@|: '#~' #~ ] ,. waterLevels NB. print a nice graph of towers and water</ |
printTowers =: ' ' , [: |.@|: '#~' #~ ] ,. waterLevels NB. print a nice graph of towers and water</syntaxhighlight> |
||
'''Examples:''' |
'''Examples:''' |
||
< |
<syntaxhighlight lang="j"> collectedWater 5 3 7 2 6 4 5 9 1 2 |
||
14 |
14 |
||
printTowers 5 3 7 2 6 4 5 9 1 2 |
printTowers 5 3 7 2 6 4 5 9 1 2 |
||
Line 1,745: | Line 2,596: | ||
TestResults =: 2 14 35 0 0 0 0 |
TestResults =: 2 14 35 0 0 0 0 |
||
TestResults -: collectedWater &> TestTowers NB. check tests |
TestResults -: collectedWater &> TestTowers NB. check tests |
||
1</ |
1</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
{{trans|D}} |
{{trans|D}} |
||
< |
<syntaxhighlight lang="java">public class WaterBetweenTowers { |
||
public static void main(String[] args) { |
public static void main(String[] args) { |
||
int i = 1; |
int i = 1; |
||
Line 1,798: | Line 2,649: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Block 1 holds 2 water units. |
<pre>Block 1 holds 2 water units. |
||
Line 1,812: | Line 2,663: | ||
===ES5=== |
===ES5=== |
||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
< |
<syntaxhighlight lang="javascript">(function () { |
||
'use strict'; |
'use strict'; |
||
Line 1,903: | Line 2,754: | ||
//--> [2, 14, 35, 0, 0, 0, 0] |
//--> [2, 14, 35, 0, 0, 0, 0] |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang="javascript">[2, 14, 35, 0, 0, 0, 0]</syntaxhighlight> |
||
===ES6=== |
===ES6=== |
||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
"use strict"; |
"use strict"; |
||
Line 2,043: | Line 2,894: | ||
// MAIN --- |
// MAIN --- |
||
return main(); |
return main(); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
< |
<syntaxhighlight lang="javascript">[2, 14, 35, 0, 0, 0, 0]</syntaxhighlight> |
||
=={{header|jq}}== |
|||
{{trans|Kotlin}} |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
<syntaxhighlight lang="jq">def waterCollected: |
|||
. as $tower |
|||
| ($tower|length) as $n |
|||
| ([0] + [range(1;$n) | ($tower[0:.] | max) ]) as $highLeft |
|||
| ( [range(1;$n) | ($tower[.:$n] | max) ] + [0]) as $highRight |
|||
| [ range(0;$n) | [ ([$highLeft[.], $highRight[.] ]| min) - $tower[.], 0 ] | max] |
|||
| add ; |
|||
def 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] |
|||
]; |
|||
towers[] |
|||
| "\(waterCollected) from \(.)"</syntaxhighlight> |
|||
{{out}} |
|||
As for [[#Kotlin]] and others. |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Inspired to [[#Python]]. |
Inspired to [[#Python]]. |
||
< |
<syntaxhighlight lang="julia">using Printf |
||
function watercollected(towers::Vector{Int}) |
function watercollected(towers::Vector{Int}) |
||
Line 2,093: | Line 2,971: | ||
towerprint(towers, watercollected(towers)) |
towerprint(towers, watercollected(towers)) |
||
println() |
println() |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,175: | Line 3,053: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="scala">// version 1.1.2 |
||
fun waterCollected(tower: IntArray): Int { |
fun waterCollected(tower: IntArray): Int { |
||
Line 2,197: | Line 3,075: | ||
println("${"%2d".format(waterCollected(tower))} from ${tower.contentToString()}") |
println("${"%2d".format(waterCollected(tower))} from ${tower.contentToString()}") |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,212: | Line 3,090: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="lua">function waterCollected(i,tower) |
||
local length = 0 |
local length = 0 |
||
for _ in pairs(tower) do |
for _ in pairs(tower) do |
||
Line 2,269: | Line 3,147: | ||
end |
end |
||
main()</ |
main()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Block 1 holds 2 water units. |
<pre>Block 1 holds 2 water units. |
||
Line 2,281: | Line 3,159: | ||
=={{header|M2000 Interpreter}}== |
=={{header|M2000 Interpreter}}== |
||
===Scan min-max for each bar=== |
===Scan min-max for each bar=== |
||
<syntaxhighlight lang="m2000 interpreter"> |
|||
<lang M2000 Interpreter> |
|||
Module Water { |
Module Water { |
||
Flush ' empty stack |
Flush ' empty stack |
||
Line 2,313: | Line 3,191: | ||
} |
} |
||
Water |
Water |
||
</syntaxhighlight> |
|||
</lang> |
|||
===Drain method=== |
===Drain method=== |
||
Module Water2 { |
Module Water2 { |
||
Line 2,349: | Line 3,227: | ||
} |
} |
||
Water2 |
Water2 |
||
<syntaxhighlight lang="m2000 interpreter"> |
|||
<lang M2000 Interpreter> |
|||
</syntaxhighlight> |
|||
</lang> |
|||
===Faster Method=== |
===Faster Method=== |
||
{{trans|AWK}} |
{{trans|AWK}} |
||
<syntaxhighlight lang="m2000 interpreter"> |
|||
<lang M2000 Interpreter> |
|||
Module Water3 { |
Module Water3 { |
||
Flush ' empty stack |
Flush ' empty stack |
||
Line 2,381: | Line 3,259: | ||
} |
} |
||
Water3 |
Water3 |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 2,389: | Line 3,267: | ||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[waterbetween] |
||
waterbetween[h_List] := Module[{mi, ma, ch}, |
waterbetween[h_List] := Module[{mi, ma, ch}, |
||
{mi, ma} = MinMax[h]; |
{mi, ma} = MinMax[h]; |
||
Line 2,406: | Line 3,284: | ||
8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1}, {5, 5, 5, 5}, {5, 6, 7, 8}, {8, |
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}}; |
7, 7, 6}, {6, 7, 10, 7, 6}}; |
||
waterbetween /@ h</ |
waterbetween /@ h</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{2, 14, 35, 0, 0, 0, 0}</pre> |
<pre>{2, 14, 35, 0, 0, 0, 0}</pre> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import math, sequtils, sugar |
||
proc water(barChart: seq[int], isLeftPeak = false, isRightPeak = false): int = |
proc water(barChart: seq[int], isLeftPeak = false, isRightPeak = false): int = |
||
Line 2,435: | Line 3,313: | ||
const waterUnits = barCharts.map(chart=>water(chart, false, false)) |
const waterUnits = barCharts.map(chart=>water(chart, false, false)) |
||
echo(waterUnits) |
echo(waterUnits) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
@[2, 14, 35, 0, 0, 0, 0] |
@[2, 14, 35, 0, 0, 0, 0] |
||
</pre > |
</pre > |
||
=={{header|Pascal}}== |
|||
{{works with|Delphi|7}} |
|||
{{works with|Free Pascal}} |
|||
<syntaxhighlight lang="pascal"> |
|||
program RainInFlatland; |
|||
{$IFDEF FPC} // Free Pascal |
|||
{$MODE Delphi} |
|||
{$ELSE} // Delphi |
|||
{$APPTYPE CONSOLE} |
|||
{$ENDIF} |
|||
uses SysUtils; |
|||
type THeight = integer; |
|||
// Heights could be f.p., but some changes to the code would be needed: |
|||
// (1) the inc function isn't available for f.p. values, |
|||
// (2) the print-out would need extra formatting. |
|||
{------------------------------------------------------------------------------ |
|||
Find highest tower; if there are 2 or more equal highest, choose any. |
|||
Then fill troughs so that on going towards the highest tower, from the |
|||
left-hand or right-hand end, there are no steps down. |
|||
Amount of filling required equals amount of water collected. |
|||
} |
|||
function FillTroughs( const h : array of THeight) : THeight; |
|||
var |
|||
m, i, i_max : integer; |
|||
h_max : THeight; |
|||
begin |
|||
result := 0; |
|||
m := High( h); // highest index, 0-based; there are m + 1 towers |
|||
if (m <= 1) then exit; // result = 0 if <= 2 towers |
|||
// Find highest tower and its index in the array. |
|||
h_max := h[0]; |
|||
i_max := 0; |
|||
for i := 1 to m do begin |
|||
if h[i] > h_max then begin |
|||
h_max := h[i]; |
|||
i_max := i; |
|||
end; |
|||
end; |
|||
// Fill troughs from left-hand end to highest tower |
|||
h_max := h[0]; |
|||
for i := 1 to i_max - 1 do begin |
|||
if h[i] < h_max then inc( result, h_max - h[i]) |
|||
else h_max := h[i]; |
|||
end; |
|||
// Fill troughs from right-hand end to highest tower |
|||
h_max := h[m]; |
|||
for i := m - 1 downto i_max + 1 do begin |
|||
if h[i] < h_max then inc( result, h_max - h[i]) |
|||
else h_max := h[i]; |
|||
end; |
|||
end; |
|||
{------------------------------------------------------------------------- |
|||
Wrapper for the above: finds amount of water, and prints input and result. |
|||
} |
|||
procedure CalcAndPrint( h : array of THeight); |
|||
var |
|||
water : THeight; |
|||
j : integer; |
|||
begin |
|||
water := FillTroughs( h); |
|||
Write( water:5, ' <-- ['); |
|||
for j := 0 to High( h) do begin |
|||
Write( h[j]); |
|||
if j < High(h) then Write(', ') else WriteLn(']'); |
|||
end; |
|||
end; |
|||
{--------------------------------------------------------------------------- |
|||
Main routine. |
|||
} |
|||
begin |
|||
CalcAndPrint([1,5,3,7,2]); |
|||
CalcAndPrint([5,3,7,2,6,4,5,9,1,2]); |
|||
CalcAndPrint([2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1]); |
|||
CalcAndPrint([5,5,5,5]); |
|||
CalcAndPrint([5,6,7,8]); |
|||
CalcAndPrint([8,7,7,6]); |
|||
CalcAndPrint([6,7,10,7,6]); |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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] |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">use Modern::Perl; |
||
use List::Util qw{ min max sum }; |
use List::Util qw{ min max sum }; |
||
Line 2,464: | Line 3,438: | ||
[ 8, 7, 7, 6 ], |
[ 8, 7, 7, 6 ], |
||
[ 6, 7, 10, 7, 6 ], |
[ 6, 7, 10, 7, 6 ], |
||
);</ |
);</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>2 14 35 0 0 0 0</pre> |
<pre>2 14 35 0 0 0 0</pre> |
||
Line 2,470: | Line 3,444: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
=== inefficient one-pass method === |
=== inefficient one-pass method === |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>function collect_water(sequence heights) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
integer res = 0 |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">collect_water</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">heights</span><span style="color: #0000FF;">)</span> |
|||
for i=2 to length(heights)-1 do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
integer lm = max(heights[1..i-1]), |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
rm = max(heights[i+1..$]), |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">lm</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]),</span> |
|||
d = min(lm,rm)-heights[i] |
|||
<span style="color: #000000;">rm</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$]),</span> |
|||
res += max(0,d) |
|||
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rm</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">+=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> |
|||
return res |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
constant tests = {{1,5,3,7,2}, |
|||
{5,3,7,2,6,4,5,9,1,2}, |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> |
|||
{2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span> |
|||
{5,5,5,5}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span> |
|||
{5,6,7,8}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},</span> |
|||
{8,7,7,6}, |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">},</span> |
|||
{6,7,10,7,6}} |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">},</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">}}</span> |
|||
for i=1 to length(tests) do |
|||
sequence ti = tests[i] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
printf(1,"%35s : %d\n",{sprint(ti),collect_water(ti)}) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
end for</lang> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%35s : %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">),</span><span style="color: #000000;">collect_water</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,504: | Line 3,481: | ||
</pre> |
</pre> |
||
=== more efficient two-pass version === |
=== more efficient two-pass version === |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>function collect_water(sequence heights) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">collect_water</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">heights</span><span style="color: #0000FF;">)</span> |
|||
integer left_max = heights[1], |
|||
right_max = heights[$] |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">left_max</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">heights</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> |
|||
sequence left_height = heights, |
|||
<span style="color: #000000;">right_max</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">heights</span><span style="color: #0000FF;">[$]</span> |
|||
right_height = heights |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">left_height</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">right_height</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">)</span> |
|||
for i=2 to length(heights)-1 do |
|||
left_max = max(heights[i],left_max) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
left_height[i] = left_max |
|||
<span style="color: #000000;">left_max</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">left_max</span><span style="color: #0000FF;">)</span> |
|||
right_max = max(heights[-i],right_max) |
|||
<span style="color: #000000;">left_height</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">left_max</span> |
|||
right_height[-i] = right_max |
|||
<span style="color: #000000;">right_max</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">[-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">right_max</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #000000;">right_height</span><span style="color: #0000FF;">[-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">right_max</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
sequence mins = sq_min(left_height,right_height), |
|||
diffs = sq_sub(mins,heights) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mins</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">left_height</span><span style="color: #0000FF;">,</span><span style="color: #000000;">right_height</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">diffs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mins</span><span style="color: #0000FF;">,</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">)</span> |
|||
return sum(diffs) |
|||
end function</lang> |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">diffs</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<!--</syntaxhighlight>--> |
|||
(same output) |
(same output) |
||
=== pretty print routine === |
=== pretty print routine === |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>procedure print_water(sequence heights) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
integer res = 0, l = length(heights) |
|||
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.2"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (bugfix in p2js.js/$sidii(), 20/4/22)</span> |
|||
sequence towers = repeat(repeat(' ',l),max(heights)) |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">print_water</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">heights</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to l do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">)</span> |
|||
for j=1 to heights[i] do |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">towers</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">))</span> |
|||
towers[-j][i] = '#' |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span> |
|||
end for |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">heights</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span> |
|||
if i>1 and i<l then |
|||
<span style="color: #000000;">towers</span><span style="color: #0000FF;">[-</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'#'</span> |
|||
integer lm = max(heights[1..i-1]), |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
rm = max(heights[i+1..$]), |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #000000;">l</span> <span style="color: #008080;">then</span> |
|||
m = min(lm,rm) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">lm</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]),</span> |
|||
for j=heights[i]+1 to m do |
|||
<span style="color: #000000;">rm</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$]),</span> |
|||
towers[-j][i] = '~' |
|||
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rm</span><span style="color: #0000FF;">)</span> |
|||
res += 1 |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">heights</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">m</span> <span style="color: #008080;">do</span> |
|||
end for |
|||
<span style="color: #000000;">towers</span><span style="color: #0000FF;">[-</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'~'</span> |
|||
end if |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
printf(1,"%s\ncollected:%d\n",{join(towers,"\n"),res}) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\ncollected:%d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">towers</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">),</span><span style="color: #000000;">res</span><span style="color: #0000FF;">})</span> |
|||
print_water({5,3,7,2,6,4,5,9,1,2})</lang> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #000000;">print_water</span><span style="color: #0000FF;">({</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">})</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,563: | Line 3,547: | ||
=={{header|Phixmonti}}== |
=={{header|Phixmonti}}== |
||
{{trans|Phix}} |
{{trans|Phix}} |
||
< |
<syntaxhighlight lang="phixmonti">include ..\Utilitys.pmt |
||
def collect_water |
def collect_water |
||
Line 2,589: | Line 3,573: | ||
len for |
len for |
||
get dup print " : " print collect_water ? |
get dup print " : " print collect_water ? |
||
endfor</ |
endfor</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[1, 5, 3, 7, 2] : 2 |
<pre>[1, 5, 3, 7, 2] : 2 |
||
Line 2,602: | Line 3,586: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de water (Lst) |
||
(sum |
(sum |
||
'((A) |
'((A) |
||
Line 2,619: | Line 3,603: | ||
(5 6 7 8) |
(5 6 7 8) |
||
(8 7 7 6) |
(8 7 7 6) |
||
(6 7 10 7 6) ) ) )</ |
(6 7 10 7 6) ) ) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>(2 14 35 0 0 0 0)</pre> |
<pre>(2 14 35 0 0 0 0)</pre> |
||
Line 2,626: | Line 3,610: | ||
Based on the algorithm explained at [http://stackoverflow.com/questions/24414700/amazon-water-collected-between-towers/32135773#32135773 Stack Overflow]: |
Based on the algorithm explained at [http://stackoverflow.com/questions/24414700/amazon-water-collected-between-towers/32135773#32135773 Stack Overflow]: |
||
< |
<syntaxhighlight lang="python">def water_collected(tower): |
||
N = len(tower) |
N = len(tower) |
||
highest_left = [0] + [max(tower[:n]) for n in range(1,N)] |
highest_left = [0] + [max(tower[:n]) for n in range(1,N)] |
||
Line 2,648: | Line 3,632: | ||
[6, 7, 10, 7, 6]] |
[6, 7, 10, 7, 6]] |
||
[water_collected(tower) for tower in towers]</ |
[water_collected(tower) for tower in towers]</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 2,698: | Line 3,682: | ||
Or, expressed in terms of '''itertools.accumulate''', and showing diagrams: |
Or, expressed in terms of '''itertools.accumulate''', and showing diagrams: |
||
< |
<syntaxhighlight lang="python">'''Water collected between towers''' |
||
from itertools import accumulate |
from itertools import accumulate |
||
Line 2,815: | Line 3,799: | ||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main() |
main() |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> █ |
<pre> █ |
||
Line 2,923: | Line 3,907: | ||
[6,7,10,7,6] -> 0</pre> |
[6,7,10,7,6] -> 0</pre> |
||
=={{header|Quackery}}== |
|||
<syntaxhighlight lang="Quackery"> [ $ "turtleduck.qky" loadfile ] now! |
|||
[ dup 0 = iff drop done |
|||
dup 2 times |
|||
[ 20 * 1 walk |
|||
1 4 turn |
|||
20 1 walk |
|||
1 4 turn ] ] is bar ( [ --> ) |
|||
[ tuck size unrot |
|||
-1 4 turn |
|||
witheach |
|||
[ dup |
|||
' [ 158 151 147 ] |
|||
dup colour |
|||
fill bar |
|||
dup 20 * 1 fly |
|||
dip |
|||
[ behead |
|||
' [ 162 197 208 ] |
|||
dup colour |
|||
fill bar ] |
|||
-20 * 1 fly |
|||
1 4 turn |
|||
20 1 fly |
|||
-1 4 turn ] |
|||
drop |
|||
1 4 turn |
|||
-20 * 1 fly ] is chart ( [ [ --> ) |
|||
[ [] 0 rot witheach |
|||
[ max dup dip join ] |
|||
drop ] is rightmax ( [ --> [ ) |
|||
[ reverse |
|||
rightmax |
|||
reverse ] is leftmax ( [ --> [ ) |
|||
[ [] unrot |
|||
witheach |
|||
[ over i^ peek |
|||
min swap dip join ] |
|||
drop ] is mins ( [ --> [ ) |
|||
[ [] unrot |
|||
witheach |
|||
[ over i^ peek |
|||
- swap dip join ] |
|||
drop ] is diffs ( [ --> [ ) |
|||
[ 0 swap witheach + ] is sum ( [ --> n ) |
|||
[ dup 2dup rightmax |
|||
swap leftmax |
|||
mins diffs chart ] is task1 ( [ --> ) |
|||
[ dup dup rightmax |
|||
swap leftmax |
|||
mins diffs sum ] is task2 ( [ --> ) |
|||
turtle |
|||
10 frames |
|||
-540 1 fly |
|||
' [ [ 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 ] ] |
|||
dup |
|||
witheach |
|||
[ dup size swap |
|||
task1 |
|||
1+ 20 * 1 fly ] |
|||
witheach |
|||
[ task2 echo sp ] |
|||
1 frames</syntaxhighlight> |
|||
{{out}} |
|||
I see from the discussion page that drawing the towers wasn't part of the task. Here they are anyway. |
|||
"What is the use of a book," thought Alice, "without pictures or conversations?" |
|||
[[File:Quackery - Water collected between towers.png|thumb|center]] |
|||
<pre>2 14 35 0 0 0 0</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket/base |
||
(require racket/match) |
(require racket/match) |
||
Line 2,959: | Line 4,035: | ||
[6 7 10 7 6]])) |
[6 7 10 7 6]])) |
||
(map water-collected-between-towers towerss)) |
(map water-collected-between-towers towerss)) |
||
(list 2 14 35 0 0 0 0)))</ |
(list 2 14 35 0 0 0 0)))</syntaxhighlight> |
||
When run produces no output -- meaning that the tests have run successfully. |
When run produces no output -- meaning that the tests have run successfully. |
||
Line 2,967: | Line 4,043: | ||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
<lang |
<syntaxhighlight lang="raku" line>sub max_l ( @a ) { [\max] @a } |
||
sub max_r ( @a ) { ([\max] @a.reverse).reverse } |
sub max_r ( @a ) { ([\max] @a.reverse).reverse } |
||
Line 2,986: | Line 4,062: | ||
[ 8, 7, 7, 6 ], |
[ 8, 7, 7, 6 ], |
||
[ 6, 7, 10, 7, 6 ], |
[ 6, 7, 10, 7, 6 ], |
||
;</ |
;</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>(2 14 35 0 0 0 0)</pre> |
<pre>(2 14 35 0 0 0 0)</pre> |
||
Line 2,992: | Line 4,068: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===version 1=== |
===version 1=== |
||
< |
<syntaxhighlight lang="rexx">/* REXX */ |
||
Call bars '1 5 3 7 2' |
Call bars '1 5 3 7 2' |
||
Call bars '5 3 7 2 6 4 5 9 1 2' |
Call bars '5 3 7 2 6 4 5 9 1 2' |
||
Line 3,057: | Line 4,133: | ||
Say ol |
Say ol |
||
End |
End |
||
Return</ |
Return</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 5 3 7 2 -> 2 |
<pre>1 5 3 7 2 -> 2 |
||
Line 3,123: | Line 4,199: | ||
===version 2, simple numeric list output=== |
===version 2, simple numeric list output=== |
||
< |
<syntaxhighlight lang="rexx">/*REXX program calculates and displays the amount of rainwater collected between towers.*/ |
||
call tower 1 5 3 7 2 |
call tower 1 5 3 7 2 |
||
call tower 5 3 7 2 6 4 5 9 1 2 |
call tower 5 3 7 2 6 4 5 9 1 2 |
||
Line 3,145: | Line 4,221: | ||
end /*f*/ |
end /*f*/ |
||
say right(w.00, 9) 'units of rainwater collected for: ' y /*display water units.*/ |
say right(w.00, 9) 'units of rainwater collected for: ' y /*display water units.*/ |
||
return</ |
return</syntaxhighlight> |
||
{{out|output|text= }} |
{{out|output|text= }} |
||
<pre> |
<pre> |
||
Line 3,161: | Line 4,237: | ||
It tries to protect the aspect ratio by showing the buildings as in this task's preamble. |
It tries to protect the aspect ratio by showing the buildings as in this task's preamble. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program calculates and displays the amount of rainwater collected between towers.*/ |
||
call tower 1 5 3 7 2 |
call tower 1 5 3 7 2 |
||
call tower 5 3 7 2 6 4 5 9 1 2 |
call tower 5 3 7 2 6 4 5 9 1 2 |
||
Line 3,195: | Line 4,271: | ||
do z=t.0 by -1 to 0; say p.z /*display various tower floors & water.*/ |
do z=t.0 by -1 to 0; say p.z /*display various tower floors & water.*/ |
||
end /*z*/ |
end /*z*/ |
||
return</ |
return</syntaxhighlight> |
||
{{out|output|text= }} |
{{out|output|text= }} |
||
<pre> |
<pre> |
||
Line 3,259: | Line 4,335: | ||
2 ██████████ |
2 ██████████ |
||
1 ██████████ no units of rainwater collected |
1 ██████████ no units of rainwater collected |
||
</pre> |
|||
=={{header|RPL}}== |
|||
{{trans|Python}} |
|||
{{works with|HP|49/50}} |
|||
« DUPDUP SIZE 1 - NDUPN →LIST |
|||
DUP 1 « 1 NSUB SUB 0 + « MAX » STREAM » DOSUBS 0 SWAP + <span style="color:grey">@ the seq of max heights to the left of each tower</span> |
|||
SWAP 1 « NSUB 1 + OVER SIZE SUB 0 + « MAX » STREAM » DOSUBS 0 + <span style="color:grey">@ the seq of max heights to the right of each tower</span> |
|||
MIN SWAP - |
|||
1 « 0 MAX » DOLIST ∑LIST |
|||
» '<span style="color:blue">WATER</span>' STO |
|||
« { {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} } |
|||
1 « <span style="color:blue">WATER</span> » DOLIST |
|||
» '<span style="color:blue">TASK</span>' STO |
|||
{{out}} |
|||
<pre> |
|||
1: { 2 14 35 0 0 0 0 } |
|||
</pre> |
</pre> |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby"> |
||
def a(array) |
def a(array) |
||
n=array.length |
n=array.length |
||
Line 3,297: | Line 4,397: | ||
a([ 8, 7, 7, 6 ]) |
a([ 8, 7, 7, 6 ]) |
||
a([ 6, 7, 10, 7, 6 ]) |
a([ 6, 7, 10, 7, 6 ]) |
||
return</ |
return</syntaxhighlight> |
||
'''output''' |
'''output''' |
||
<pre> |
<pre> |
||
Line 3,309: | Line 4,409: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust"> |
||
use std::cmp::min; |
use std::cmp::min; |
||
Line 3,342: | Line 4,442: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''output''' |
'''output''' |
||
<pre> |
<pre> |
||
Line 3,363: | Line 4,463: | ||
{{libheader|Scastie qualified}} |
{{libheader|Scastie qualified}} |
||
{{works with|Scala|2.13}} |
{{works with|Scala|2.13}} |
||
< |
<syntaxhighlight lang="scala">import scala.collection.parallel.CollectionConverters.VectorIsParallelizable |
||
// Program to find maximum amount of water |
// Program to find maximum amount of water |
||
Line 3,391: | Line 4,491: | ||
println(s"Block ${barSet._2 + 1} could hold max. ${sqBoxWater(barSet._1)} units.")) |
println(s"Block ${barSet._2 + 1} could hold max. ${sqBoxWater(barSet._1)} units.")) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
< |
<syntaxhighlight lang="scheme">(import (scheme base) |
||
(scheme write)) |
(scheme write)) |
||
Line 3,427: | Line 4,527: | ||
(5 6 7 8) |
(5 6 7 8) |
||
(8 7 7 6) |
(8 7 7 6) |
||
(6 7 10 7 6)))</ |
(6 7 10 7 6)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>(1 5 3 7 2) -> 2 |
<pre>(1 5 3 7 2) -> 2 |
||
Line 3,442: | Line 4,542: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func max_l(Array a, m = a[0]) { |
||
gather { a.each {|e| take(m = max(m, e)) } } |
gather { a.each {|e| take(m = max(m, e)) } } |
||
} |
} |
||
Line 3,463: | Line 4,563: | ||
[ 8, 7, 7, 6 ], |
[ 8, 7, 7, 6 ], |
||
[ 6, 7, 10, 7, 6 ], |
[ 6, 7, 10, 7, 6 ], |
||
].map { water_collected(_) }.say</ |
].map { water_collected(_) }.say</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,470: | Line 4,570: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang="swift">// Based on this answer from Stack Overflow: |
||
// https://stackoverflow.com/a/42821623 |
// https://stackoverflow.com/a/42821623 |
||
Line 3,503: | Line 4,603: | ||
[6, 7, 10, 7, 6]] { |
[6, 7, 10, 7, 6]] { |
||
print("water collected = \(waterCollected(heights))") |
print("water collected = \(waterCollected(heights))") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,517: | Line 4,617: | ||
=={{header|Tailspin}}== |
=={{header|Tailspin}}== |
||
< |
<syntaxhighlight lang="tailspin"> |
||
templates histogramWater |
templates histogramWater |
||
$ -> \( @: 0"1"; |
$ -> \( @: 0"1"; |
||
[$... -> { leftMax: $ -> #, value: ($)"1" } ] ! |
[$... -> ($)"1"-> { leftMax: $ -> #, value: ($)"1" } ] ! |
||
when <$@..> do @: $; $ ! |
when <$@..> do @: $; $ ! |
||
otherwise $@ ! |
otherwise $@ ! |
||
Line 3,532: | Line 4,632: | ||
\) ! |
\) ! |
||
end histogramWater |
end histogramWater |
||
[[1, 5, 3, 7, 2], |
[[1, 5, 3, 7, 2], |
||
[5, 3, 7, 2, 6, 4, 5, 9, 1, 2], |
[5, 3, 7, 2, 6, 4, 5, 9, 1, 2], |
||
Line 3,540: | Line 4,640: | ||
[8, 7, 7, 6], |
[8, 7, 7, 6], |
||
[6, 7, 10, 7, 6]]... -> '$ -> histogramWater; water in $;$#10;' -> !OUT::write |
[6, 7, 10, 7, 6]]... -> '$ -> histogramWater; water in $;$#10;' -> !OUT::write |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
2 water in [1, 5, 3, 7, 2] |
2"1" water in [1, 5, 3, 7, 2] |
||
14 water in [5, 3, 7, 2, 6, 4, 5, 9, 1, 2] |
14"1" water in [5, 3, 7, 2, 6, 4, 5, 9, 1, 2] |
||
35 water in [2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1] |
35"1" water in [2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1] |
||
0 water in [5, 5, 5, 5] |
0"1" water in [5, 5, 5, 5] |
||
0 water in [5, 6, 7, 8] |
0"1" water in [5, 6, 7, 8] |
||
0 water in [8, 7, 7, 6] |
0"1" water in [8, 7, 7, 6] |
||
0 water in [6, 7, 10, 7, 6] |
0"1" water in [6, 7, 10, 7, 6] |
||
</pre> |
</pre> |
||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
Tcl makes for a surprisingly short and readable implementation, next to some of the more functional-oriented languages. |
Tcl makes for a surprisingly short and readable implementation, next to some of the more functional-oriented languages. |
||
< |
<syntaxhighlight lang="tcl">namespace path {::tcl::mathfunc ::tcl::mathop} |
||
proc flood {ground} { |
proc flood {ground} { |
||
Line 3,589: | Line 4,689: | ||
} { |
} { |
||
puts [flood $p]:\t$p |
puts [flood $p]:\t$p |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,600: | Line 4,700: | ||
0: 8 7 7 6 |
0: 8 7 7 6 |
||
0: 6 7 10 7 6</pre> |
0: 6 7 10 7 6</pre> |
||
=={{header|Visual Basic .NET}}== |
|||
===Version 1=== |
|||
'''Method:''' Instead of "scanning" adjoining towers for each column, this routine converts the tower data into a string representation with building blocks, empty spaces, and potential water retention sites. The potential water retention sites are then "eroded" away where they are found to be unsupported. This is accomplished with the '''.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 |
|||
[[{{FULLPAGENAME}}#version_3|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. |
|||
Module Module1 |
|||
Sub Main(Args() As String) |
|||
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 = vbLf, ' Line feed to separate floors in a block of towers. |
|||
tb = "██", wr = "≈≈", mt = " " ' Tower Block, Water Retained, eMpTy space. |
|||
For i As Integer = 0 To wta.Length - 1 |
|||
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 wta(i).Length - 1 |
|||
If wta(i)(j) > 0 Then ' Tower block detected, add block to floor, |
|||
floor &= tb : wta(i)(j) -= 1 : bpf += 1 ' reduce tower by one. |
|||
Else ' Empty space detected, fill when not first or last column. |
|||
floor &= If(j > 0 AndAlso j < wta(i).Length - 1, wr, mt) |
|||
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. |
|||
' Erode potential water retention cells from left and right. |
|||
While blk.Contains(mt & wr) : blk = blk.Replace(mt & wr, mt & mt) : End While |
|||
While blk.Contains(wr & mt) : blk = blk.Replace(wr & mt, mt & mt) : End While |
|||
' Optionaly show towers w/ water marks. |
|||
If shoTow Then Console.Write("{0}{1}", lf, blk) |
|||
' Subtract the amount of non-water mark characters from the total char amount. |
|||
Console.Write("Block {0} retains {1,2} water units.{2}", i + 1, |
|||
(blk.Length - blk.Replace(wr, "").Length) \ 2, lf) |
|||
Next |
|||
End Sub |
|||
End Module</lang> |
|||
{{out}}<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>Module Module1 |
|||
''' <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 |
|||
End Module</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> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
Line 3,850: | Line 4,705: | ||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="wren">import "./math" for Math, Nums |
||
import "/fmt" for Fmt |
import "./fmt" for Fmt |
||
var waterCollected = Fn.new { |tower| |
var waterCollected = Fn.new { |tower| |
||
Line 3,857: | Line 4,712: | ||
var highLeft = [0] + (1...n).map { |i| Nums.max(tower[0...i]) }.toList |
var highLeft = [0] + (1...n).map { |i| Nums.max(tower[0...i]) }.toList |
||
var highRight = (1...n).map { |i| Nums.max(tower[i...n]) }.toList + [0] |
var highRight = (1...n).map { |i| Nums.max(tower[i...n]) }.toList + [0] |
||
var t = (0...n).map { |i| |
var t = (0...n).map { |i| Math.max(Math.min(highLeft[i], highRight[i]) - tower[i], 0) } |
||
return Nums.sum(t) |
return Nums.sum(t) |
||
} |
} |
||
Line 3,870: | Line 4,725: | ||
[6, 7, 10, 7, 6] |
[6, 7, 10, 7, 6] |
||
] |
] |
||
for (tower in towers) Fmt.print("$2d from $n", waterCollected.call(tower), tower)</ |
for (tower in towers) Fmt.print("$2d from $n", waterCollected.call(tower), tower)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,883: | Line 4,738: | ||
</pre> |
</pre> |
||
=={{header| |
=={{header|XPL0}}== |
||
<syntaxhighlight lang="xpl0">func WaterCollected(Array, Width); \Return amount of water collected |
|||
{{trans|AWK}} |
|||
int Array, Width, Height, I, Row, Col, Left, Right, Water; |
|||
<lang Yabasic>data 7 |
|||
[Water:= 0; Height:= 0; |
|||
data "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" |
|||
for I:= 0 to Width-1 do \find max height |
|||
data "5,5,5,5", "5,6,7,8", "8,7,7,6", "6,7,10,7,6" |
|||
if Array(I) > Height then Height:= Array(I); |
|||
for Row:= 2 to Height do |
|||
for Col:= 1 to Width-2 do \(zero-based) |
|||
if Row > Array(Col) then \empty location |
|||
[Left:= false; Right:= false; \check for barriers |
|||
for I:= 0 to Width-1 do |
|||
if Array(I) >= Row then \have barrier |
|||
[if I < Col then Left:= true; |
|||
if I > Col then Right:= true; |
|||
]; |
|||
if Left & Right then Water:= Water+1; |
|||
]; |
|||
return Water; |
|||
]; |
|||
int Towers, I; |
|||
read n |
|||
[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], |
|||
[0]]; \for determining sub-array lengths |
|||
for I:= 0 to 7-1 do |
|||
[IntOut( 0, WaterCollected(Towers(I), (Towers(I+1)-Towers(I))/4) ); |
|||
ChOut(0, ^ ); |
|||
]; |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
for i = 1 to n |
|||
<pre> |
|||
read n$ |
|||
2 14 35 0 0 0 0 |
|||
wcbt(n$) |
|||
</pre> |
|||
next i |
|||
sub wcbt(s$) |
|||
local tower$(1), hr(1), hl(1), n, i, ans, k |
|||
n = token(s$, tower$(), ",") |
|||
redim hr(n) |
|||
redim hl(n) |
|||
for i = n to 1 step -1 |
|||
if i < n then |
|||
k = hr(i + 1) |
|||
else |
|||
k = 0 |
|||
end if |
|||
hr(i) = max(val(tower$(i)), k) |
|||
next i |
|||
for i = 1 to n |
|||
if i then |
|||
k = hl(i - 1) |
|||
else |
|||
k = 0 |
|||
end if |
|||
hl(i) = max(val(tower$(i)), k) |
|||
ans = ans + min(hl(i), hr(i)) - val(tower$(i)) |
|||
next i |
|||
print ans," ",n$ |
|||
end sub</lang> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
< |
<syntaxhighlight lang="zkl">fcn waterCollected(walls){ |
||
// compile max wall heights from left to right and right to left |
// compile max wall heights from left to right and right to left |
||
// then each pair is left/right wall of that cell. |
// then each pair is left/right wall of that cell. |
||
Line 3,938: | Line 4,793: | ||
xs.reduce('wrap(s,x,a){ s=f(s,x); a.append(s); s },i,ss:=List()); |
xs.reduce('wrap(s,x,a){ s=f(s,x); a.append(s); s },i,ss:=List()); |
||
ss |
ss |
||
} // scanl((1,5,3,7,2),max,0) --> (1,5,5,7,7)</ |
} // scanl((1,5,3,7,2),max,0) --> (1,5,5,7,7)</syntaxhighlight> |
||
< |
<syntaxhighlight 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(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(5, 5, 5, 5), T(5, 6, 7, 8),T(8, 7, 7, 6), |
||
T(6, 7, 10, 7, 6) ) |
T(6, 7, 10, 7, 6) ) |
||
.pump(List, waterCollected).println();</ |
.pump(List, waterCollected).println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Revision as of 17:37, 19 February 2024
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.
11l
F water_collected(tower)
V l = tower.len
V highest_left = [0] [+] (1 .< l).map(n -> max(@tower[0 .< n]))
V highest_right = (1 .< l).map(n -> max(@tower[n .< @l])) [+] [0]
V water_level = (0 .< l).map(n -> max(min(@highest_left[n], @highest_right[n]) - @tower[n], 0))
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(‘’)
R sum(water_level)
V 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]]
print(towers.map(tower -> water_collected(tower)))
- 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, 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]
8080 Assembly
org 100h
jmp demo
;;; Calculate the amount of water a row of towers will hold
;;; Note: this will destroy the input array.
;;; Input: DE = tower array, BC = length of array
;;; Output: A = amount of water
water: xra a ; Start with no water
sta w_out+1
wscanr: mov h,d ; HL = right edge
mov l,e
dad b
wscrlp: dcx h
call cmp16 ; Reached beginning?
jnc w_out ; Then stop
mov a,m ; Otherwise, if current tower is zero
ora a
jz wscrlp ; Then keep scanning
push b ; Keep length
push d ; Keep array begin
mvi b,0 ; No blocks yet
xchg ; HL = left scanning edge, DE = right
wscanl: mov a,m ; Get current column
ora a ; Is zero?
jz wunit ; Then see if an unit of water must be added
dcr m ; Otherwise, decrease column
inr b ; Increase blocks
jmp wnext
wunit: mov a,b ; Any blocks?
ora a
jz wnext
lda w_out+1 ; If so, add water
inr a
sta w_out+1
wnext: inx h ; Next column
call cmp16
jnc wscanl ; Until right edge reached
mov a,b
cmc ; Check if more than 1 block left
rar
ora a
pop d ; Restore array begin
pop b ; and length
jnz wscanr ; If more than 1 block, keep scanning
w_out: mvi a,0 ; Load water into A
ret
;;; 16-bit compare DE to HL
cmp16: mov a,d
cmp h
rnz
mov a,e
cmp l
ret
;;; Calculate and print the amount of water for each input
demo: lxi h,series
load: mov e,m ; Load pointer
inx h
mov d,m
inx h
mov c,m ; Load length
inx h
mov b,m
inx h
mov a,d ; If pointer is zero,
ora e
rz ; stop.
push h ; Otherwise, save the series pointer
call water ; Calculate amount of water
call printa ; Output amount of water
pop h ; Restore series pointer
jmp load ; Load next example
;;; Print A as integer value
printa: lxi d,num ; Pointer to number string
mvi c,10 ; Divisor
digit: mvi b,-1 ; Quotient
dloop: inr b ; Divide (by trial subtraction)
sub c
jnc dloop
adi '0'+10 ; ASCII digit from remainder
dcx d ; Store ASCII digit
stax d
mov a,b ; Continue with quotient
ana a ; If not zero
jnz digit
mvi c,9 ; 9 = CP/M print string syscall
jmp 5 ; Print number string
db '***' ; Output number placeholder
num: db ' $'
;;; Series
t1: db 1,5,3,7,2
t2: db 5,3,7,2,6,4,5,9,1,2
t3: db 2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1
t4: db 5,5,5,5
t5: db 5,6,7,8
t6: db 8,7,7,6
t7: db 6,7,10,7,6
t_end: equ $
;;; Lengths and pointers
series: dw t1,t2-t1
dw t2,t3-t2
dw t3,t4-t3
dw t4,t5-t4
dw t5,t6-t5
dw t6,t7-t6
dw t7,t_end-t7
dw 0
- Output:
2 14 35 0 0 0 0
8086 Assembly
cpu 8086
org 100h
section .text
jmp demo
;;; Calculate the amount of water a row of towers will hold
;;; Note: this will destroy the input array.
;;; Input: DX = tower array, CX = length of array
;;; Output: AX = amount of water
water: xor ax,ax ; Amount of water starts at zero
xor bx,bx ; BH = zero, BL = block count
.scanr: mov di,dx ; DI = right edge of towers
add di,cx
.rloop: dec di
cmp di,dx ; Reached beginning?
jl .out ; Then calculation is done.
cmp bh,[di] ; Otherwise, if the tower is zero,
je .rloop ; Keep scanning
xor bl,bl ; Set block count to zero
mov si,dx ; SI = left scanning edge
.scanl: cmp bh,[si] ; Is the column empty?
je .unit ; Then see whether to add an unit of water
dec byte [si] ; Otherwise, remove block from tower
inc bx ; And count it
jmp .next
.unit: test bl,bl ; Any blocks?
jz .next
inc ax ; If so, add unit of water
.next: inc si ; Scan rightward
cmp si,di ; Reached the right edge?
jbe .scanl ; If not, keep going
shr bl,1 ; If more than 1 block,
jnz .scanr ; Keep going
.out: ret
;;; Calculate and print the amount of water for each input
demo: mov si,series
.loop: lodsw ; Load pointer
test ax,ax ; If 0,
jz .done ; we're done.
xchg ax,dx
lodsw ; Load length
xchg ax,cx
push si ; Keep array pointer
call water ; Calculate amount of water
call prax ; Print AX
pop si ; Restore array pointer
jmp .loop
.done: ret
;;; Print AX as number
prax: mov bx,num ; Pointer to end of number string
mov cx,10 ; Divisor
.dgt: xor dx,dx ; Divide by 10
div cx
add dl,'0' ; Add ASCII 0 to remainder
dec bx ; Store digit
mov [bx],dl
test ax,ax ; If number not zero yet
jnz .dgt ; Find rest of digits
mov dx,bx ; Print number string
mov ah,9
int 21h
ret
section .data
db '*****' ; Output number placeholder
num: db ' $'
;;; Series
t1: db 1,5,3,7,2
t2: db 5,3,7,2,6,4,5,9,1,2
t3: db 2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1
t4: db 5,5,5,5
t5: db 5,6,7,8
t6: db 8,7,7,6
t7: db 6,7,10,7,6
t_end: equ $
;;; Lengths and pointers
series: dw t1,t2-t1
dw t2,t3-t2
dw t3,t4-t3
dw t4,t5-t4
dw t5,t6-t5
dw t6,t7-t6
dw t7,t_end-t7
dw 0
- Output:
2 14 35 0 0 0 0
Action!
PROC PrintArray(BYTE ARRAY a BYTE len)
BYTE i
Put('[)
FOR i=0 TO len-1
DO
IF i>0 THEN
Put(32)
FI
PrintB(a(i))
OD
Put('])
RETURN
BYTE FUNC Max(BYTE ARRAY a BYTE start,stop)
BYTE i,res
res=0
FOR i=start TO stop
DO
IF a(i)>res THEN
res=a(i)
FI
OD
RETURN (res)
BYTE FUNC CalcWater(BYTE ARRAY a BYTE len)
BYTE water,i,maxL,maxR,lev
IF len<3 THEN
RETURN (0)
FI
water=0
FOR i=1 TO len-2
DO
maxL=Max(a,0,i-1)
maxR=Max(a,i+1,len-1)
IF maxL<maxR THEN
lev=maxL
ELSE
lev=maxR
FI
IF a(i)<lev THEN
water==+lev-a(i)
FI
OD
RETURN (water)
PROC Test(BYTE ARRAY a BYTE len)
BYTE water
water=CalcWater(a,len)
PrintArray(a,len)
PrintF(" holds %B water units%E%E",water)
RETURN
PROC Main()
DEFINE COUNT="7"
BYTE ARRAY
a1=[1 5 3 7 2],
a2=[5 3 7 2 6 4 5 9 1 2],
a3=[2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1],
a4=[5 5 5 5],
a5=[5 6 7 8],
a6=[8 7 7 6],
a7=[6 7 10 7 6]
Test(a1,5)
Test(a2,10)
Test(a3,16)
Test(a4,4)
Test(a5,4)
Test(a6,4)
Test(a7,5)
RETURN
- Output:
Screenshot from Atari 8-bit computer
[1 5 3 7 2] holds 2 water units [5 3 7 2 6 4 5 9 1 2] holds 14 water units [2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1] holds 35 water units [5 5 5 5] holds 0 water units [5 6 7 8] holds 0 water units [8 7 7 6] holds 0 water units [6 7 10 7 6] holds 0 water units
Ada
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;
- Output:
The series: [ 1 5 3 7 2 ] holds 2 units of water. The series: [ 5 3 7 2 6 4 5 9 1 2 ] holds 14 units of water. The series: [ 2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1 ] holds 35 units of water. The series: [ 5 5 5 5 ] holds 0 units of water. The series: [ 5 6 7 8 ] holds 0 units of water. The series: [ 8 7 7 6 ] holds 0 units of water. The series: [ 6 7 10 7 6 ] holds 0 units of water.
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
- Output:
{2, 14, 35, 0, 0, 0, 0}
Arturo
cmax: function => [
m: neg ∞
map & 'x -> m:<=max @[m x]
]
vmin: $ => [map couple & & => min]
vsub: $ => [map couple & & 'p -> p\0 - p\1]
water: function [a][
sum vsub vmin reverse cmax reverse a cmax a a
]
loop [
[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]
] 'a -> print [a "->" water a]
- 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
AutoHotkey
WCBT(oTwr){
topL := Max(oTwr*), l := num := 0, barCh := lbarCh := "", oLvl := []
while (++l <= topL)
for t, h in oTwr
oLvl[l,t] := h ? "██" : "≈≈" , oTwr[t] := oTwr[t]>0 ? oTwr[t]-1 : 0
for l, obj in oLvl{
while (oLvl[l, A_Index] = "≈≈")
oLvl[l, A_Index] := " "
while (oLvl[l, obj.Count() +1 - A_Index] = "≈≈")
oLvl[l, obj.Count() +1 - A_Index] := " "
for t, v in obj
lbarCh .= StrReplace(v, "≈≈", "≈≈", n), num += n
barCh := lbarCh "`n" barCh, lbarCh := ""
}
return [num, barCh]
}
Examples:
data := [[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]]
result := ""
for i, oTwr in data{
inp := ""
for i, h in oTwr
inp .= h ", "
inp := "[" Trim(inp, ", ") "]"
x := WCBT(oTwr)
result .= "Chart " inp " has " x.1 " water units`n" x.2 "------------------------`n"
}
MsgBox % result
- Output:
Chart [1, 5, 3, 7, 2] has 2 water units ██ ██ ██≈≈██ ██≈≈██ ██████ ████████ ██████████ ------------------------ Chart [5, 3, 7, 2, 6, 4, 5, 9, 1, 2] has 14 water units ██ ██ ██≈≈≈≈≈≈≈≈██ ██≈≈██≈≈≈≈██ ██≈≈██≈≈██≈≈████ ██≈≈██≈≈████████ ██████≈≈████████ ████████████████≈≈██ ████████████████████ ------------------------ Chart [2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1] has 35 water units ██ ██≈≈≈≈≈≈≈≈≈≈≈≈≈≈██ ██≈≈≈≈≈≈██≈≈≈≈≈≈≈≈≈≈≈≈≈≈██ ██≈≈██≈≈██≈≈≈≈≈≈≈≈██≈≈████ ██≈≈██≈≈██≈≈██≈≈≈≈██≈≈██████ ██████≈≈██≈≈██≈≈≈≈██████████ ████████████≈≈████████████████ ████████████████████████████████ ------------------------ Chart [5, 5, 5, 5] has 0 water units ████████ ████████ ████████ ████████ ████████ ------------------------ Chart [5, 6, 7, 8] has 0 water units ██ ████ ██████ ████████ ████████ ████████ ████████ ████████ ------------------------ Chart [8, 7, 7, 6] has 0 water units ██ ██████ ████████ ████████ ████████ ████████ ████████ ████████ ------------------------ Chart [6, 7, 10, 7, 6] has 0 water units ██ ██ ██ ██████ ██████████ ██████████ ██████████ ██████████ ██████████ ██████████ ------------------------
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) }
- 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
BASIC
FreeBASIC
Uses Nigel Galloway's very elegant idea, expressed verbosely so you can really see what's going on.
type tower
hght as uinteger
posi as uinteger
end type
sub shellsort( a() as tower )
'quick and dirty shellsort, not the focus of this exercise
dim as uinteger gap = ubound(a), i, j, n=ubound(a)
dim as tower temp
do
gap = int(gap / 2.2)
if gap=0 then gap=1
for i=gap to n
temp = a(i)
j=i
while j>=gap andalso a(j-gap).hght < temp.hght
a(j) = a(j - gap)
j -= gap
wend
a(j) = temp
next i
loop until gap = 1
end sub
'heights of towers in each city prefixed by the number of towers
data 5, 1, 5, 3, 7, 2
data 10, 5, 3, 7, 2, 6, 4, 5, 9, 1, 2
data 16, 2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1
data 4, 5, 5, 5, 5
data 4, 5, 6, 7, 8
data 4, 8, 7, 7, 6
data 5, 6, 7, 10, 7, 6
dim as uinteger i, n, j, first, last, water
dim as tower manhattan(0 to 1)
for i = 1 to 7
read n
redim manhattan( 0 to n-1 )
for j = 0 to n-1
read manhattan(j).hght
manhattan(j).posi = j
next j
shellsort( manhattan() )
if manhattan(0).posi < manhattan(1).posi then
first = manhattan(0).posi
last = manhattan(1).posi
else
first = manhattan(1).posi
last = manhattan(0).posi
end if
water = manhattan(1).hght * (last-first-1)
for j = 2 to n-1
if first<manhattan(j).posi and manhattan(j).posi<last then water -= manhattan(j).hght
if manhattan(j).posi < first then
water += manhattan(j).hght * (first-manhattan(j).posi-1)
first = manhattan(j).posi
end if
if manhattan(j).posi > last then
water += manhattan(j).hght * (manhattan(j).posi-last-1)
last = manhattan(j).posi
end if
next j
print using "City configuration ## collected #### units of water."; i; water
next i
- Output:
City configuration 1 collected 2 units of water. City configuration 2 collected 14 units of water. City configuration 3 collected 35 units of water. City configuration 4 collected 0 units of water. City configuration 5 collected 0 units of water. City configuration 6 collected 0 units of water. City configuration 7 collected 0 units of water.
GW-BASIC
10 DEFINT A-Z: DIM T(20): K=0
20 K=K+1: READ N: IF N=0 THEN END
30 FOR I=0 TO N-1: READ T(I): NEXT
40 W=0
50 FOR R=N-1 TO 0 STEP -1: IF T(R)=0 THEN NEXT ELSE IF R=0 THEN 110
60 B=0
70 FOR C=0 TO R
80 IF T(C)>0 THEN T(C)=T(C)-1: B=B+1 ELSE IF B>0 THEN W=W+1
90 NEXT
100 IF B>1 THEN 50
110 PRINT "Block";K;"holds";W;"water units."
120 GOTO 20
130 DATA 5, 1,5,3,7,2
140 DATA 10, 5,3,7,2,6,4,5,9,1,2
150 DATA 16, 2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1
160 DATA 4, 5,5,5,5
170 DATA 4, 5,6,7,8
180 DATA 4, 8,7,7,6
190 DATA 5, 6,7,10,7,6
200 DATA 0
- Output:
Block 1 holds 2 water units. Block 2 holds 14 water units. Block 3 holds 35 water units. Block 4 holds 0 water units. Block 5 holds 0 water units. Block 6 holds 0 water units. Block 7 holds 0 water units.
Nascom BASIC
10 REM Water collected between towers
20 MXN=19
30 REM Heights of towers in each city
40 REM prefixed by the number of towers
50 DATA 5,1,5,3,7,2
60 DATA 10,5,3,7,2,6,4,5,9,1,2
70 DATA 16,2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1
80 DATA 4,5,5,5,5
90 DATA 4,5,6,7,8
100 DATA 4,8,7,7,6
110 DATA 5,6,7,10,7,6
120 DIM A(MXN,1)
130 FOR I=1 TO 7
140 READ N
150 FOR J=0 TO N-1
160 READ A(J,0)
170 A(J,1)=J
180 NEXT J
190 GOSUB 390
200 IF A(0,1)>=A(1,1) THEN 220
210 FRST=A(0,1):LST=A(1,1):GOTO 230
220 FRST=A(1,1):LST=A(0,1)
230 WTR=A(1,0)*(LST-FRST-1)
240 FOR J=2 TO N-1
250 IF FRST>=A(J,1) OR A(J,1)>=LST THEN 270
260 WTR=WTR-A(J,0)
270 IF A(J,1)>=FRST THEN 300
280 WTR=WTR+A(J,0)*(FRST-A(J,1)-1)
290 FRST=A(J,1)
300 IF A(J,1)<=LST THEN 330
310 WTR=WTR+A(J,0)*(A(J,1)-LST-1)
320 LST=A(J,1)
330 NEXT J
340 PRINT "Bar chart";I;"collected";
350 PRINT WTR;"units of water."
360 NEXT I
370 END
380 REM ** ShellSort
390 GAP=N-1
400 GAP=INT(GAP/2.2)
410 IF GAP=0 THEN GAP=1
420 FOR K=GAP TO N-1
430 TH=A(K,0):TP=A(K,1)
440 L=K
450 IF L<GAP THEN 500
460 IF A(L-GAP,0)>=TH THEN 500
470 A(L,0)=A(L-GAP,0):A(L,1)=A(L-GAP,1)
480 L=L-GAP
490 GOTO 450
500 A(L,0)=TH:A(L,1)=TP
510 NEXT K
520 IF GAP<>1 THEN 400
530 RETURN
- Output:
Bar chart 1 collected 2 units of water. Bar chart 2 collected 14 units of water. Bar chart 3 collected 35 units of water. Bar chart 4 collected 0 units of water. Bar chart 5 collected 0 units of water. Bar chart 6 collected 0 units of water. Bar chart 7 collected 0 units of water.
QuickBASIC
' Water collected between towers
DECLARE SUB ShellSort (A() AS ANY)
TYPE TTowerRec
Hght AS INTEGER
Posi AS INTEGER
END TYPE
'heights of towers in each city prefixed by the number of towers
DATA 5, 1, 5, 3, 7, 2
DATA 10, 5, 3, 7, 2, 6, 4, 5, 9, 1, 2
DATA 16, 2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1
DATA 4, 5, 5, 5, 5
DATA 4, 5, 6, 7, 8
DATA 4, 8, 7, 7, 6
DATA 5, 6, 7, 10, 7, 6
REM $DYNAMIC
DIM Manhattan(0 TO 1) AS TTowerRec
FOR I% = 1 TO 7
READ N%
ERASE Manhattan
REDIM Manhattan(0 TO N% - 1) AS TTowerRec
FOR J% = 0 TO N% - 1
READ Manhattan(J%).Hght
Manhattan(J%).Posi = J%
NEXT J%
ShellSort Manhattan()
IF Manhattan(0).Posi < Manhattan(1).Posi THEN
First% = Manhattan(0).Posi
Last% = Manhattan(1).Posi
ELSE
First% = Manhattan(1).Posi
Last% = Manhattan(0).Posi
END IF
Water% = Manhattan(1).Hght * (Last% - First% - 1)
FOR J% = 2 TO N% - 1
IF First% < Manhattan(J%).Posi AND Manhattan(J%).Posi < Last% THEN Water% = Water% - Manhattan(J%).Hght
IF Manhattan(J%).Posi < First% THEN
Water% = Water% + Manhattan(J%).Hght * (First% - Manhattan(J%).Posi - 1)
First% = Manhattan(J%).Posi
END IF
IF Manhattan(J%).Posi > Last% THEN
Water% = Water% + Manhattan(J%).Hght * (Manhattan(J%).Posi - Last% - 1)
Last% = Manhattan(J%).Posi
END IF
NEXT J%
PRINT USING "City configuration ## collected #### units of water."; I%; Water%
NEXT I%
END
REM $STATIC
SUB ShellSort (A() AS TTowerRec)
'quick and dirty shellsort, not the focus of this exercise
Gap% = UBOUND(A): N% = UBOUND(A)
DIM Temp AS TTowerRec
DO
Gap% = INT(Gap% / 2.2)
IF Gap% = 0 THEN Gap% = 1
FOR I% = Gap% TO N%
Temp = A(I%)
J% = I%
' Simulated WHILE J% >= Gap% ANDALSO A(J% - Gap%).Hght < Temp.Hght
DO
IF J% < Gap% THEN EXIT DO
IF A(J% - Gap%).Hght >= Temp.Hght THEN EXIT DO
A(J%) = A(J% - Gap%)
J% = J% - Gap%
LOOP
A(J%) = Temp
NEXT I%
LOOP UNTIL Gap% = 1
END SUB
- Output:
City configuration 1 collected 2 units of water. City configuration 2 collected 14 units of water. City configuration 3 collected 35 units of water. City configuration 4 collected 0 units of water. City configuration 5 collected 0 units of water. City configuration 6 collected 0 units of water. City configuration 7 collected 0 units of water.
uBasic/4tH
Dim @t(20)
k = FUNC (_getWater (1, 5, 3, 7, 2, 1))
k = FUNC (_getWater (5, 3, 7, 2, 6, 4, 5, 9, 1, 2, k))
k = FUNC (_getWater (2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1, k))
k = FUNC (_getWater (5, 5, 5, 5, k))
k = FUNC (_getWater (5, 6, 7, 8, k))
k = FUNC (_getWater (8, 7, 7, 6, k))
k = FUNC (_getWater (6, 7, 10, 7, 6, k))
End
_getWater
Param (1)
Local (2)
w = 0
c@ = Used()
For b@ = c@ - 1 To 0 Step -1
@t(b@) = Pop()
Next
Do While FUNC(_netWater (c@)) > 1 : Loop
Print "Block ";a@;" holds ";w;" water units."
Return (a@ + 1)
_netWater
Param (1)
Local (3)
For d@ = a@-1 To 0 Step -1
If @t(d@) Then
If d@ = 0 Then Unloop : Return (0) : fi
Else
Continue
EndIf
b@ = 0
For c@ = 0 To d@
If @t(c@) > 0 Then
@t(c@) = @t(c@) - 1
b@ = b@ + 1
Else
If b@ > 0 Then w = w + 1 : fi
EndIf
Next
Unloop : Return (b@)
Next
Return (0)
- Output:
Block 1 holds 2 water units. Block 2 holds 14 water units. Block 3 holds 35 water units. Block 4 holds 0 water units. Block 5 holds 0 water units. Block 6 holds 0 water units. Block 7 holds 0 water units. 0 OK, 0:409
Visual Basic .NET
Version 1
Method: Instead of "scanning" adjoining towers for each column, this routine converts the tower data into a string representation with building blocks, empty spaces, and potential water retention sites. The potential water retention sites are then "eroded" away where they are found to be unsupported. This is accomplished with the .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.
' Convert tower block data into a string representation, then manipulate that.
Module Module1
Sub Main(Args() As String)
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 = vbLf, ' Line feed to separate floors in a block of towers.
tb = "██", wr = "≈≈", mt = " " ' Tower Block, Water Retained, eMpTy space.
For i As Integer = 0 To wta.Length - 1
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 wta(i).Length - 1
If wta(i)(j) > 0 Then ' Tower block detected, add block to floor,
floor &= tb : wta(i)(j) -= 1 : bpf += 1 ' reduce tower by one.
Else ' Empty space detected, fill when not first or last column.
floor &= If(j > 0 AndAlso j < wta(i).Length - 1, wr, mt)
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.
' Erode potential water retention cells from left and right.
While blk.Contains(mt & wr) : blk = blk.Replace(mt & wr, mt & mt) : End While
While blk.Contains(wr & mt) : blk = blk.Replace(wr & mt, mt & mt) : End While
' Optionaly show towers w/ water marks.
If shoTow Then Console.Write("{0}{1}", lf, blk)
' Subtract the amount of non-water mark characters from the total char amount.
Console.Write("Block {0} retains {1,2} water units.{2}", i + 1,
(blk.Length - blk.Replace(wr, "").Length) \ 2, lf)
Next
End Sub
End Module
- Output:
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.
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.
██
██
██≈≈██
██≈≈██
██████
████████
██████████
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.
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.
Module Module1
''' <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
End Module
Regular version 2 output:
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.
Sample of version 2 verbose output:
██
██≈≈≈≈≈≈≈≈≈≈≈≈≈≈██
██≈≈≈≈≈≈██≈≈≈≈≈≈≈≈≈≈≈≈≈≈██
██≈≈██≈≈██≈≈≈≈≈≈≈≈██≈≈████
██≈≈██≈≈██≈≈██≈≈≈≈██≈≈██████
██████≈≈██≈≈██≈≈≈≈██████████
████████████≈≈████████████████
████████████████████████████████ Block 3 holds 35 water units.
████████
████████
████████
████████
████████ Block 4 does not hold any water units.
Yabasic
data 7
data "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"
data "5,5,5,5", "5,6,7,8", "8,7,7,6", "6,7,10,7,6"
read n
for i = 1 to n
read n$
wcbt(n$)
next i
sub wcbt(s$)
local tower$(1), hr(1), hl(1), n, i, ans, k
n = token(s$, tower$(), ",")
redim hr(n)
redim hl(n)
for i = n to 1 step -1
if i < n then
k = hr(i + 1)
else
k = 0
end if
hr(i) = max(val(tower$(i)), k)
next i
for i = 1 to n
if i then
k = hl(i - 1)
else
k = 0
end if
hl(i) = max(val(tower$(i)), k)
ans = ans + min(hl(i), hr(i)) - val(tower$(i))
next i
print ans," ",n$
end sub
C
Takes the integers as input from command line, prints out usage on incorrect invocation.
#include<stdlib.h>
#include<stdio.h>
int getWater(int* arr,int start,int end,int cutoff){
int i, sum = 0;
for(i=start;i<=end;i++)
sum += ((arr[cutoff] > arr[i])?(arr[cutoff] - arr[i]):0);
return sum;
}
int netWater(int* arr,int size){
int i, j, ref1, ref2, marker, markerSet = 0,sum = 0;
if(size<3)
return 0;
for(i=0;i<size-1;i++){
start:if(i!=size-2 && arr[i]>arr[i+1]){
ref1 = i;
for(j=ref1+1;j<size;j++){
if(arr[j]>=arr[ref1]){
ref2 = j;
sum += getWater(arr,ref1+1,ref2-1,ref1);
i = ref2;
goto start;
}
else if(j!=size-1 && arr[j] < arr[j+1] && (markerSet==0||(arr[j+1]>=arr[marker]))){
marker = j+1;
markerSet = 1;
}
}
if(markerSet==1){
sum += getWater(arr,ref1+1,marker-1,marker);
i = marker;
markerSet = 0;
goto start;
}
}
}
return sum;
}
int main(int argC,char* argV[])
{
int *arr,i;
if(argC==1)
printf("Usage : %s <followed by space separated series of integers>");
else{
arr = (int*)malloc((argC-1)*sizeof(int));
for(i=1;i<argC;i++)
arr[i-1] = atoi(argV[i]);
printf("Water collected : %d",netWater(arr,argC-1));
}
return 0;
}
Output :
C:\rosettaCode>waterTowers.exe 1 5 3 7 2 Water collected : 2 C:\rosettaCode>waterTowers.exe 5 3 7 2 6 4 5 9 1 2 Water collected : 14 C:\rosettaCode>waterTowers.exe 2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1 Water collected : 35 C:\rosettaCode>waterTowers.exe 5 5 5 5 Water collected : 0 C:\rosettaCode>waterTowers.exe 8 7 7 6 Water collected : 0 C:\rosettaCode>waterTowers.exe 6 7 10 7 6 Water collected : 0
C#
Version 1
Translation from Visual Basic .NET. See that version 1 entry for code comment details and more sample output.
class Program
{
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", tb = "██", wr = "≈≈", mt = " ";
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 += tb; wta[i][j] -= 1; bpf += 1; }
else floor += (j > 0 && j < wta[i].Length - 1 ? wr : mt);
}
if (bpf > 0) blk = floor + lf + blk;
} while (bpf > 0);
while (blk.Contains(mt + wr)) blk = blk.Replace(mt + wr, mt + mt);
while (blk.Contains(wr + mt)) blk = blk.Replace(wr + mt, mt + mt);
if (args.Length > 0) System.Console.Write("\n{0}", blk);
System.Console.WriteLine("Block {0} retains {1,2} water units.",
i + 1, (blk.Length - blk.Replace(wr, "").Length) / 2);
}
}
}
- Output:
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.
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.
class Program
{
// 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 (int[] 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()));
}
}
}
Output:
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.
C++
#include <iostream>
#include <vector>
#include <algorithm>
enum { EMPTY, WALL, WATER };
auto fill(const std::vector<int> b) {
auto water = 0;
const auto rows = *std::max_element(std::begin(b), std::end(b));
const auto cols = std::size(b);
std::vector<std::vector<int>> g(rows);
for (auto& r : g) {
for (auto i = 0; i < cols; ++i) {
r.push_back(EMPTY);
}
}
for (auto c = 0; c < cols; ++c) {
for (auto r = rows - 1u, i = 0u; i < b[c]; ++i, --r) {
g[r][c] = WALL;
}
}
for (auto c = 0; c < cols - 1; ++c) {
auto start_row = rows - b[c];
while (start_row < rows) {
if (g[start_row][c] == EMPTY) break;
auto c2 = c + 1;
bool hitWall = false;
while (c2 < cols) {
if (g[start_row][c2] == WALL) {
hitWall = true;
break;
}
++c2;
}
if (hitWall) {
for (auto i = c + 1; i < c2; ++i) {
g[start_row][i] = WATER;
++water;
}
}
++start_row;
}
}
return water;
}
int main() {
std::vector<std::vector<int>> b = {
{ 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 }
};
for (const auto v : b) {
auto water = fill(v);
std::cout << water << " water drops." << std::endl;
}
std::cin.ignore();
std::cin.get();
return 0;
}
- Output:
2 water drops. 14 water drops. 35 water drops. 0 water drops. 0 water drops. 0 water drops. 0 water drops.
Clojure
Similar two passes algorithm as many solutions here. First traverse left to right to find the highest tower on the left of each position, inclusive of the tower at the current position, than do the same to find the highest tower to the right of each position. Finally, compute the total water units held at any position as the difference of those two heights.
(defn trapped-water [towers]
(let [maxes #(reductions max %) ; the seq of increasing max values found in the input seq
maxl (maxes towers) ; the seq of max heights to the left of each tower
maxr (reverse (maxes (reverse towers))) ; the seq of max heights to the right of each tower
mins (map min maxl maxr)] ; minimum highest surrounding tower per position
(reduce + (map - mins towers)))) ; sum up the trapped water per position
- Output:
;; in the following, # is a tower block and ~ is trapped water:
;;
;; 10|
;; 9| #
;; 8| #
;; 7| # ~ ~ ~ ~ #
;; 6| # ~ # ~ ~ #
;; 5| # ~ # ~ # ~ # #
;; 4| # ~ # ~ # # # #
;; 3| # # # ~ # # # #
;; 2| # # # # # # # # ~ #
;; 1| # # # # # # # # # #
;; ---+---------------------
;; 5 3 7 2 6 4 5 9 1 2
(trapped-water [5 3 7 2 6 4 5 9 1 2]) ;; 14
CLU
max = proc [T: type] (a,b: T) returns (T)
where T has lt: proctype (T,T) returns (bool)
if a<b then return(b)
else return(a)
end
end max
% based on: https://stackoverflow.com/a/42821623
water = proc (towers: sequence[int]) returns (int)
si = sequence[int]
w: int := 0
left: int := 1
right: int := si$size(towers)
max_left: int := si$bottom(towers)
max_right: int := si$top(towers)
while left <= right do
if towers[left] <= towers[right] then
max_left := max[int](towers[left], max_left)
w := w + max[int](max_left - towers[left], 0)
left := left + 1
else
max_right := max[int](towers[right], max_right)
w := w + max[int](max_right - towers[right], 0)
right := right - 1
end
end
return(w)
end water
start_up = proc ()
si = sequence[int]
ssi = sequence[si]
po: stream := stream$primary_output()
tests: ssi := ssi$[
si$[1, 5, 3, 7, 2],
si$[5, 3, 7, 2, 6, 4, 5, 9, 1, 2],
si$[2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1],
si$[5, 5, 5, 5],
si$[5, 6, 7, 8],
si$[8, 7, 7, 6],
si$[6, 7, 10, 7, 6]
]
for test: si in ssi$elements(tests) do
stream$puts(po, int$unparse(water(test)) || " ")
end
end start_up
- Output:
2 14 35 0 0 0 0
Cowgol
include "cowgol.coh";
include "argv.coh";
# Count the amount of water in a given array
sub water(towers: [uint8], length: intptr): (units: uint8) is
units := 0;
loop
var right := towers + length;
loop
right := @prev right;
if right < towers or [right] != 0 then
break;
end if;
end loop;
if right < towers then break; end if;
var blocks: uint8 := 0;
var col := towers;
while col <= right loop
if [col] != 0 then
[col] := [col] - 1;
blocks := blocks + 1;
elseif blocks != 0 then
units := units + 1;
end if;
col := @next col;
end loop;
if blocks < 2 then
break;
end if;
end loop;
end sub;
# Read list from the command line and print the answer
ArgvInit();
var towers: uint8[256];
var count: @indexof towers := 0;
var n32: int32;
loop
var argmt := ArgvNext();
if argmt == 0 as [uint8] then
break;
end if;
(n32, argmt) := AToI(argmt);
towers[count] := n32 as uint8;
count := count + 1;
end loop;
if count == 0 then
print("enter towers on command line\n");
ExitWithError();
end if;
print_i8(water(&towers[0], count as intptr));
print_nl();
- Output:
$ ./water.386 1 5 3 7 2 2 $ ./water.386 5 3 7 2 6 4 5 9 1 2 14 $ ./water.386 2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1 35 $ ./water.386 5 5 5 5 0 $ ./water.386 5 6 7 8 0 $ ./water.386 8 7 7 6 0 $ ./water.386 6 7 10 7 6 0
D
import std.stdio;
void main() {
int i = 1;
int[][] tba = [
[ 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 ]
];
foreach (tea; tba) {
int rht, wu, 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);
write("Block ", i++);
if (wu == 0) {
write(" does not hold any");
} else {
write(" holds ", wu);
}
writeln(" water units.");
}
}
- Output:
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.
Delphi
The program builds a matrix of the towers and scans each line looking for pairs of towers that trap water.
var Towers1: array [0..4] of integer = (1, 5, 3, 7, 2);
var Towers2: array [0..9] of integer = (5, 3, 7, 2, 6, 4, 5, 9, 1, 2);
var Towers3: array [0..15] of integer = (2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1);
var Towers4: array [0..3] of integer = (5, 5, 5, 5);
var Towers5: array [0..3] of integer = (5, 6, 7, 8);
var Towers6: array [0..3] of integer = (8, 7, 7, 6);
var Towers7: array [0..4] of integer = (6, 7, 10, 7, 6);
type TMatrix = array of array of boolean;
function ArrayToMatrix(Towers: array of integer): TMatrix;
{Convert Tower Array to Matrix for analysis}
var Max,I,X,Y: integer;
begin
Max:=0;
for I:=0 to High(Towers) do if Towers[I]>=Max then Max:=Towers[I];
SetLength(Result,Length(Towers),Max);
for Y:=0 to High(Result[0]) do
for X:=0 to High(Result) do Result[X,Y]:=Towers[X]>(Max-Y);
end;
procedure DisplayMatrix(Memo: TMemo; Matrix: TMatrix);
{Display a matrix}
var X,Y: integer;
var S: string;
begin
for Y:=0 to High(Matrix[0]) do
begin
S:='[';
for X:=0 to High(Matrix) do
begin
if Matrix[X,Y] then S:=S+'#'
else S:=S+' ';
end;
S:=S+']';
Memo.Lines.Add(S);
end;
end;
function GetWaterStorage(Matrix: TMatrix): integer;
{Analyze matrix to get water storage amount}
var X,Y,Cnt: integer;
var Inside: boolean;
begin
Result:=0;
{Scan each row of matrix to see if it is storing water}
for Y:=0 to High(Matrix[0]) do
begin
Inside:=False;
Cnt:=0;
for X:=0 to High(Matrix) do
begin
{Test if this is a tower}
if Matrix[X,Y] then
begin
{if so, we may be inside trough}
Inside:=True;
{If Cnt>0 there was a previous tower}
{And we've impounded water }
Result:=Result+Cnt;
{Start new count with new tower}
Cnt:=0;
end
else if Inside then Inc(Cnt); {Count potential impounded water}
end;
end;
end;
procedure ShowWaterLevels(Memo: TMemo; Towers: array of integer);
{Analyze the water storage of towers and display result}
var Water: integer;
var Matrix: TMatrix;
begin
Matrix:=ArrayToMatrix(Towers);
DisplayMatrix(Memo,Matrix);
Water:=GetWaterStorage(Matrix);
Memo.Lines.Add('Storage: '+IntToStr(Water)+CRLF);
end;
procedure WaterLevel(Memo: TMemo);
begin
ShowWaterLevels(Memo,Towers1);
ShowWaterLevels(Memo,Towers2);
ShowWaterLevels(Memo,Towers3);
ShowWaterLevels(Memo,Towers4);
ShowWaterLevels(Memo,Towers5);
ShowWaterLevels(Memo,Towers6);
ShowWaterLevels(Memo,Towers7);
end;
- Output:
[ ] [ # ] [ # ] [ # # ] [ # # ] [ ### ] [ ####] Storage: 2 [ ] [ # ] [ # ] [ # # ] [ # # # ] [# # # ## ] [# # #### ] [### #### ] [######## #] Storage: 14 [ ] [ # ] [ # # ] [ # # # ] [ # # # # ## ] [ # # # # # ### ] [ ### # # ##### ] [###### ######## ] Storage: 35 [ ] [####] [####] [####] [####] Storage: 0 [ ] [ #] [ ##] [ ###] [####] [####] [####] [####] Storage: 0 [ ] [# ] [### ] [####] [####] [####] [####] [####] Storage: 0 [ ] [ # ] [ # ] [ # ] [ ### ] [#####] [#####] [#####] [#####] [#####] Storage: 0 Elapsed Time: 171.444 ms.
EasyLang
proc water h[] . .
n = len h[]
len left[] n
len right[] n
for i = 1 to n
max = higher max h[i]
left[i] = max
.
max = 0
for i = n downto 1
max = higher max h[i]
right[i] = max
.
for i = 1 to n
sum += (lower left[i] right[i]) - h[i]
.
print sum
.
repeat
s$ = input
until s$ = ""
water number strsplit s$ " "
.
#
input_data
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
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.
-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.
- 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.
(*
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))
- 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
Factor
USING: formatting kernel math.statistics math.vectors sequences ;
: area ( seq -- n )
[ cum-max ] [ <reversed> cum-max reverse vmin ] [ v- sum ] tri ;
{
{ 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 }
} [ dup area "%[%d, %] -> %d\n" printf ] each
- 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
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}))
}
- Output:
2 14 35 0 0 0 0
Groovy
Integer waterBetweenTowers(List<Integer> towers) {
// iterate over the vertical axis. There the amount of water each row can hold is
// the number of empty spots, minus the empty spots at the beginning and end
return (1..towers.max()).collect { height ->
// create a string representing the row, '#' for tower material and ' ' for air
// use .trim() to remove spaces at beginning and end and then count remaining spaces
towers.collect({ it >= height ? "#" : " " }).join("").trim().count(" ")
}.sum()
}
tasks = [
[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]
]
tasks.each {
println "$it => total water: ${waterBetweenTowers it}"
}
- Output:
[1, 5, 3, 7, 2] => total water: 2 [5, 3, 7, 2, 6, 4, 5, 9, 1, 2] => total water: 14 [2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1] => total water: 35 [5, 5, 5, 5] => total water: 0 [5, 6, 7, 8] => total water: 0 [8, 7, 7, 6] => total water: 0 [6, 7, 10, 7, 6] => total water: 0
Haskell
Following the approach of slightly modified cdk's Haskell solution at Stack Overflow. As recommended in Programming as if the Correct Data Structure (and Performance) Mattered it uses Vector instead of Array:
import Data.Vector.Unboxed (Vector)
import qualified Data.Vector.Unboxed as V
waterCollected :: Vector Int -> Int
waterCollected =
V.sum . -- Sum of the water depths over each of
V.filter (> 0) . -- the columns that are covered by some water.
(V.zipWith (-) =<< -- Where coverages are differences between:
(V.zipWith min . -- the lower water level in each case of:
V.scanl1 max <*> -- highest wall to left, and
V.scanr1 max)) -- highest wall to right.
main :: IO ()
main =
mapM_
(print . waterCollected . V.fromList)
[ [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]
]
- Output:
2 14 35 0 0 0 0
Or, using Data.List for simplicity - no need to prioritize performance here - and adding diagrams:
import Data.List (replicate, transpose)
-------------- WATER COLLECTED BETWEEN TOWERS ------------
towerPools :: [Int] -> [(Int, Int)]
towerPools =
zipWith min . scanl1 max <*> scanr1 max
>>= zipWith ((<*>) (,) . (-))
--------------------------- TEST -------------------------
main :: IO ()
main =
mapM_
(putStrLn . display . towerPools)
[ [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]
]
------------------------- DIAGRAMS -----------------------
display :: [(Int, Int)] -> String
display = (<>) . showTowers <*> (('\n' :) . showLegend)
showTowers :: [(Int, Int)] -> String
showTowers xs =
let upper = maximum (fst <$> xs)
in '\n' :
( unlines
. transpose
. fmap
( \(x, d) ->
concat $
replicate (upper - (x + d)) " "
<> replicate d "x"
<> replicate x "█"
)
)
xs
showLegend :: [(Int, Int)] -> String
showLegend =
((<>) . show . fmap fst)
<*> ((" -> " <>) . show . foldr ((+) . snd) 0)
- Output:
█ █ █x█ █x█ ███ ████ █████ [1,5,3,7,2] -> 2 █ █ █xxxx█ █x█xx█ █x█x█x██ █x█x████ ███x████ ████████x█ ██████████ [5,3,7,2,6,4,5,9,1,2] -> 14 █ █xxxxxxx█ █xxx█xxxxxxx█ █x█x█xxxx█x██ █x█x█x█xx█x███ ███x█x█xx█████ ██████x████████ ████████████████ [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
J
Inspired by #Julia.
Solution:
collectLevels =: >./\ <. >./\. NB. collect levels after filling
waterLevels=: collectLevels - ] NB. water levels for each tower
collectedWater=: +/@waterLevels NB. sum the units of water collected
printTowers =: ' ' , [: |.@|: '#~' #~ ] ,. waterLevels NB. print a nice graph of towers and water
Examples:
collectedWater 5 3 7 2 6 4 5 9 1 2
14
printTowers 5 3 7 2 6 4 5 9 1 2
#
#
#~~~~#
#~#~~#
#~#~#~##
#~#~####
###~####
########~#
##########
NB. Test cases
TestTowers =: <@".;._2 noun define
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
)
TestResults =: 2 14 35 0 0 0 0
TestResults -: collectedWater &> TestTowers NB. check tests
1
Java
public class WaterBetweenTowers {
public static void main(String[] args) {
int i = 1;
int[][] tba = new int[][]{
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}
};
for (int[] tea : 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]--;
bof += 1;
} else if (bof > 0) {
wu++;
}
}
if (bof < 2) {
break;
}
} while (true);
System.out.printf("Block %d", i++);
if (wu == 0) {
System.out.print(" does not hold any");
} else {
System.out.printf(" holds %d", wu);
}
System.out.println(" water units.");
}
}
}
- Output:
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.
JavaScript
ES5
(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]
})();
- Output:
[2, 14, 35, 0, 0, 0, 0]
ES6
(() => {
"use strict";
// --------- WATER COLLECTED BETWEEN TOWERS ----------
// waterCollected :: [Int] -> Int
const waterCollected = xs =>
sum(filter(lt(0))(
zipWith(subtract)(xs)(
zipWith(min)(
scanl1(max)(xs)
)(
scanr1(max)(xs)
)
)
));
// ---------------------- TEST -----------------------
const main = () => [
[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);
// --------------------- GENERIC ---------------------
// Tuple (,) :: a -> b -> (a, b)
const Tuple = a =>
b => ({
type: "Tuple",
"0": a,
"1": b,
length: 2
});
// filter :: (a -> Bool) -> [a] -> [a]
const filter = p =>
// The elements of xs which match
// the predicate p.
xs => [...xs].filter(p);
// lt (<) :: Ord a => a -> a -> Bool
const lt = a =>
b => a < b;
// max :: Ord a => a -> a -> a
const max = a =>
// b if its greater than a,
// otherwise a.
b => a > b ? a : b;
// min :: Ord a => a -> a -> a
const min = a =>
b => b < a ? b : a;
// scanl :: (b -> a -> b) -> b -> [a] -> [b]
const scanl = f => startValue => xs =>
xs.reduce((a, x) => {
const v = f(a[0])(x);
return Tuple(v)(a[1].concat(v));
}, Tuple(startValue)([startValue]))[1];
// scanl1 :: (a -> a -> a) -> [a] -> [a]
const scanl1 = f =>
// scanl1 is a variant of scanl that
// has no starting value argument.
xs => xs.length > 0 ? (
scanl(f)(
xs[0]
)(xs.slice(1))
) : [];
// scanr :: (a -> b -> b) -> b -> [a] -> [b]
const scanr = f =>
startValue => xs => xs.reduceRight(
(a, x) => {
const v = f(x)(a[0]);
return Tuple(v)([v].concat(a[1]));
}, Tuple(startValue)([startValue])
)[1];
// scanr1 :: (a -> a -> a) -> [a] -> [a]
const scanr1 = f =>
// scanr1 is a variant of scanr that has no
// seed-value argument, and assumes that
// xs is not empty.
xs => xs.length > 0 ? (
scanr(f)(
xs.slice(-1)[0]
)(xs.slice(0, -1))
) : [];
// subtract :: Num -> Num -> Num
const subtract = x =>
y => y - x;
// sum :: [Num] -> Num
const sum = xs =>
// The numeric sum of all values in xs.
xs.reduce((a, x) => a + x, 0);
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f =>
// A list constructed by zipping with a
// custom function, rather than with the
// default tuple constructor.
xs => ys => xs.map(
(x, i) => f(x)(ys[i])
).slice(
0, Math.min(xs.length, ys.length)
);
// MAIN ---
return main();
})();
- Output:
[2, 14, 35, 0, 0, 0, 0]
jq
Works with gojq, the Go implementation of jq
def waterCollected:
. as $tower
| ($tower|length) as $n
| ([0] + [range(1;$n) | ($tower[0:.] | max) ]) as $highLeft
| ( [range(1;$n) | ($tower[.:$n] | max) ] + [0]) as $highRight
| [ range(0;$n) | [ ([$highLeft[.], $highRight[.] ]| min) - $tower[.], 0 ] | max]
| add ;
def 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]
];
towers[]
| "\(waterCollected) from \(.)"
- Output:
As for #Kotlin and others.
Julia
Inspired to #Python.
using Printf
function watercollected(towers::Vector{Int})
high_lft = vcat(0, accumulate(max, towers[1:end-1]))
high_rgt = vcat(reverse(accumulate(max, towers[end:-1:2])), 0)
waterlvl = max.(min.(high_lft, high_rgt) .- towers, 0)
return waterlvl
end
function towerprint(towers, levels)
ctowers = copy(towers)
clevels = copy(levels)
hmax = maximum(towers)
ntow = length(towers)
for h in hmax:-1:1
@printf("%2i |", h)
for j in 1:ntow
if ctowers[j] + clevels[j] ≥ h
if clevels[j] > 0
cell = "≈≈"
clevels[j] -= 1
else
cell = "NN"
ctowers[j] -= 1
end
else
cell = " "
end
print(cell)
end
println("|")
end
println(" " * join(lpad(t, 2) for t in levels) * ": Water lvl")
println(" " * join(lpad(t, 2) for t in towers) * ": Tower lvl")
end
for towers in [[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]]
towerprint(towers, watercollected(towers))
println()
end
- Output:
7 | NN | 6 | NN | 5 | NN≈≈NN | 4 | NN≈≈NN | 3 | NNNNNN | 2 | NNNNNNNN| 1 |NNNNNNNNNN| 0 0 2 0 0: Water lvl 1 5 3 7 2: Tower lvl 9 | NN | 8 | NN | 7 | NN≈≈≈≈≈≈≈≈NN | 6 | NN≈≈NN≈≈≈≈NN | 5 |NN≈≈NN≈≈NN≈≈NNNN | 4 |NN≈≈NN≈≈NNNNNNNN | 3 |NNNNNN≈≈NNNNNNNN | 2 |NNNNNNNNNNNNNNNN≈≈NN| 1 |NNNNNNNNNNNNNNNNNNNN| 0 2 0 5 1 3 2 0 1 0: Water lvl 5 3 7 2 6 4 5 9 1 2: Tower lvl 8 | NN | 7 | NN≈≈≈≈≈≈≈≈≈≈≈≈≈≈NN | 6 | NN≈≈≈≈≈≈NN≈≈≈≈≈≈≈≈≈≈≈≈≈≈NN | 5 | NN≈≈NN≈≈NN≈≈≈≈≈≈≈≈NN≈≈NNNN | 4 | NN≈≈NN≈≈NN≈≈NN≈≈≈≈NN≈≈NNNNNN | 3 | NNNNNN≈≈NN≈≈NN≈≈≈≈NNNNNNNNNN | 2 |NNNNNNNNNNNN≈≈NNNNNNNNNNNNNNNN | 1 |NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN| 0 0 3 1 4 0 6 3 5 5 2 4 2 0 0 0: Water lvl 2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1: Tower lvl 5 |NNNNNNNN| 4 |NNNNNNNN| 3 |NNNNNNNN| 2 |NNNNNNNN| 1 |NNNNNNNN| 0 0 0 0: Water lvl 5 5 5 5: Tower lvl 8 | NN| 7 | NNNN| 6 | NNNNNN| 5 |NNNNNNNN| 4 |NNNNNNNN| 3 |NNNNNNNN| 2 |NNNNNNNN| 1 |NNNNNNNN| 0 0 0 0: Water lvl 5 6 7 8: Tower lvl 8 |NN | 7 |NNNNNN | 6 |NNNNNNNN| 5 |NNNNNNNN| 4 |NNNNNNNN| 3 |NNNNNNNN| 2 |NNNNNNNN| 1 |NNNNNNNN| 0 0 0 0: Water lvl 8 7 7 6: Tower lvl 10 | NN | 9 | NN | 8 | NN | 7 | NNNNNN | 6 |NNNNNNNNNN| 5 |NNNNNNNNNN| 4 |NNNNNNNNNN| 3 |NNNNNNNNNN| 2 |NNNNNNNNNN| 1 |NNNNNNNNNN| 0 0 0 0 0: Water lvl 6 710 7 6: Tower lvl
Kotlin
// 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()}")
}
}
- 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]
Lua
function waterCollected(i,tower)
local length = 0
for _ in pairs(tower) do
length = length + 1
end
local wu = 0
repeat
local rht = length - 1
while rht >= 0 do
if tower[rht + 1] > 0 then
break
end
rht = rht - 1
end
if rht < 0 then
break
end
local bof = 0
local col = 0
while col <= rht do
if tower[col + 1] > 0 then
tower[col + 1] = tower[col + 1] - 1
bof = bof + 1
elseif bof > 0 then
wu = wu + 1
end
col = col + 1
end
if bof < 2 then
break
end
until false
if wu == 0 then
print(string.format("Block %d does not hold any water.", i))
else
print(string.format("Block %d holds %d water units.", i, wu))
end
end
function main()
local 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}
}
for i,tbl in pairs(towers) do
waterCollected(i,tbl)
end
end
main()
- Output:
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. Block 5 does not hold any water. Block 6 does not hold any water. Block 7 does not hold any water.
M2000 Interpreter
Scan min-max for each bar
Module Water {
Flush ' empty stack
Data (1, 5, 3, 7, 2)
Data (5, 3, 7, 2, 6, 4, 5, 9, 1, 2)
Data (2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1)
Data (5, 5, 5, 5), (5, 6, 7, 8),(8, 7, 7, 6)
Data (6, 7, 10, 7, 6)
bars=stack.size ' mark stack frame
Dim bar()
for bar=1 to bars
bar()=Array ' pop an array from stack
acc=0
For i=1 to len(bar())-2
level1=bar(i)
level2=level1
m=each(bar(), i+1, 1)
while m
if array(m)>level1 then level1=array(m)
End While
n=each(bar(), i+1, -1)
while n
if array(n)>level2 then level2=array(n)
End While
acc+=max.data(min(level1, level2)-bar(i), 0)
Next i
Data acc ' push to end value
Next bar
finalwater=[] ' is a stack object
Print finalwater
}
Water
Drain method
Module Water2 {
Flush ' empty stack Data (1, 5, 3, 7, 2) Data (5, 3, 7, 2, 6, 4, 5, 9, 1, 2) Data (2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1) Data (5, 5, 5, 5), (5, 6, 7, 8),(8, 7, 7, 6) Data (6, 7, 10, 7, 6) bars=stack.size ' mark stack frame Dim bar() For bar=1 to bars bar()=Array ' pop an array from stack acc=0 range=bar()#max()-bar()#min() if range>0 then dim water(len(bar()))=bar()#max() water(0)=bar(0) water(len(bar())-1)=bar(len(bar())-1) For j=1 to range-1 For i=1 to len(bar())-2 if water(i)>bar(i) then if water(i-1)<water(i) Then water(i)-- Next i For i=len(bar())-2 to 1 if water(i)>bar(i) then if water(i+1)<water(i) Then water(i)-- Next i Next j Data water()#sum()-bar()#sum() Else Data 0 End if Next bar finalwater=[] Print finalwater
} Water2
Faster Method
Module Water3 {
Flush ' empty stack
Data (1, 5, 3, 7, 2)
Data (5, 3, 7, 2, 6, 4, 5, 9, 1, 2)
Data (2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1)
Data (5, 5, 5, 5), (5, 6, 7, 8),(8, 7, 7, 6)
Data (6, 7, 10, 7, 6)
bars=stack.size ' mark stack frame
Dim bar()
for bar=1 to bars
bar()=Array ' pop an array from stack
acc=0
n=len(bar())-1
dim hl(n+1), hr(n+1)
For i=n to 0
hr(i)=max.data(bar(i), if(i<n->hr(i+1), 0))
Next i
For i=0 to n
hl(i)=max.data(bar(i), if(i>0->hl(i-1), 0))
acc+=min.data(hl(i), hr(i))-bar(i)
Next i
Data acc ' push to end value
Next bar
finalwater=[] ' is a stack object
Print finalwater
}
Water3
- Output:
2 14 35 0 0 0 0
Mathematica / Wolfram Language
ClearAll[waterbetween]
waterbetween[h_List] := Module[{mi, ma, ch},
{mi, ma} = MinMax[h];
Sum[
ch = h - i;
Count[
Flatten@
Position[
ch, _?Negative], _?(Between[
MinMax[Position[ch, _?NonNegative]]])]
,
{i, mi + 1, ma}
]
]
h = {{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}};
waterbetween /@ h
- Output:
{2, 14, 35, 0, 0, 0, 0}
Nim
import math, sequtils, sugar
proc water(barChart: seq[int], isLeftPeak = false, isRightPeak = false): int =
if len(barChart) <= 2:
return
if isLeftPeak and isRightPeak:
return sum(barChart[1..^2].map(x=>min(barChart[0], barChart[^1])-x))
var i: int
if isLeftPeak:
i = maxIndex(barChart[1..^1])+1
else:
i = maxIndex(barChart[0..^2])
return water(barChart[0..i], isLeftPeak, true)+water(barChart[i..^1], true, isRightPeak)
const barCharts = [
@[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]]
const waterUnits = barCharts.map(chart=>water(chart, false, false))
echo(waterUnits)
- Output:
@[2, 14, 35, 0, 0, 0, 0]
Pascal
program RainInFlatland;
{$IFDEF FPC} // Free Pascal
{$MODE Delphi}
{$ELSE} // Delphi
{$APPTYPE CONSOLE}
{$ENDIF}
uses SysUtils;
type THeight = integer;
// Heights could be f.p., but some changes to the code would be needed:
// (1) the inc function isn't available for f.p. values,
// (2) the print-out would need extra formatting.
{------------------------------------------------------------------------------
Find highest tower; if there are 2 or more equal highest, choose any.
Then fill troughs so that on going towards the highest tower, from the
left-hand or right-hand end, there are no steps down.
Amount of filling required equals amount of water collected.
}
function FillTroughs( const h : array of THeight) : THeight;
var
m, i, i_max : integer;
h_max : THeight;
begin
result := 0;
m := High( h); // highest index, 0-based; there are m + 1 towers
if (m <= 1) then exit; // result = 0 if <= 2 towers
// Find highest tower and its index in the array.
h_max := h[0];
i_max := 0;
for i := 1 to m do begin
if h[i] > h_max then begin
h_max := h[i];
i_max := i;
end;
end;
// Fill troughs from left-hand end to highest tower
h_max := h[0];
for i := 1 to i_max - 1 do begin
if h[i] < h_max then inc( result, h_max - h[i])
else h_max := h[i];
end;
// Fill troughs from right-hand end to highest tower
h_max := h[m];
for i := m - 1 downto i_max + 1 do begin
if h[i] < h_max then inc( result, h_max - h[i])
else h_max := h[i];
end;
end;
{-------------------------------------------------------------------------
Wrapper for the above: finds amount of water, and prints input and result.
}
procedure CalcAndPrint( h : array of THeight);
var
water : THeight;
j : integer;
begin
water := FillTroughs( h);
Write( water:5, ' <-- [');
for j := 0 to High( h) do begin
Write( h[j]);
if j < High(h) then Write(', ') else WriteLn(']');
end;
end;
{---------------------------------------------------------------------------
Main routine.
}
begin
CalcAndPrint([1,5,3,7,2]);
CalcAndPrint([5,3,7,2,6,4,5,9,1,2]);
CalcAndPrint([2,6,3,5,2,8,1,4,2,2,5,3,5,7,4,1]);
CalcAndPrint([5,5,5,5]);
CalcAndPrint([5,6,7,8]);
CalcAndPrint([8,7,7,6]);
CalcAndPrint([6,7,10,7,6]);
end.
- 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]
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 ],
);
- Output:
2 14 35 0 0 0 0
Phix
inefficient one-pass method
with javascript_semantics function collect_water(sequence heights) integer res = 0 for i=2 to length(heights)-1 do integer lm = max(heights[1..i-1]), rm = max(heights[i+1..$]), d = min(lm,rm)-heights[i] res += max(0,d) end for return res end function constant tests = {{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}} for i=1 to length(tests) do sequence ti = tests[i] printf(1,"%35s : %d\n",{sprint(ti),collect_water(ti)}) end for
- 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
more efficient two-pass version
with javascript_semantics function collect_water(sequence heights) integer left_max = heights[1], right_max = heights[$] sequence left_height = deep_copy(heights), right_height = deep_copy(heights) for i=2 to length(heights)-1 do left_max = max(heights[i],left_max) left_height[i] = left_max right_max = max(heights[-i],right_max) right_height[-i] = right_max end for sequence mins = sq_min(left_height,right_height), diffs = sq_sub(mins,heights) return sum(diffs) end function
(same output)
pretty print routine
with javascript_semantics requires("1.0.2") -- (bugfix in p2js.js/$sidii(), 20/4/22) procedure print_water(sequence heights) integer res = 0, l = length(heights) sequence towers = repeat(repeat(' ',l),max(heights)) for i=1 to l do for j=1 to heights[i] do towers[-j][i] = '#' end for if i>1 and i<l then integer lm = max(heights[1..i-1]), rm = max(heights[i+1..$]), m = min(lm,rm) for j=heights[i]+1 to m do towers[-j][i] = '~' res += 1 end for end if end for printf(1,"%s\ncollected:%d\n",{join(towers,"\n"),res}) end procedure print_water({5,3,7,2,6,4,5,9,1,2})
- Output:
# # #~~~~# #~#~~# #~#~#~## #~#~#### ###~#### ########~# ########## collected:14
Phixmonti
include ..\Utilitys.pmt
def collect_water
0 var res
len 1 - 2 swap 2 tolist
for
var i
1 i 1 - slice max >ps
len i - 1 + i swap slice max >ps
i get ps> ps> min swap -
0 max res + var res
endfor
drop
res
enddef
( ( 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 ) )
len for
get dup print " : " print collect_water ?
endfor
- 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 === Press any key to exit ===
PicoLisp
(de water (Lst)
(sum
'((A)
(cnt
nT
(clip (mapcar '((B) (>= B A)) Lst)) ) )
(range 1 (apply max Lst)) ) )
(println
(mapcar
water
(quote
(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) ) ) )
- Output:
(2 14 35 0 0 0 0)
Python
Based on the algorithm explained at Stack Overflow:
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]
- 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]
Or, expressed in terms of itertools.accumulate, and showing diagrams:
'''Water collected between towers'''
from itertools import accumulate
from functools import reduce
from operator import add
# ---------------------- TOWER POOLS -----------------------
# towerPools :: [Int] -> [(Int, Int)]
def towerPools(towers):
'''Tower heights with water depths.
'''
def towerAndWater(level, tower):
return tower, level - tower
waterlevels = map(
min,
accumulate(towers, max),
reversed(list(
accumulate(reversed(towers), max)
)),
)
return list(map(towerAndWater, waterlevels, towers))
# ------------------------ DIAGRAMS ------------------------
# showTowers :: [(Int, Int)] -> String
def showTowers(xs):
'''Diagrammatic representation.
'''
upper = max(xs, key=fst)[0]
def row(xd):
return ' ' * (upper - add(*xd)) + (
snd(xd) * 'x' + '██' * fst(xd)
)
return unlines([
''.join(x) for x in zip(*map(row, xs))
])
# showLegend :: (Int, Int)] -> String
def showLegend(xs):
'''String display of tower heights and
total sum of trapped water units.
'''
towers, depths = zip(*xs)
return showList(towers) + (
' -> ' + str(sum(depths))
)
# -------------------------- TEST --------------------------
# main :: IO ()
def main():
'''Water collected in various flooded bar charts.'''
def diagram(xs):
return showTowers(xs) + '\n\n' + (
showLegend(xs) + '\n\n'
)
print(unlines(
map(compose(diagram, towerPools), [
[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]
])
))
# ------------------------ GENERIC -------------------------
# compose :: ((a -> a), ...) -> (a -> a)
def compose(*fs):
'''Composition, from right to left,
of a series of functions.
'''
def go(f, g):
return lambda x: f(g(x))
return reduce(go, fs, lambda x: x)
# fst :: (a, b) -> a
def fst(tpl):
'''First member of a pair.'''
return tpl[0]
# showList :: [a] -> String
def showList(xs):
'''Stringification of a list.'''
return '[' + ','.join(str(x) for x in xs) + ']'
# snd :: (a, b) -> b
def snd(tpl):
'''Second member of a pair.'''
return tpl[1]
# unlines :: [String] -> String
def unlines(xs):
'''A single string formed by the intercalation
of a list of strings with the newline character.
'''
return '\n'.join(xs)
# MAIN ---
if __name__ == '__main__':
main()
- Output:
█ █ █x█ █x█ ███ ████ █████ █████ [1,5,3,7,2] -> 2 █ █ █xxxx█ █x█xx█ █x█x█x██ █x█x████ ███x████ ████████x█ ██████████ ██████████ [5,3,7,2,6,4,5,9,1,2] -> 14 █ █xxxxxxx█ █xxx█xxxxxxx█ █x█x█xxxx█x██ █x█x█x█xx█x███ ███x█x█xx█████ ██████x████████ ████████████████ ████████████████ [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
Quackery
[ $ "turtleduck.qky" loadfile ] now!
[ dup 0 = iff drop done
dup 2 times
[ 20 * 1 walk
1 4 turn
20 1 walk
1 4 turn ] ] is bar ( [ --> )
[ tuck size unrot
-1 4 turn
witheach
[ dup
' [ 158 151 147 ]
dup colour
fill bar
dup 20 * 1 fly
dip
[ behead
' [ 162 197 208 ]
dup colour
fill bar ]
-20 * 1 fly
1 4 turn
20 1 fly
-1 4 turn ]
drop
1 4 turn
-20 * 1 fly ] is chart ( [ [ --> )
[ [] 0 rot witheach
[ max dup dip join ]
drop ] is rightmax ( [ --> [ )
[ reverse
rightmax
reverse ] is leftmax ( [ --> [ )
[ [] unrot
witheach
[ over i^ peek
min swap dip join ]
drop ] is mins ( [ --> [ )
[ [] unrot
witheach
[ over i^ peek
- swap dip join ]
drop ] is diffs ( [ --> [ )
[ 0 swap witheach + ] is sum ( [ --> n )
[ dup 2dup rightmax
swap leftmax
mins diffs chart ] is task1 ( [ --> )
[ dup dup rightmax
swap leftmax
mins diffs sum ] is task2 ( [ --> )
turtle
10 frames
-540 1 fly
' [ [ 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 ] ]
dup
witheach
[ dup size swap
task1
1+ 20 * 1 fly ]
witheach
[ task2 echo sp ]
1 frames
- Output:
I see from the discussion page that drawing the towers wasn't part of the task. Here they are anyway.
"What is the use of a book," thought Alice, "without pictures or conversations?"
2 14 35 0 0 0 0
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)))
When run produces no output -- meaning that the tests have run successfully.
Raku
(formerly Perl 6)
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 ],
;
- Output:
(2 14 35 0 0 0 0)
REXX
version 1
/* 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
- 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, simple numeric list output
/*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
- 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, with ASCII art
This REXX version shows a scale (showing the number of floors in the building) and a representation of the towers and water collected.
It tries to protect the aspect ratio by showing the buildings as in this task's preamble.
/*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".*/
ratio= 2 /*used to maintain a good aspect ratio.*/
p.= /*P. stores plot versions of towers. */
do c=0 to #; cc= c * ratio /*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 ) /*tower scale*/
else p.h= overlay(copies(glyph,ratio) , p.h, 10+cc) /*build tower*/
end /*h*/
end /*c*/
p.1= overlay(w.00 'units of rainwater collected', p.1, 15*ratio+#) /*append text*/
do z=t.0 by -1 to 0; say p.z /*display various tower floors & water.*/
end /*z*/
return
- 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
RPL
« DUPDUP SIZE 1 - NDUPN →LIST DUP 1 « 1 NSUB SUB 0 + « MAX » STREAM » DOSUBS 0 SWAP + @ the seq of max heights to the left of each tower SWAP 1 « NSUB 1 + OVER SIZE SUB 0 + « MAX » STREAM » DOSUBS 0 + @ the seq of max heights to the right of each tower MIN SWAP - 1 « 0 MAX » DOLIST ∑LIST » 'WATER' STO « { {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} } 1 « WATER » DOLIST » 'TASK' STO
- Output:
1: { 2 14 35 0 0 0 0 }
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
output
14 35 0 0 0 0
Rust
use std::cmp::min;
fn getfill(pattern: &[usize]) -> usize {
let mut total = 0;
for (idx, val) in pattern.iter().enumerate() {
let l_peak = pattern[..idx].iter().max();
let r_peak = pattern[idx + 1..].iter().max();
if l_peak.is_some() && r_peak.is_some() {
let peak = min(l_peak.unwrap(), r_peak.unwrap());
if peak > val {
total += peak - val;
}
}
}
total
}
fn main() {
let patterns = vec![
vec![1, 5, 3, 7, 2],
vec![5, 3, 7, 2, 6, 4, 5, 9, 1, 2],
vec![2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1],
vec![5, 5, 5, 5],
vec![5, 6, 7, 8],
vec![8, 7, 7, 6],
vec![6, 7, 10, 7, 6],
];
for pattern in patterns {
println!("pattern: {:?}, fill: {}", &pattern, getfill(&pattern));
}
}
output
pattern: [1, 5, 3, 7, 2], fill: 2 pattern: [5, 3, 7, 2, 6, 4, 5, 9, 1, 2], fill: 14 pattern: [2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1], fill: 35 pattern: [5, 5, 5, 5], fill: 0 pattern: [5, 6, 7, 8], fill: 0 pattern: [8, 7, 7, 6], fill: 0 pattern: [6, 7, 10, 7, 6], fill: 0
Scala
No sweat.
- Output:
See it yourself by running in your browser either by ScalaFiddle (ES aka JavaScript, non JVM) or Scastie (remote JVM).
import scala.collection.parallel.CollectionConverters.VectorIsParallelizable
// Program to find maximum amount of water
// that can be trapped within given set of bars.
object TrappedWater extends App {
private val barLines = List(
Vector(1, 5, 3, 7, 2),
Vector(5, 3, 7, 2, 6, 4, 5, 9, 1, 2),
Vector(2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1),
Vector(5, 5, 5, 5),
Vector(5, 6, 7, 8),
Vector(8, 7, 7, 6),
Vector(6, 7, 10, 7, 6)).zipWithIndex
// Method for maximum amount of water
private def sqBoxWater(barHeights: Vector[Int]): Int = {
def maxOfLeft = barHeights.par.scanLeft(0)(math.max).tail
def maxOfRight = barHeights.par.scanRight(0)(math.max).init
def waterlevels = maxOfLeft.zip(maxOfRight)
.map { case (maxL, maxR) => math.min(maxL, maxR) }
waterlevels.zip(barHeights).map { case (level, towerHeight) => level - towerHeight }.sum
}
barLines.foreach(barSet =>
println(s"Block ${barSet._2 + 1} could hold max. ${sqBoxWater(barSet._1)} units."))
}
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)))
- 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
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
- Output:
[2, 14, 35, 0, 0, 0, 0]
Swift
// Based on this answer from Stack Overflow:
// https://stackoverflow.com/a/42821623
func waterCollected(_ heights: [Int]) -> Int {
guard heights.count > 0 else {
return 0
}
var water = 0
var left = 0, right = heights.count - 1
var maxLeft = heights[left], maxRight = heights[right]
while left < right {
if heights[left] <= heights[right] {
maxLeft = max(heights[left], maxLeft)
water += maxLeft - heights[left]
left += 1
} else {
maxRight = max(heights[right], maxRight)
water += maxRight - heights[right]
right -= 1
}
}
return water
}
for heights in [[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]] {
print("water collected = \(waterCollected(heights))")
}
- Output:
water collected = 2 water collected = 14 water collected = 35 water collected = 0 water collected = 0 water collected = 0 water collected = 0
Tailspin
templates histogramWater
$ -> \( @: 0"1";
[$... -> ($)"1"-> { leftMax: $ -> #, value: ($)"1" } ] !
when <$@..> do @: $; $ !
otherwise $@ !
\) -> \( @: { rightMax: 0"1", sum: 0"1" };
$(last..1:-1)... -> #
$@.sum !
when <{ value: <$@.rightMax..> }> do @.rightMax: $.value;
when <{ value: <$.leftMax..> }> do !VOID
when <{ leftMax: <..$@.rightMax>}> do @.sum: $@.sum + $.leftMax - $.value;
otherwise @.sum: $@.sum + $@.rightMax - $.value;
\) !
end histogramWater
[[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]]... -> '$ -> histogramWater; water in $;$#10;' -> !OUT::write
- Output:
2"1" water in [1, 5, 3, 7, 2] 14"1" water in [5, 3, 7, 2, 6, 4, 5, 9, 1, 2] 35"1" water in [2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1] 0"1" water in [5, 5, 5, 5] 0"1" water in [5, 6, 7, 8] 0"1" water in [8, 7, 7, 6] 0"1" water in [6, 7, 10, 7, 6]
Tcl
Tcl makes for a surprisingly short and readable implementation, next to some of the more functional-oriented languages.
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
}
- 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
Wren
import "./math" for Math, Nums
import "./fmt" for Fmt
var waterCollected = Fn.new { |tower|
var n = tower.count
var highLeft = [0] + (1...n).map { |i| Nums.max(tower[0...i]) }.toList
var highRight = (1...n).map { |i| Nums.max(tower[i...n]) }.toList + [0]
var t = (0...n).map { |i| Math.max(Math.min(highLeft[i], highRight[i]) - tower[i], 0) }
return Nums.sum(t)
}
var 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]
]
for (tower in towers) Fmt.print("$2d from $n", waterCollected.call(tower), tower)
- 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]
XPL0
func WaterCollected(Array, Width); \Return amount of water collected
int Array, Width, Height, I, Row, Col, Left, Right, Water;
[Water:= 0; Height:= 0;
for I:= 0 to Width-1 do \find max height
if Array(I) > Height then Height:= Array(I);
for Row:= 2 to Height do
for Col:= 1 to Width-2 do \(zero-based)
if Row > Array(Col) then \empty location
[Left:= false; Right:= false; \check for barriers
for I:= 0 to Width-1 do
if Array(I) >= Row then \have barrier
[if I < Col then Left:= true;
if I > Col then Right:= true;
];
if Left & Right then Water:= Water+1;
];
return Water;
];
int Towers, I;
[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],
[0]]; \for determining sub-array lengths
for I:= 0 to 7-1 do
[IntOut( 0, WaterCollected(Towers(I), (Towers(I+1)-Towers(I))/4) );
ChOut(0, ^ );
];
]
- Output:
2 14 35 0 0 0 0
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)
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();
- Output:
L(2,14,35,0,0,0,0)
- Programming Tasks
- Solutions by Programming Task
- 11l
- 8080 Assembly
- 8086 Assembly
- Action!
- Ada
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BASIC
- FreeBASIC
- GW-BASIC
- Nascom BASIC
- QuickBASIC
- UBasic/4tH
- Visual Basic .NET
- Yabasic
- C
- C sharp
- C++
- Clojure
- CLU
- Cowgol
- D
- Delphi
- SysUtils,StdCtrls
- EasyLang
- Erlang
- F Sharp
- Factor
- Go
- Groovy
- Haskell
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Lua
- M2000 Interpreter
- Mathematica
- Wolfram Language
- Nim
- Pascal
- Perl
- Phix
- Phixmonti
- PicoLisp
- Python
- Quackery
- Racket
- Raku
- REXX
- RPL
- Ruby
- Rust
- Scala
- Scala Concise
- Scala Parallel Programming
- Scala Time complexity O(n)
- ScalaFiddle qualified
- Scastie qualified
- Scheme
- Sidef
- Swift
- Tailspin
- Tcl
- Wren
- Wren-math
- Wren-fmt
- XPL0
- Zkl