Hydrologists predict a river's flow from the rain that falls on its valley. One millimetre of rain in one hour makes the river at the gauge rise and fall over the following hours in a pattern called the unit hydrograph, h: h[i] is the extra flow, in cubic metres per second, i hours after that hour of rain. The valley is treated as linear and time-invariant, so the rain of hour j, rain[j] millimetres, adds rain[j] * h[i] to the flow at hour j + i.
Adding all those contributions gives the convolution of rain and h:
flow[k] = sum of rain[j] * h[k - j], over every j for which both rain[j] and h[k - j] exist.
Write river_flow(rain, h) that returns the whole extra flow, from hour 0 until the last rain has drained away: len(rain) + len(h) - 1 values (the full convolution). With no rain at all, return []. Press Run with plot(rain, kind="stem") and plot(river_flow(rain, h)) to see the flood arrive after the storm.
Examples
Input: rain = [2, 0, 1], h = [0.5, 1.5, 1.0]
Output: [1.0, 3.0, 2.5, 1.5, 1.0]
Explanation: flow[2] = rain[0]*h[2] + rain[1]*h[1] + rain[2]*h[0] = 2.0 + 0 + 0.5 = 2.5.
flow[4] = rain[2]*h[2] = 1.0, the last hour of the second shower's runoff.
Input: rain = [4], h = [1, 2]
Output: [4, 8]
Constraints
- answers are compared with a tolerance of
1e-6, so ints and floats are both fine
Goals
- Compute a convolution sum y[k] = sum of x[j] * h[k - j] by hand
- Know that the full output has len(x) + len(h) - 1 samples
- Skip the index pairs that fall outside either list