Step by Step solution about How to resolve the algorithm Water collected between towers step by step in the Haskell programming language

Water Collected Between Towers

Both snippets of code solve the same problem: calculating the amount of water collected between a series of towers. Let's break down each implementation:

First Solution:

• The first solution uses the Data.Vector.Unboxed library to store the tower heights as a vector.
• It defines a function waterCollected that takes a vector of tower heights as input and calculates the total amount of water collected.
• It uses a series of higher-order functions to perform the following steps:
  • It scans the vector from left to right and from right to left, finding the maximum height of any tower to the left and right of each position.
  • It calculates the difference between the minimum of the two maximum heights for each position, representing the amount of water that can be collected at that position.
  • It filters out any negative values (indicating no water) and sums the positive values to get the total water collected.
• In main, it creates several lists of tower heights and calculates the water collected for each using the waterCollected function. It then prints the results.

Second Solution:

• The second solution uses the Data.List library to store the tower heights as a list.
• It defines a function towerPools that takes a list of tower heights as input and returns a list of pairs. Each pair represents the minimum height between two towers and the amount of water that can be collected between them.
• It first scans the list from left to right and from right to left, finding the maximum height of any tower to the left and right of each position.
• It then calculates the minimum height between the two maximum heights for each position and subtracts this value from the maximum height on that side, effectively finding the amount of water that can be collected.
• In main, it creates several lists of tower heights and calculates the water pools for each using the towerPools function. It then prints the results.

Additional Features in the Second Solution:

• It includes two additional functions, display and showTowers, which are used to create a diagram of the towers and the water collected between them.
• This provides a visual representation of the water collection, making it easier to understand the results.

Overall, both solutions effectively calculate the amount of water collected between towers, with the second solution providing additional visualization features.

import Data.Vector.Unboxed (Vector)
import qualified Data.Vector.Unboxed as V

waterCollected :: Vector Int -> Int
waterCollected =
  V.sum .            -- Sum of the water depths over each of
  V.filter (> 0) .   -- the columns that are covered by some water.
  (V.zipWith (-) =<< -- Where coverages are differences between:
   (V.zipWith min .  -- the lower water level in each case of:
    V.scanl1 max <*> -- highest wall to left, and
    V.scanr1 max))   -- highest wall to right.

main :: IO ()
main =
  mapM_
    (print . waterCollected . V.fromList)
    [ [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]
    ]


import Data.List (replicate, transpose)

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

towerPools :: [Int] -> [(Int, Int)]
towerPools =
  zipWith min . scanl1 max <*> scanr1 max
    >>= zipWith ((<*>) (,) . (-))


--------------------------- TEST -------------------------
main :: IO ()
main =
  mapM_
    (putStrLn . display . towerPools)
    [ [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]
    ]

------------------------- DIAGRAMS -----------------------

display :: [(Int, Int)] -> String
display = (<>) . showTowers <*> (('\n' :) . showLegend)

showTowers :: [(Int, Int)] -> String
showTowers xs =
  let upper = maximum (fst <$> xs)
   in '\n' :
      ( unlines
          . transpose
          . fmap
            ( \(x, d) ->
                concat $
                  replicate (upper - (x + d)) " "
                    <> replicate d "x"
                    <> replicate x "█"
            )
      )
        xs

showLegend :: [(Int, Int)] -> String
showLegend =
  ((<>) . show . fmap fst)
    <*> ((" -> " <>) . show . foldr ((+) . snd) 0)