# 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. ```hoon /+ *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.* ```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.* ```hoon => |% ++ 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.* ```hoon :: +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)) == :: -- ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.urbit.org/hoon/examples/water-towers.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.