Volume of Histogram

In [1]:

    

import Data.List


    

In [2]:

    

computeState :: (Num a, Ord a) => (a, a) -> a -> (a, a)
computeState (waterLevel, currentVolume) wallHeight =
    let waterLevel' = max waterLevel wallHeight in
        (waterLevel', currentVolume + waterLevel' - wallHeight)


    

In [3]:

    

scanHistogram :: (Num a, Ord a) => [a] -> a
scanHistogram xs = snd $ foldl' computeState (0, 0) xs


    

In [4]:

    

findMaximumPosition :: (Ord a) => [a] -> Int
findMaximumPosition xs = snd $ maximum $ zip xs [1..]


    

In [5]:

    

computeWaterVolume :: (Num a, Ord a) => [a] -> a
computeWaterVolume xs =
    let (leftPart, rightPart) = splitAt (findMaximumPosition xs) xs
    in sum $ map scanHistogram [leftPart, reverse rightPart]


    

In [6]:

    

computeWaterVolume [0, 0, 4, 0, 0, 6, 0, 0, 3, 0, 5, 0, 1, 0, 0, 0]


    

    






26