Predict Each Delivery Before It Happens

A courier app predicts how long each delivery will take and then, once it is done, learns from it. Its developers judge the app by the predictions it really made: each one used only the deliveries before it.

Write predict_then_learn(xs, ys), where the deliveries arrive in list order (xs[i] the distance, ys[i] the time). For every i >= 1, predict ys[i] from the deliveries 0 … i-1:

• with the least-squares line a + b·xs[i] through those earlier deliveries, if at least two of their x values differ;
• otherwise with the mean of the earlier y values.

Return a tuple (mse, a, b): the mean of the squared prediction errors over i = 1 … n-1, and the intercept and slope of the least-squares line through all n deliveries (both None if all x are equal).

The setup provides delivery_stream(n, seed, change=False), which returns (xs, ys) for n deliveries; with change=True the courier gets faster halfway through.

Examples

Input:  xs = [1, 2, 3, 4], ys = [3, 5, 8, 9]
Output: (2.259259259259259, 1.0, 2.1)
Explanation: delivery 1 is predicted by the mean 3 (error 2); delivery 2 by the line through (1, 3)
and (2, 5), which is 1 + 2x, giving 7 (error 1); delivery 3 by the line through the first three,
0.333 + 2.5x, giving 10.333 (error -1.333). The mean of 4, 1 and 1.778 is 2.259.

Constraints

• 2 <= len(xs) == len(ys) <= 10**5; all values are whole numbers between 0 and 10**4
• floats are compared with a tolerance of 1e-6
• each test must finish in well under a second in your browser: refitting the line from scratch for every delivery is far too slow

Goals

• Refit the least-squares line after every new example from running sums
• Evaluate a model honestly by predicting each example before learning from it
• Fall back to the mean when no line can be fitted yet