Problem 289536 · medium · Level 02 Linear Data Structures

Boxes Passing the Light Gate

FIR filter · difference filter · edge detection · convolution · runs

A light gate watches a conveyor belt: a lamp shines across the belt onto a sensor, which reports the brightness as a whole number every millisecond. A passing box blocks the beam, so the brightness falls when a box arrives and rises when it has gone. The lamp flickers, so the readings are never perfectly flat.

The controller finds the changes with an FIR filter, a convolution of the readings x with the coefficients

b = [1] * w + [-1] * w (w ones, then w minus ones),

that is, y[k] = sum of b[j] * x[k - j] for j = 0, ..., 2w - 1: the sum of the last w readings minus the sum of the w readings before them. On flat stretches this is near 0; at a change of level it swings far positive (a rise) or negative (a fall). With w = 1 it is the plain difference x[k] - x[k - 1]. Only compute y[k] where every reading it needs exists, k = 2w - 1, ..., len(x) - 1.

Edges:

  • a rise event is a run of consecutive k with y[k] >= threshold; a fall event a run of consecutive k with y[k] <= -threshold;
  • in each run, take the k with the largest |y[k]| (the first such k on a tie); the edge itself is at reading k - w + 1, the first reading of the new level.

Write find_edges(x, w, threshold) that returns a list of pairs (index, "rise") or (index, "fall"), in order. Press Run with plot(x) and a plot of your y to see each step become a peak.

Examples

Input:  x = [90, 90, 12, 10, 11, 88, 90], w = 1, threshold = 30
Output: [(2, 'fall'), (5, 'rise')]
Explanation: y[1..6] = [0, -78, -2, 1, 77, 2]. The box arrives at reading 2 and leaves at reading 5.

Input:  x = [50, 52, 49, 51, 20, 22, 18, 21], w = 2, threshold = 25
Output: [(4, 'fall')]
Explanation: y[3..7] = [-2, -30, -58, -31, -3]. Readings 4, 5 and 6 cross the threshold
together: one event, strongest at k = 5, so the edge is at reading 5 - 2 + 1 = 4.

Constraints

  • if len(x) < 2 * w there is no y at all and the answer is []
  • a list [index, kind] is accepted in place of a tuple

Goals

  • Apply an FIR filter as a convolution with its coefficients, keeping only the samples where it fits
  • Use a difference filter to turn a change of level into a peak
  • Group threshold crossings into single events and locate each one
Starting Python…