Problem 145202 · hard · Level 01 Prerequisites & Setup

Changing a Wind Logger's Sample Rate

resampling · sample rate · linear interpolation · zero-order hold · integer arithmetic

A weather mast logs wind speed fs_in times per second, but the wind farm's control computer expects readings fs_out times per second. The readings must be resampled: new samples are made at the new times from the old ones.

Old sample i was taken at time i / fs_in, and new sample m is wanted at time m / fs_out. The new samples cover the same stretch of time as the old ones, from 0 up to the last old sample at (N - 1) / fs_in, where N = len(x). So there are M = (N - 1) * fs_out // fs_in + 1 new samples (none if x is empty).

New sample m lies at position p = m * fs_in / fs_out in the old list: between old samples i = floor(p) and i + 1, a fraction f = p - i of the way along. Its value depends on method:

  • "hold": repeat the most recent old sample, x[i] (a zero-order hold: the value stays flat until the next reading arrives),
  • "linear": draw a straight line from x[i] to x[i + 1], giving x[i] + f * (x[i + 1] - x[i]). When f is 0 (the new time is exactly an old time) the value is just x[i], which matters at the very last sample, where there is no x[i + 1].

Write resample(x, fs_in, fs_out, method) that returns the list of the M new samples. Press Run with plot(resample(x, 2, 8, "hold"), kind="step") and plot(resample(x, 2, 8, "linear")) to compare the two.

Examples

Input:  x = [0, 10, 20, 10], fs_in = 2, fs_out = 4, method = "linear"
Output: [0, 5.0, 10, 15.0, 20, 15.0, 10]
Explanation: M = 3 * 4 // 2 + 1 = 7 new samples at positions 0, 0.5, 1, ..., 3;
the half-way ones lie midway between their neighbours.

Input:  x = [0, 10, 20, 10], fs_in = 2, fs_out = 4, method = "hold"
Output: [0, 0, 10, 10, 20, 20, 10]

Input:  x = [1, 2, 3, 4, 5, 6, 7], fs_in = 3, fs_out = 2, method = "linear"
Output: [1, 2.5, 4, 5.5, 7]
Explanation: slowing down from 3 to 2 samples per second: positions 0, 1.5, 3, 4.5 and 6.

Constraints

  • answers are compared with a tolerance of 1e-6, so ints and floats are both fine
  • at most 10**5 new samples

Goals

  • Find where each new sample time falls between two old samples
  • Fill in values by holding the last sample or by drawing a straight line to the next one
  • Work out how many new samples fit in the same stretch of time
Starting Python…