A Chapel's Echoes as an Impulse Response

In a stone chapel a hand clap reaches a listener first directly and then again from each wall, later and quieter. If you could record a perfect click there, you would see a spike of height 1 for the direct sound and one spike per reflection: a reflection that arrives delay seconds after the direct sound with relative strength gain (negative if the wall flips the pressure wave) is a spike of height gain at sample round(delay * fs). That list of spikes, zeros everywhere else, is the chapel's impulse response h. Its length is the last spike's position plus 1. Two reflections that arrive on the same sample add up.

A recording engineer wants to make a dry recording (made in a studio with no echoes) sound as if played in the chapel. The chapel is linear and time-invariant, so the wet sound is the full convolution of dry with h:

wet[k] = sum of dry[j] * h[k - j], with len(dry) + len(h) - 1 samples.

Write chapel(dry, fs, reflections) where reflections is a list of pairs (delay, gain) (seconds, ratio) and fs is the sample rate in hertz. Return wet as a list of floats, or [] for an empty dry. Recordings can be several seconds long and echoes almost a second late, so h may have thousands of samples, almost all zero: the tests expect a method that does not spend time on them. Press Run with plot(wet) to see the echoes pile up.

Examples

Input:  dry = [1, 0.5], fs = 10, reflections = [(0.2, 0.5), (0.3, -0.25)]
Output: [1.0, 0.5, 0.5, 0.0, -0.125]
Explanation: h = [1, 0, 0.5, -0.25] (spikes at samples 0, 2 and 3).
wet[3] = 0.5 * 0.5 + 1 * (-0.25) = 0.0, and wet[4] = 0.5 * (-0.25).

Input:  dry = [0.2, 0.4], fs = 100, reflections = []
Output: [0.2, 0.4]
Explanation: with no walls, h = [1] and the sound is unchanged.

Constraints

• every delay * fs is within 1e-6 of a whole number of samples (at least 1), so rounding is never in doubt

Goals

• Write a room's echoes down as an impulse response: one spike per reflection
• Turn delays in seconds into sample offsets with the sample rate
• Convolve fast by skipping the zeros of a long, mostly empty impulse response