The One Sensor That Predicts Failure

A water company has a log of pumps: X[i] holds the d sensor readings of pump i and y[i] is 1 if it failed within a month, 0 otherwise. The engineers want the single question that best predicts failure: "is sensor f above t?" If yes, predict above; if no, predict 1 - above.

For each sensor f, the thresholds considered are the midpoints (a + b) / 2 of every two neighbouring distinct values a < b of that sensor in the log. A sensor whose readings are all equal offers no threshold.

Write fit_stump(X, y) that returns a tuple (f, t, above, mistakes) for the rule with the fewest wrong predictions on the log. On a tie prefer the smallest f, then the smallest t, then above = 1.

The tests use pump_log(n, d, seed), which returns (X, y); it is available in your code. The logs have up to 30,000 pumps, too many to recount the whole log for every candidate threshold.

Examples

Input:  X = [[1, 10], [2, 30], [3, 20], [4, 40]], y = [0, 1, 0, 1]
Output: (1, 25.0, 1, 0)
Explanation: no threshold on sensor 0 makes fewer than 1 mistake; "sensor 1 above 25
means failure" makes none.

Input:  X = [[5, 7], [5, 3], [5, 9]], y = [1, 0, 1]
Output: (1, 5.0, 1, 0)
Explanation: sensor 0 always reads 5 and offers no threshold.

Constraints

• 2 <= len(X) <= 30000, 1 <= d <= 5; at least one sensor has two distinct values
• readings are whole numbers or have one decimal; y holds only 0 and 1

Goals

• Learn the best single-feature threshold rule over every feature and both directions
• Replace a quadratic recount by one sorted sweep with running counts per feature
• Apply a four-level tie rule consistently