Water Towers

Challenge: Water between Towers

In a two-dimensional world, we begin with a bar-chart, or rows of unit-width 'towers' of arbitrary height. Then it rains, completely filling all convex enclosures in the chart with water.

9        █       
8        █           
7   █    █          
6   █ █  █           
5 █ █ █ ██      
4 █ █ ████      
3 ███ ████     
2 ████████ █ 
1 ██████████ 

9        █    
8        █    
7   █≈≈≈≈█    
6   █≈█≈≈█    
5 █≈█≈█≈██    
4 █≈█≈████    
3 ███≈████    
2 ████████≈█
1 ██████████

Your task for this challenge is to write a generator water-towers. It will take as input a (list @ud), with each number representing the height of a tower from left to right. It will output a @ud representing the units of water that can be contained within the structure.

Example usage:

> +water-towers [5 3 7 2 6 4 5 9 1 2 ~]
14

Unit Tests

Following a principle of test-driven development, we compose a series of tests which allow us to rigorously check for expected behavior.

/+  *test
/=  water-towers  /gen/water-towers
|%
++  test-01
  %+  expect-eq
    !>  `@ud`2
    !>  (water-towers [1 5 3 7 2 ~])
++  test-02
  %+  expect-eq
    !>  `@ud`14
    !>  (water-towers [5 3 7 2 6 4 5 9 1 2 ~])
++  test-03
  %+  expect-eq
    !>  `@ud`35
    !>  (water-towers [2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1 ~])
++  test-04
  %+  expect-eq
    !>  `@ud`0
    !>  (water-towers [5 5 5 5 ~])
++  test-05
  %+  expect-eq
    !>  `@ud`0
    !>  (water-towers [5 6 7 8 ~])
++  test-06
  %+  expect-eq
    !>  `@ud`0
    !>  (water-towers [8 7 7 6 5 4 3 2 ~])
++  test-07
  %+  expect-eq
    !>  `@ud`0
    !>  (water-towers [0 1 6 7 10 7 6 1 0 ~])
++  test-08
  %+  expect-eq
    !>  `@ud`0
    !>  (water-towers [100 0 0 0 0 0 0 0 ~])
++  test-09
  %+  expect-eq
    !>  `@ud`7
    !>  (water-towers [100 0 0 0 0 0 0 0 1 ~])
++  test-10
  %+  expect-eq
    !>  `@ud`50
    !>  (water-towers [10 0 0 0 0 0 10 ~])
++  test-11
  %+  expect-eq
    !>  `@ud`4
    !>  (water-towers [8 7 8 7 8 7 8 7 8 ~])
++  test-12
  %+  expect-eq
    !>  `@ud`40
    !>  (water-towers [0 1 2 3 4 5 4 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 4 5 4 3 2 1 0 ~])
--

Solutions

These solutions were submitted by the Urbit community as part of a competition in ~2023.6. They are made available under the MIT License and CC0. We ask you to acknowledge authorship should you utilize these elsewhere.

Solution #1

By ~dannul-bortux. A model for literate programming in Hoon.

::
::  A gate for computing volume of water collected between towers.
::
::    Take a list (of type list @ud), with each value representing the height of
::    a tower from left to right. Outputs a @ud representing the units of water 
::    that can be contained within the structure.
::
::    Our approach involves calculating the total volume of rainfall or water by
::    aggregating the water volume from each tower location. For a specific 
::    tower location. water volume is determined by subtracting the “height” 
::    of the tower with maximum rainfall (“total height with water”) from the 
::    height of the tower alone. Tower heights are given by corresponding values
::    in the input list.
::  
::    The “total height with water” at a location is determined by the height of
::    surrounding boundary towers within our structure. Each tower location will
::    have at most two boundary towers: one boundary tower on either side (left 
::    and right). The left boundary tower is defined as the highest tower to the
::    left of our specified tower location. The right boundary tower is defined 
::    as the highest tower to the right of our specified tower location. The 
::    value of “total height with water” at a location is equal to the lesser of
::    the two boundary tower heights (the minimum of the left boundary tower 
::    height vs. right boundary tower height). When less than two boundary 
::    towers are present, the “total height with water” is equal to the height
::    of the tower itself because no water can be contained without boundaries.
::
|=  inlist=(list @ud)
^-  @ud
::  If, input list is empty
::
?:  =(0 (lent inlist))
  ::  Then, throw error
  ::
  ~|  'Error - input list cannot be empty'
  !!
=<  (compute-totalvol inlist)
|%
::
::  +compute-totalvol: Gets total volume of water by summing water at each 
::  individual location.
::
::    Moves left to right iterating over each location (index in list). 
::    Determines waterfall at each location and aggregates all waterfall to 
::    find and return total volume.
::
++  compute-totalvol
  |=  [n=(list @ud)]
  ^-  @ud
  ::  i is face for iterating over all index/locations
  ::
  =/  i  0
  ::  tot is face for aggregating volume of water
  ::
  =/  tot  0
  |-
  ::  If, we're at end of input list
  ::
  ?:  =(i (lent n))
    ::  then, return total
    ::
    tot
  ::  else, compute water volume at current index, add to total, and increment i
  ::
  %=  $
      tot  (add tot (compute-indvol i n))
      i  +(i)
  ==
::
::  +compute-indvol: Computes volume at an individual location.
::   
::    Computes volume at an individual location (index in input list) by 
::    subtracting tower height from “total height with water”. “Total height 
::    with water” will be determined at a particular location by the height of 
::    “boundary towers” for that location. 
::
++  compute-indvol
  |=  [loc=@ud n=(list @ud)]
  ^-  @ud
  (sub (compute-waterheight loc n) (snag loc `(list @ud)`n))
::
::  +compute-waterheight: Measures the “total height with water” at a specified 
::  index/location.
::
::    “Total height with water” at a particular location is measured using the 
::    heights (value) at the left and right boundary towers. The lesser of these
::    two values (left height vs right height) is equal to the “total height 
::    with water” at our input location. 
::  
::    Right boundary tower is the tallest tower to the right of the location--
::    i.e. highest value (height) with higher index. The left boundary tower is
::    the tallest tower to the left of the location i.e. highest value (height) 
::    with lower index. 
::
::    The “find-boundaryheight” arm iterates left to right and works for 
::    measuring height of the right boundary tower. For the left boundary tower 
::    we can use a mirror approach. We reverse the input list and adjust the 
::    input index accordinglyto move right-to-left. 
::
::    In the case where no right or left boundary tower exists, our 
::    “find-boundaryheight” arm will return the tower height at our current 
::    index (indicating no water present) and we correctly compute 0 water 
::    volume in our compute-indvol arm.
::
++  compute-waterheight
  |=  [loc=@ud n=(list @ud)]
  ^-  @ud
  ::  rbth is a face for our "right boundary tower height" computed using our 
  ::  "find-boundaryheight" arm moving left to right
  ::
  =/  rbth  (find-boundaryheight loc n)
  ::  lbth is a face for our "right boundary tower height" computed using our 
  ::  "find-boundaryheight" arm moving (mirrored) right to left
  ::
  =/  lbth  (find-boundaryheight (sub (lent n) +(loc)) (flop n))
  ::  If, right boundary tower height is less than left boundary tower height, 
  ::
  ?:  (lth rbth lbth)
  ::  then, return right boundary tower height
  ::
    rbth
  ::  else, return left boundary tower height
  ::
  lbth
::
::  +find-boundaryheight: Computes the height of the highest tower to the right 
::  of the input location
::
::    Moves left to right starting at input location until the end of input 
::    list. Tracks height of each tower location with a height greater than 
::    height at corresponding input location.
::
++  find-boundaryheight
  |=  [loc=@ud n=(list @ud)]
  ^-  @ud
  ::  i is face used to iterate over input list starting one past input index
  ::
  =/  i  +(loc)
  ::  bheight is face used to measure boundary tower heights--i.e. any tower
  ::  heights greater than height at input location. At start, bheight is set to
  ::  input location height. If no greater heights are found, input location
  ::  height is returned (indicating no higher boundary towers found).
  ::
  =/  bheight  (snag loc n)
  |-
  ::  If, we are at the end of our input
  ::
  ?:  (gte i (lent n))
    ::  then, return boundary tower height
    ::
    bheight
  ::  else, if current tower height is greater than currently stored boundary 
  ::  tower height, replace boundary tower height. Incr iteration idx.
  ::
  %=  $
      bheight  ?:  (gth (snag i n) bheight)
                 (snag i n) 
               bheight
      i        +(i)
  ==
--

Solution #2

By ~racfer-hattes. A short and elegant solution.

=>
|%
++  go 
  |=  [current=@ud previous=(list @ud) next=(list @ud)]
  =/  left-peak  (roll previous max)
  =/  right-peak  (roll next max)
  =/  min-peak  (min left-peak right-peak)
  =/  water-level  
    ?:  (lth min-peak current)  0  
    (sub min-peak current)
  ?~  next  water-level
  (add water-level $(current i.next, next t.next, previous [current previous]))
--
|=  xs=(list @ud)
?~  xs  0
%-  go  [i.xs ~ t.xs]

Solution #3

By ~dozreg-toplud. Another very literate and clean solution.

::  +water-towers: a solution to the HSL challenge #1
::
::    https://github.com/tamlut-modnys/template-hsl-water-towers
::    Takes a (list @ud) of tower heights, returns the number of the units of
::    water that can be held in the given structure.
::
|=  towers=(list @ud)
^-  @ud
=<
::  x, y are horizontal and vertical axes
::
=|  water-counter=@ud
=/  x-last-tower=@ud  (dec (lent towers))
=/  y-highest-tower=@ud  (roll towers max)
::  iterate along y axis from y=0
::
=/  y=@ud  0
|-
^-  @ud
::  if, y > max(towers)
::
?:  (gth y y-highest-tower)
  ::  then, return water-counter
  ::
  water-counter
::  else, iterate along x axis from x=1
::
=/  x=@ud  1
|-
^-  @ud
::  if, x = x(last tower)
::
?:  =(x x-last-tower)
  ::  then, go to the next y
  ::
  ^$(y +(y))
::  else, increment water-counter if the point [x y] is not occupied by a tower
::  and has towers to the left and right on the same y, after go to the next x
::
=?  water-counter  ?&  (not-tower x y)
                       (has-tower-left x y)
                       (has-tower-right x y)
                   ==
  +(water-counter)
$(x +(x))
::
::  Core with helping functions
::
|%
::  ++not-tower: returns %.y if the coordinate [x y] is free from a tower,
::  %.n if occupied.
::
++  not-tower
  |=  [x=@ud y=@ud]
  ^-  ?
  (gth y (snag x towers))
::  ++has-tower-left: returns %.y if there is a tower with height >= y to
::  the left from x, %.n otherwise. Enabled computation caching to only test
::  each point once.
::
++  has-tower-left
  |=  [x=@ud y=@ud]
  ~+
  ^-  ?
  ::  no towers to the left from the 0th tower
  ::
  ?:  =(x 0)
    %.n
  ::  check recursively to the left
  ::
  ?|  (gte (snag (dec x) towers) y)
      $(x (dec x))
  ==
::  ++has-tower-right: returns %.y if there is a tower with height >= y to
::  the right from x, %.n otherwise. Enabled computation caching to only test
::  each point once.
::
++  has-tower-right
  |=  [x=@ud y=@ud]
  ~+
  ^-  ?
  ::  no towers to the right from the last tower
  ::
  ?:  =(x (dec (lent towers)))
    %.n
  ::  check recursively to the right
  ::
  ?|  (gte (snag +(x) towers) y)
      $(x +(x))
  ==
::
--