Problem 330785 · medium · Level 03 Linear Management & Searching

Is a Straight Line the Right Shape?

residuals · R squared · least-squares line · model checking

A driving school measured braking distances (metres) at different speeds (km/h). Before anyone quotes a "metres per km/h" rule, the instructor wants to check whether a straight line is a sensible description at all.

Write residual_report(speed, dist, tol):

  1. Fit the least-squares line dist = a + b * speed to the pairs (the line with the smallest sum of squared residuals).
  2. The residual of a measurement is its actual distance minus the line's distance.
  3. Return a tuple (r2, signs):
    • r2 = 1 - SSE / SST, where SSE is the sum of the squared residuals and SST the sum of the squared differences between each distance and the mean distance. If SST is 0 (all distances equal), r2 is 1.0.
    • signs is a string with one character per measurement, in order of increasing speed (measurements with equal speeds keep their original order): "+" when the residual is greater than tol, "-" when it is less than -tol, and "0" otherwise.

If all speeds are equal, return None.

The setup provides braking_tests(n, seed, curved), which returns random lists (speed, dist); with curved=True the distance grows with the square of the speed, as in real braking, and with curved=False it grows in a straight line.

Examples

Input:  speed = [0, 1, 2, 3, 4, 5, 6], dist = [0, 1, 4, 9, 16, 25, 36], tol = 0.5
Output: (0.9230769230769231, "+0---0+")
Explanation: the line is dist = -5 + 6 * speed. The residuals are 5, 0, -3, -4, -3, 0, 5:
above the line at both ends and below it in the middle, the signature of a curve,
although the line accounts for 92% of the variation.

Input:  speed = [30, 10, 20], dist = [9, 4, 5], tol = 0.1
Output: (0.8928571428571429, "+-+")
Explanation: sorted by speed the residuals are 0.5, -1 and 0.5.

Constraints

  • 2 <= len(speed) == len(dist) <= 10**5
  • 0 <= tol; values are integers or floats between 0 and 10**4
  • floats are compared with a tolerance of 1e-6

Goals

  • Compute the residuals of a least-squares line as actual minus predicted
  • Compute R² as the share of the variation the line accounts for
  • Read the sign pattern of the residuals along x to spot a curved relationship
Starting Python…