A hiking app records a trail's height every 10 metres. GPS heights are noisy, so after the walk the app smooths them by convolving with a short kernel h of weights (for example [0.25, 0.5, 0.25]: half the sample itself, a quarter of each neighbour). The full convolution full[k] = sum of x[j] * h[k - j] has len(x) + len(h) - 1 values, more than the trail has points, and its peaks sit later than in x: the summit would move up the trail.
The app keeps a list of the same length as x instead, centred on the kernel:
same[k] = full[k + c] for k = 0, ..., len(x) - 1, with c = (len(h) - 1) // 2.
Heights before the first and after the last recorded point count as 0, exactly as in the full convolution. For a kernel of odd length the centre weight then lines up with x[k]; for an even length there is no centre, and this rule puts the output half a sample late.
Write same_conv(x, h) that returns same (an empty list for an empty x). Press Run with plot(x) and plot(same_conv(x, h)) to check the summit has stayed put.
Examples
Input: x = [0, 0, 6, 0, 0], h = [0.25, 0.5, 0.25]
Output: [0.0, 1.5, 3.0, 1.5, 0.0]
Explanation: full = [0, 0, 1.5, 3, 1.5, 0, 0] and c = 1, so same = full[1:6].
The spike is spread out but its middle is still at index 2.
Input: x = [2, 4, 6], h = [0.5, 0.5]
Output: [1.0, 3.0, 5.0]
Explanation: c = (2 - 1) // 2 = 0: same[1] = (2 + 4) / 2, the average of the point and the one before.
Input: x = [4, 4, 4], h = [0.25, 0.5, 0.25]
Output: [3.0, 4.0, 3.0]
Explanation: at the ends one neighbour is missing and counts as 0, so a flat trail dips.
Constraints
hmay be longer thanx; the output still haslen(x)values- answers are compared with a tolerance of
1e-6
Goals
- Cut the full convolution down to the input's length with a stated alignment
- See why the alignment keeps a peak in place for a symmetric kernel
- Explain the dip at the edges when missing samples count as zero