rainwater.fsx

// https://techdevguide.withgoogle.com/resources/volume-of-water/
// Imagine an island that is in the shape of a bar graph. When it rains, certain areas of the island fill up with rainwater to form lakes. Any excess rainwater the island cannot hold in lakes will run off the island to the west or east and drain into the ocean.
// Given an array of positive integers representing 2-D bar heights, design an algorithm (or write a function) that can compute the total volume (capacity) of water that could be held in all lakes on such an island given an array of the heights of the bars. Assume an elevation map where the width of each bar is 1.

// Calculate rainwater capacity of bar graph island.
let capacity heights =
    // height to which water rises is bounded above by greatest height to the left and greatest height to the right, and equal to the minimum of these. This is the 'rectilinear convex hull' of the original shape.

    // greatest height strictly to the left of ith bar
    let leftLimits = List.scan max 0 heights |> List.tail
    // greatest height strictly to the right of ith bar
    let rightLimits = List.scanBack max heights 0 |> List.rev |> List.tail |> List.rev

    let limits = List.map2 min leftLimits rightLimits 

    // flooded height cannot be lower than original height
    let floodedHeights = List.map2 max heights limits

    let depths = List.map2 (-) floodedHeights heights
    assert (List.min depths >= 0)
    List.sum depths

assert (capacity [1;3;2;4;1;3;1;4;5;2;2;1;4;2;2] = 15)