Anonymous user
Water collected between towers: Difference between revisions
uBasic/4tH - eliminated a global
(Dialects of BASIC moved to the BASIC section.) |
imported>Thebeez (uBasic/4tH - eliminated a global) |
||
| (10 intermediate revisions by 7 users not shown) | |||
Line 970:
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}}
<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.
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</pre>
==={{header|Visual Basic .NET}}===
Line 1,730 ⟶ 1,951:
Block 6 does not hold any water units.
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}}==
Line 2,877 ⟶ 3,318:
@[2, 14, 35, 0, 0, 0, 0]
</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}}==
Line 3,798 ⟶ 4,335:
2 ██████████
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>
Line 4,144 ⟶ 4,705:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
var waterCollected = Fn.new { |tower|
| |||