Kalman filter for a price level

hardQuantacceptance —~40 min

Implement kalman_level(values, q, r) — a one-state Kalman filter tracking a price level as a random walk: predict x_prior = x, p_prior = p + q; then correct with gain k = p_prior / (p_prior + r), x = x_prior + k·(z - x_prior), p = (1 - k)·p_prior. Start from x = values[0], p = 1.0, and process every observation including the first.

It is the smoother the workbench's Kalman bot draws over a noisy tape: q is how much you believe the level moves, r how noisy each print is. Return the list of filtered levels rounded to 4 decimal places.

example 1

input

values=[100.0, 101.0, 99.5, 102.0, 101.5], q=0.0, r=1.0

output

[100, 100.3333, 100.125, 100.5, 100.6667]

example 2

input

values=[100.0, 101.0, 99.5, 102.0, 101.5], q=0.5, r=1.0

output

[100, 100.5238, 100.0059, 101.0059, 101.2531]

constraints

1 ≤ len(values) ≤ 10_000
q ≥ 0
r > 0

teacher · 2 hints · the first is free

↗ read the theory

the chapter this problem is cut from

▶ open in the workbench

run the same math on a real tape

●solution.py· utf-8 · spaces:4

def kalman_level(values: list, q: float, r: float) -> list:
    """One-state Kalman filter of a price level. Each estimate rounded to 4 dp."""
    x = values[0]
    p = 1.0
    out = []
    for z in values:
        # TODO: predict step — the level can drift, so the prior variance grows by q
        p_prior = p
        k = p_prior / (p_prior + r)
        x = x + k * (z - x)
        p = (1 - k) * p_prior
        out.append(round(x, 4))
    return out

ln 1, col 1tab indent · esc leave editor

python 3.13 · pyodide

+ 6 hidden on submit

input · keyword arguments to kalman_level()

values=[100.0, 101.0, 99.5, 102.0, 101.5], q=0.0, r=1.0

expected

[100, 100.3333, 100.125, 100.5, 100.6667]

the judge calls kalman_level() with exactly these inputs · outputs are compared to 6 decimal places

● standing bypython 3.13 in your browser · pyodide 0.28.3 · judged on the server to 6 dp⌘↵ run · ⌘⇧↵ submit

paper only · educational · not advice