Water collected between towers: Difference between revisions

{{trans|Python}}

 

V l = tower.len

V highest_left = [0] [+] (1 .< l).map(n -> max(@tower[0 .< n]))

[6, 7, 10, 7, 6]]

 

 

{{out}}

 

=={{header|8080 Assembly}}==

jmp demo

;;; Calculate the amount of water a row of towers will hold

dw t6,t7-t6

dw t7,t_end-t7

 

{{out}}

 

=={{header|8086 Assembly}}==

org 100h

section .text

dw t6,t7-t6

dw t7,t_end-t7

 

{{out}}

 

<pre>2 14 35 0 0 0 0</pre>

 

=={{header|AppleScript}}==

{{Trans|JavaScript}}

 

 

-- waterCollected :: [Int] -> Int

return lst

end tell

{{Out}}

 

=={{header|AutoHotkey}}==

while (++l <= topL)

for t, h in oTwr

}

result := ""

for i, oTwr in data{

x := WCBT(oTwr)

}

{{out}}

<pre>Chart [1, 5, 3, 7, 2] has 2 water units

 

=={{header|AWK}}==

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

BEGIN {

function max(x,y) { return((x > y) ? x : y) }

function min(x,y) { return((x < y) ? x : y) }

{{out}}

<pre>

 

=={{header|BASIC}}==

20 K=K+1: READ N: IF N=0 THEN END

30 FOR I=0 TO N-1: READ T(I): NEXT

180 DATA 4, 8,7,7,6

190 DATA 5, 6,7,10,7,6

 

{{out}}

 

<pre>Block 1 holds 2 water units.

Block 2 holds 14 water units.

Block 5 holds 0 water units.

Block 6 holds 0 water units.

 

=={{header|C}}==

Takes the integers as input from command line, prints out usage on incorrect invocation.

#include<stdlib.h>

#include<stdio.h>

return 0;

}

Output :

<pre>

===Version 1===

Translation from [[{{FULLPAGENAME}}#Visual_Basic_.NET|Visual Basic .NET]]. See that version 1 entry for code comment details and more sample output.

{

static void Main(string[] args)

}

}

Block 2 retains 14 water units.

Block 3 retains 35 water units.

Block 5 retains 0 water units.

Block 6 retains 0 water units.

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

{

// Variable names key:

}

}

'''Output:'''

<pre>Block 1 holds 2 water units.

 

=={{header|C++}}==

#include <iostream>

#include <vector>

std::cin.get();

return 0;

 

{{out}}

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

mins (map min maxl maxr)] ; minimum highest surrounding tower per position

(reduce + (map - mins towers)))) ; sum up the trapped water per position

{{out}}

;; in the following, # is a tower block and ~ is trapped water:

;;

;; 5 3 7 2 6 4 5 9 1 2

(trapped-water [5 3 7 2 6 4 5 9 1 2]) ;; 14

 

=={{header|Cowgol}}==

include "argv.coh";

 

 

print_i8(water(&towers[0], count as intptr));

 

{{out}}

=={{header|D}}==

{{Trans|C#}}

 

void main() {

writeln(" water units.");

}

 

{{out}}

Block 6 does not hold any water units.

Block 7 does not hold any water units.</pre>

 

=={{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.

 

-module(watertowers).

-export([towers/1, demo/0]).

[io:format("~p -> ~p~n", [Case, towers(Case)]) || Case <- Cases],

ok.

 

{{out}}

=={{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.

(*

A solution I'd show to Euclid !!!!.

| _ -> l

fn (min n i) (max n i) g (e*(abs(n-i)-1))

{{out}}

<pre>

 

=={{header|Factor}}==

 

: area ( seq -- n )

{ 8 7 7 6 }

{ 6 7 10 7 6 }

{{out}}

<pre>

{ 6, 7, 10, 7, 6 } -> 0

</pre>

 

=={{header|Go}}==

package main

 

fmt.Println(waterCollected([]int{8, 7, 7, 6}))

fmt.Println(waterCollected([]int{6, 7, 10, 7, 6}))

 

{{out}}

=={{header|Groovy}}==

 

Integer waterBetweenTowers(List<Integer> towers) {

// iterate over the vertical axis. There the amount of water each row can hold is

println "$it => total water: ${waterBetweenTowers it}"

}

 

{{out}}

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:

 

import qualified Data.Vector.Unboxed as V

 

, [8, 7, 7, 6]

, [6, 7, 10, 7, 6]

{{Out}}

<pre>2

Or, using Data.List for simplicity - no need to prioritize performance here - and adding diagrams:

 

 

-------------- WATER COLLECTED BETWEEN TOWERS ------------

showLegend =

((<>) . show . fmap fst)

{{Out}}

<pre>

 

'''Solution:'''

waterLevels=: collectLevels - ] NB. water levels for each tower

collectedWater=: +/@waterLevels NB. sum the units of water collected

 

'''Examples:'''

14

printTowers 5 3 7 2 6 4 5 9 1 2

TestResults =: 2 14 35 0 0 0 0

TestResults -: collectedWater &> TestTowers NB. check tests

 

=={{header|Java}}==

{{trans|D}}

public static void main(String[] args) {

int i = 1;

}

}

{{out}}

<pre>Block 1 holds 2 water units.

===ES5===

{{Trans|Haskell}}

'use strict';

 

 

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

 

{{Out}}

 

===ES6===

{{Trans|Haskell}}

 

 

// waterCollected :: [Int] -> Int

 

 

const main = () => [

[1, 5, 3, 7, 2],

 

 

 

// Tuple (,) :: a -> b -> (a, b)

const Tuple = a =>

b => ({

length: 2

});

// the predicate p.

xs => [...xs].filter(p);

 

 

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

xs => xs.length > 0 ? (

scanl(f)(

 

 

const scanr = f =>

 

 

// scanr1 :: (a -> a -> a) -> [a] -> [a]

const scanr1 = f =>

// seed-value argument, and assumes that

// xs is not empty.

// The numeric sum of all values in xs.

xs.reduce((a, x) => a + x, 0);

 

 

// custom function, rather than with the

// default tuple constructor.

 

// MAIN ---

return main();

{{Out}}

 

=={{header|Julia}}==

Inspired to [[#Python]].

 

 

function watercollected(towers::Vector{Int})

towerprint(towers, watercollected(towers))

println()

 

{{out}}

=={{header|Kotlin}}==

{{trans|Python}}

 

fun waterCollected(tower: IntArray): Int {

println("${"%2d".format(waterCollected(tower))} from ${tower.contentToString()}")

}

 

{{out}}

=={{header|Lua}}==

{{trans|C#}}

local length = 0

for _ in pairs(tower) do

end

 

{{out}}

<pre>Block 1 holds 2 water units.

=={{header|M2000 Interpreter}}==

===Scan min-max for each bar===

Module Water {

Flush ' empty stack

}

Water

===Drain method===

Module Water2 {

}

Water2

===Faster Method===

{{trans|AWK}}

Module Water3 {

Flush ' empty stack

}

Water3

 

{{out}}

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

waterbetween[h_List] := Module[{mi, ma, ch},

{mi, ma} = MinMax[h];

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

{{out}}

<pre>{2, 14, 35, 0, 0, 0, 0}</pre>

 

=={{header|Nim}}==

 

proc water(barChart: seq[int], isLeftPeak = false, isRightPeak = false): int =

const waterUnits = barCharts.map(chart=>water(chart, false, false))

echo(waterUnits)

{{out}}

<pre>

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

</pre >

 

=={{header|Perl}}==

use List::Util qw{ min max sum };

 

[ 8, 7, 7, 6 ],

[ 6, 7, 10, 7, 6 ],

{{Out}}

<pre>2 14 35 0 0 0 0</pre>

=={{header|Phix}}==

=== inefficient one-pass method ===

{{out}}

<pre>

</pre>

=== more efficient two-pass version ===

(same output)

 

=== pretty print routine ===

{{out}}

<pre>

=={{header|Phixmonti}}==

{{trans|Phix}}

 

def collect_water

len for

get dup print " : " print collect_water ?

{{out}}

<pre>[1, 5, 3, 7, 2] : 2

 

=={{header|PicoLisp}}==

(sum

'((A)

(5 6 7 8)

(8 7 7 6)

{{out}}

<pre>(2 14 35 0 0 0 0)</pre>

Based on the algorithm explained at [http://stackoverflow.com/questions/24414700/amazon-water-collected-between-towers/32135773#32135773 Stack Overflow]:

 

N = len(tower)

highest_left = [0] + [max(tower[:n]) for n in range(1,N)]

[6, 7, 10, 7, 6]]

 

{{Out}}

<pre>

Or, expressed in terms of '''itertools.accumulate''', and showing diagrams:

 

 

from itertools import accumulate

if __name__ == '__main__':

main()

{{Out}}

<pre> █

 

[6,7,10,7,6] -> 0</pre>

 

=={{header|Racket}}==

(require racket/match)

 

[6 7 10 7 6]]))

(map water-collected-between-towers towerss))

 

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

{{Trans|Haskell}}

 

sub max_r ( @a ) { ([\max] @a.reverse).reverse }

 

[ 8, 7, 7, 6 ],

[ 6, 7, 10, 7, 6 ],

{{Out}}

<pre>(2 14 35 0 0 0 0)</pre>

=={{header|REXX}}==

===version 1===

Call bars '1 5 3 7 2'

Call bars '5 3 7 2 6 4 5 9 1 2'

Say ol

End

{{out}}

<pre>1 5 3 7 2 -> 2

 

===version 2, simple numeric list output===

call tower 1 5 3 7 2

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

end /*f*/

say right(w.00, 9) 'units of rainwater collected for: ' y /*display water units.*/

{{out|output|text=&nbsp;}}

<pre>

 

It tries to protect the aspect ratio by showing the buildings as in this task's preamble.

call tower 1 5 3 7 2

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

do z=t.0 by -1 to 0; say p.z /*display various tower floors & water.*/

end /*z*/

{{out|output|text=&nbsp;}}

<pre>

2 ██████████

1 ██████████ no units of rainwater collected

</pre>

 

=={{header|Ruby}}==

def a(array)

n=array.length

a([ 8, 7, 7, 6 ])

a([ 6, 7, 10, 7, 6 ])

'''output'''

<pre>

 

=={{header|Rust}}==

use std::cmp::min;

 

}

}

'''output'''

<pre>

{{libheader|Scastie qualified}}

{{works with|Scala|2.13}}

 

// Program to find maximum amount of water

println(s"Block ${barSet._2 + 1} could hold max. ${sqBoxWater(barSet._1)} units."))

 

 

=={{header|Scheme}}==

(scheme write))

 

(5 6 7 8)

(8 7 7 6)

{{out}}

<pre>(1 5 3 7 2) -> 2

 

=={{header|Sidef}}==

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

}

[ 8, 7, 7, 6 ],

[ 6, 7, 10, 7, 6 ],

{{out}}

<pre>

 

=={{header|Swift}}==

// https://stackoverflow.com/a/42821623

 

[6, 7, 10, 7, 6]] {

print("water collected = \(waterCollected(heights))")

 

{{out}}

 

=={{header|Tailspin}}==

templates histogramWater

when <$@..> do @: $; $ !

otherwise $@ !

$(last..1:-1)... -> #

$@.sum !

[8, 7, 7, 6],

[6, 7, 10, 7, 6]]... -> '$ -> histogramWater; water in $;$#10;' -> !OUT::write

 

{{out}}

<pre>

</pre>

 

=={{header|Tcl}}==

Tcl makes for a surprisingly short and readable implementation, next to some of the more functional-oriented languages.

 

proc flood {ground} {

} {

puts [flood $p]:\t$p

 

{{out}}

0: 8 7 7 6

0: 6 7 10 7 6</pre>

 

=={{header|Wren}}==

{{libheader|Wren-math}}

{{libheader|Wren-fmt}}

 

var waterCollected = Fn.new { |tower|

[6, 7, 10, 7, 6]

]

 

{{out}}

</pre>

 

 

 

 

=={{header|zkl}}==

{{trans|Haskell}}

// compile max wall heights from left to right and right to left

// then each pair is left/right wall of that cell.

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

ss

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

{{out}}

<pre>