Data science: Flag unusual days

A monitoring job checks each day's value against the days just before it, and raises a flag when it is far out of line.

What to build

A program that flags anomalies with a rolling mean and standard deviation of the previous k values.

Requirements

  • For each day that has k days before it, compute the mean and the population standard deviation of those k values.
  • Flag the day when the standard deviation is over 0 and the value is more than 3 standard deviations from the mean, or when the standard deviation is 0 and the value differs from the mean.
  • For each flagged day print day D: V (mean M), with D counting from 1, V exactly as given and M to two decimals; if no day is flagged, print no anomalies.

Input

Line 1: k. Line 2: the daily values separated by spaces.

Output

One line per flagged day, or one line.

Constraints

1 ≤ k ≤ 100; 1 to 1000 values.

Example

Input:

3
10 11 10 30 11 10 11

Output:

day 4: 30 (mean 10.33)

Why it works

Using only the previous k values gives a threshold that adapts to recent behaviour and could run live, and measuring the distance in standard deviations makes the rule work for any scale of data.

Examples

Example 1 · Input
3
10 11 10 30 11 10 11
Expected output
day 4: 30 (mean 10.33)
Example 2 · Input
2
5 5 5 6
Expected output
day 4: 6 (mean 5.00)

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

For day i (counting from 0), the recent past is values[i - k:i].

Hint 2

The population standard deviation is the square root of the average squared distance from the mean.

Hint 3

When the standard deviation is 0, any different value is unusual.

Solution

Show one correct solution (try it yourself first)
k = int(input())
raw = input().split()
values = [float(v) for v in raw]
flagged = False
for i in range(k, len(values)):
    past = values[i - k:i]
    mean = sum(past) / k
    sd = (sum((v - mean) ** 2 for v in past) / k) ** 0.5
    v = values[i]
    if (sd > 0 and abs(v - mean) > 3 * sd) or (sd == 0 and v != mean):
        print(f"day {i + 1}: {raw[i]} (mean {mean:.2f})")
        flagged = True
if not flagged:
    print("no anomalies")

Lesson: Time series basics →