Water collected between towers: Difference between revisions

==={{header|FreeBASIC}}===

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|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>