source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    L = x['limit']
    W = x['window_ms']
    log = []
    now = None
    out = []
    for t in x['requests']:
        now = t if now is None else max(now, t)
        log = [s for s in log if s > now - W]
        if len(log) < L:
            log.insert(0, now)
            log.sort(reverse=True)
            out.append(['allow', 0])
        else:
            out.append(['deny', log[0] + W - now])
    return [out, log]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['exact expiry boundary',
   {'limit': 2, 'requests': [0, 10, 1000, 1011, 1012], 'window_ms': 1000},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]]],
  ['denied requests not logged',
   {'limit': 2, 'requests': [0, 100, 200, 300, 1051, 1150], 'window_ms': 1000},
   [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
    [1051, 1150]]],
  ['late timestamp uses monotonic now',
   {'limit': 2, 'requests': [400, 450, 101, 900, 905, 960], 'window_ms': 500},
   [[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
    [900, 960]]],
  ['retry after oldest expires',
   {'limit': 3, 'requests': [0, 300, 600, 701, 999, 1000, 1001], 'window_ms': 1000},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 299],
     ['deny', 1],
     ['allow', 0],
     ['deny', 299]],
    [300, 600, 1000]]],
  ['random traffic',
   {'limit': 3,
    'requests': [737, 924, 1194, 1231, 1362, 1408, 1509, 1520, 1559, 1643, 1776, 2570],
    'window_ms': 800},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 306],
     ['deny', 175],
     ['deny', 129],
     ['deny', 28],
     ['deny', 17],
     ['allow', 0],
     ['deny', 81],
     ['allow', 0],
     ['allow', 0]],
    [1776, 2570]]],
  ['single slot',
   {'limit': 1, 'requests': [0, 50, 100, 151, 251], 'window_ms': 100},
   [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]]]],
 [['exact expiry boundary',
   {'limit': 2, 'requests': [0, 10, 1000, 1012, 1013], 'window_ms': 1000},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 987]], [1000, 1012]]],
  ['denied requests not logged',
   {'limit': 2, 'requests': [0, 100, 200, 300, 1052, 1150], 'window_ms': 1000},
   [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
    [1052, 1150]]],
  ['late timestamp uses monotonic now',
   {'limit': 2, 'requests': [400, 450, 102, 900, 905, 960], 'window_ms': 500},
   [[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
    [900, 960]]],
  ['retry after oldest expires',
   {'limit': 3, 'requests': [0, 300, 600, 702, 999, 1000, 1001], 'window_ms': 1000},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 298],
     ['deny', 1],
     ['allow', 0],
     ['deny', 299]],
    [300, 600, 1000]]],
  ['random traffic',
   {'limit': 3,
    'requests': [203, 368, 954, 964, 1092, 1537, 1711, 1845, 1983, 2392, 2599, 2816],
    'window_ms': 800},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 39],
     ['allow', 0],
     ['allow', 0],
     ['deny', 43],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 46],
     ['allow', 0]],
    [2392, 2816]]],
  ['single slot',
   {'limit': 1, 'requests': [0, 50, 100, 152, 252], 'window_ms': 100},
   [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 48], ['allow', 0]], [252]]]],
 [['exact expiry boundary',
   {'limit': 2, 'requests': [0, 10, 1000, 1013, 1014], 'window_ms': 1000},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 986]], [1000, 1013]]],
  ['denied requests not logged',
   {'limit': 2, 'requests': [0, 100, 200, 300, 1053, 1150], 'window_ms': 1000},
   [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
    [1053, 1150]]],
  ['late timestamp uses monotonic now',
   {'limit': 2, 'requests': [400, 450, 103, 900, 905, 960], 'window_ms': 500},
   [[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
    [900, 960]]],
  ['retry after oldest expires',
   {'limit': 3, 'requests': [0, 300, 600, 703, 999, 1000, 1001], 'window_ms': 1000},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 297],
     ['deny', 1],
     ['allow', 0],
     ['deny', 299]],
    [300, 600, 1000]]],
  ['random traffic',
   {'limit': 3,
    'requests': [659, 794, 1414, 1446, 1627, 2009, 2196, 2262, 2536, 2557, 2734, 2819],
    'window_ms': 800},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 13],
     ['allow', 0],
     ['allow', 0],
     ['deny', 18],
     ['allow', 0],
     ['allow', 0],
     ['deny', 252],
     ['deny', 75],
     ['allow', 0]],
    [2262, 2536, 2819]]],
  ['single slot',
   {'limit': 1, 'requests': [0, 50, 100, 153, 253], 'window_ms': 100},
   [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 47], ['allow', 0]], [253]]]],
 [['exact expiry boundary',
   {'limit': 2, 'requests': [0, 10, 1000, 1014, 1015], 'window_ms': 1000},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 985]], [1000, 1014]]],
  ['denied requests not logged',
   {'limit': 2, 'requests': [0, 100, 200, 300, 1054, 1150], 'window_ms': 1000},
   [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
    [1054, 1150]]],
  ['late timestamp uses monotonic now',
   {'limit': 2, 'requests': [400, 450, 104, 900, 905, 960], 'window_ms': 500},
   [[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
    [900, 960]]],
  ['retry after oldest expires',
   {'limit': 3, 'requests': [0, 300, 600, 704, 999, 1000, 1001], 'window_ms': 1000},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 296],
     ['deny', 1],
     ['allow', 0],
     ['deny', 299]],
    [300, 600, 1000]]],
  ['random traffic',
   {'limit': 3,
    'requests': [81, 344, 553, 1450, 1591, 1736, 1934, 2492, 2556, 2664, 2677, 2831],
    'window_ms': 800},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 316],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 615],
     ['deny', 461]],
    [2492, 2556, 2664]]],
  ['single slot',
   {'limit': 1, 'requests': [0, 50, 100, 154, 254], 'window_ms': 100},
   [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 46], ['allow', 0]], [254]]]],
 [['exact expiry boundary',
   {'limit': 2, 'requests': [0, 10, 1000, 1015, 1016], 'window_ms': 1000},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 984]], [1000, 1015]]],
  ['denied requests not logged',
   {'limit': 2, 'requests': [0, 100, 200, 300, 1055, 1150], 'window_ms': 1000},
   [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
    [1055, 1150]]],
  ['late timestamp uses monotonic now',
   {'limit': 2, 'requests': [400, 450, 105, 900, 905, 960], 'window_ms': 500},
   [[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
    [900, 960]]],
  ['retry after oldest expires',
   {'limit': 3, 'requests': [0, 300, 600, 705, 999, 1000, 1001], 'window_ms': 1000},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 295],
     ['deny', 1],
     ['allow', 0],
     ['deny', 299]],
    [300, 600, 1000]]],
  ['random traffic',
   {'limit': 3,
    'requests': [85, 117, 140, 309, 683, 1093, 2036, 2231, 2349, 2416, 2706, 2868],
    'window_ms': 800},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 576],
     ['deny', 202],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 420],
     ['deny', 130],
     ['allow', 0]],
    [2231, 2349, 2868]]],
  ['single slot',
   {'limit': 1, 'requests': [0, 50, 100, 155, 255], 'window_ms': 100},
   [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 45], ['allow', 0]], [255]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The retry hint is computed from the newest request instead of the oldest.

Input {limit, window_ms, requests [t]}. The limiter clock is now = max of all timestamps seen, so a late request is evaluated at now. Log entries with s <= now - W are pruned. Allow while fewer than limit entries remain and log now; denials are not logged and report retry = oldest + W - now. Return [[decision, retry]], final log].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    L = x['limit']
    W = x['window_ms']
    idx, prev, cur = 0, 0, 0
    out = []
    for t in x['requests']:
        ci = t // W
        if ci == idx + 1:
            prev, cur = cur, 0
        elif ci > idx + 1:
            prev, cur = 0, 0
        idx = ci
        elapsed = t - idx * W
        est = prev * Fraction(elapsed, W) + cur
        if est + 1 <= L:
            cur += 1
            out.append(['allow', str(est + 1)])
        else:
            out.append(['deny', str(est)])
    return [out, [idx, prev, cur]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1251, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '999/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2601, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3501, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1601, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2197/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 401, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '399/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [762, 1183, 1614, 1772, 2334, 2411, 2425, 2509, 2551, 2560, 2651, 2748, 2860, 2881],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '1817/1000'],
     ['allow', '1193/500'],
     ['allow', '807/250'],
     ['allow', '1499/500'],
     ['allow', '3767/1000'],
     ['deny', '149/40'],
     ['deny', '3473/1000'],
     ['deny', '3347/1000'],
     ['deny', '83/25'],
     ['deny', '3047/1000'],
     ['allow', '939/250'],
     ['deny', '171/50'],
     ['deny', '3357/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 31], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1252, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '499/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2602, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3502, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1602, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '1097/500'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 402, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '199/40'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 284, 685, 716, 946, 1419, 1442, 1550, 1788, 1900, 2219, 2384, 2628, 2704],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['allow', '831/250'],
     ['deny', '404/125'],
     ['allow', '19/5'],
     ['allow', '481/125'],
     ['deny', '17/5'],
     ['allow', '3343/1000'],
     ['allow', '481/125'],
     ['deny', '779/250'],
     ['allow', '486/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 32], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1253, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '997/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2603, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3503, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1603, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2191/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 403, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '397/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [88, 165, 511, 523, 538, 1193, 1202, 1389, 1722, 1826, 2373, 2548, 2774, 2968],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['deny', '807/250'],
     ['deny', '399/125'],
     ['allow', '861/250'],
     ['allow', '389/125'],
     ['allow', '462/125'],
     ['allow', '2881/1000'],
     ['allow', '839/250'],
     ['allow', '1839/500'],
     ['deny', '387/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 33], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1254, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '498/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2604, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3504, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1604, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '547/250'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 404, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '99/20'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [113, 180, 253, 634, 1224, 1448, 1496, 1722, 1887, 2254, 2425, 2792, 2877, 2945],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '388/125'],
     ['allow', '401/125'],
     ['deny', '377/125'],
     ['allow', '389/125'],
     ['allow', '863/250'],
     ['allow', '1619/500'],
     ['allow', '149/40'],
     ['allow', '453/125'],
     ['deny', '3369/1000'],
     ['deny', '633/200']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 34], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1255, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '199/50'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2605, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3505, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1605, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '437/200'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 405, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '79/16'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [237, 850, 1324, 1370, 1559, 1744, 1852, 2112, 2117, 2141, 2288, 2346, 2510, 2979],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '294/125'],
     ['allow', '163/50'],
     ['allow', '1941/500'],
     ['deny', '439/125'],
     ['deny', '412/125'],
     ['allow', '458/125'],
     ['deny', '3649/1000'],
     ['deny', '3577/1000'],
     ['deny', '392/125'],
     ['allow', '1981/500'],
     ['deny', '347/100'],
     ['allow', '3063/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 35], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    L = x['limit']
    W = x['window_ms']
    idx, prev, cur = 0, 0, 0
    out = []
    for t in x['requests']:
        ci = t // W
        if ci == idx + 1:
            prev, cur = cur, 0
        elif ci > idx + 1:
            prev, cur = 0, 0
        idx = ci
        elapsed = t - idx * W
        est = prev + cur * Fraction(W - elapsed, W)
        if est + 1 <= L:
            cur += 1
            out.append(['allow', str(est + 1)])
        else:
            out.append(['deny', str(est)])
    return [out, [idx, prev, cur]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1251, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '999/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2601, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3501, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1601, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2197/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 401, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '399/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [762, 1183, 1614, 1772, 2334, 2411, 2425, 2509, 2551, 2560, 2651, 2748, 2860, 2881],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '1817/1000'],
     ['allow', '1193/500'],
     ['allow', '807/250'],
     ['allow', '1499/500'],
     ['allow', '3767/1000'],
     ['deny', '149/40'],
     ['deny', '3473/1000'],
     ['deny', '3347/1000'],
     ['deny', '83/25'],
     ['deny', '3047/1000'],
     ['allow', '939/250'],
     ['deny', '171/50'],
     ['deny', '3357/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 31], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1252, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '499/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2602, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3502, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1602, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '1097/500'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 402, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '199/40'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 284, 685, 716, 946, 1419, 1442, 1550, 1788, 1900, 2219, 2384, 2628, 2704],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['allow', '831/250'],
     ['deny', '404/125'],
     ['allow', '19/5'],
     ['allow', '481/125'],
     ['deny', '17/5'],
     ['allow', '3343/1000'],
     ['allow', '481/125'],
     ['deny', '779/250'],
     ['allow', '486/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 32], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1253, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '997/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2603, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3503, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1603, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2191/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 403, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '397/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [88, 165, 511, 523, 538, 1193, 1202, 1389, 1722, 1826, 2373, 2548, 2774, 2968],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['deny', '807/250'],
     ['deny', '399/125'],
     ['allow', '861/250'],
     ['allow', '389/125'],
     ['allow', '462/125'],
     ['allow', '2881/1000'],
     ['allow', '839/250'],
     ['allow', '1839/500'],
     ['deny', '387/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 33], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1254, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '498/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2604, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3504, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1604, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '547/250'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 404, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '99/20'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [113, 180, 253, 634, 1224, 1448, 1496, 1722, 1887, 2254, 2425, 2792, 2877, 2945],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '388/125'],
     ['allow', '401/125'],
     ['deny', '377/125'],
     ['allow', '389/125'],
     ['allow', '863/250'],
     ['allow', '1619/500'],
     ['allow', '149/40'],
     ['allow', '453/125'],
     ['deny', '3369/1000'],
     ['deny', '633/200']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 34], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1255, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '199/50'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2605, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3505, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1605, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '437/200'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 405, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '79/16'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [237, 850, 1324, 1370, 1559, 1744, 1852, 2112, 2117, 2141, 2288, 2346, 2510, 2979],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '294/125'],
     ['allow', '163/50'],
     ['allow', '1941/500'],
     ['deny', '439/125'],
     ['deny', '412/125'],
     ['allow', '458/125'],
     ['deny', '3649/1000'],
     ['deny', '3577/1000'],
     ['deny', '392/125'],
     ['allow', '1981/500'],
     ['deny', '347/100'],
     ['allow', '3063/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 35], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Right after a boundary the previous window counts for nothing, allowing a double burst.

Input {limit, window_ms, requests [t]} with nondecreasing t. Keep counts for the current and previous epoch windows; moving to the next window rotates cur into prev, skipping more than one window clears both. The estimate is prev * (W - elapsed)/W + cur with elapsed = t - window start, exactly. Allow when est + 1 <= limit (reporting est + 1), else deny (reporting est). Return [[decision, estimate as fraction string]], [window, prev, cur]].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    L = x['limit']
    W = x['window_ms']
    idx, prev, cur = 0, 0, 0
    out = []
    for t in x['requests']:
        ci = t // W
        if ci > idx:
            prev, cur = cur, 0
        idx = ci
        elapsed = t - idx * W
        est = prev * Fraction(W - elapsed, W) + cur
        if est + 1 <= L:
            cur += 1
            out.append(['allow', str(est + 1)])
        else:
            out.append(['deny', str(est)])
    return [out, [idx, prev, cur]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1251, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '999/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2601, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3501, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1601, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2197/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 401, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '399/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [762, 1183, 1614, 1772, 2334, 2411, 2425, 2509, 2551, 2560, 2651, 2748, 2860, 2881],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '1817/1000'],
     ['allow', '1193/500'],
     ['allow', '807/250'],
     ['allow', '1499/500'],
     ['allow', '3767/1000'],
     ['deny', '149/40'],
     ['deny', '3473/1000'],
     ['deny', '3347/1000'],
     ['deny', '83/25'],
     ['deny', '3047/1000'],
     ['allow', '939/250'],
     ['deny', '171/50'],
     ['deny', '3357/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 31], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1252, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '499/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2602, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3502, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1602, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '1097/500'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 402, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '199/40'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 284, 685, 716, 946, 1419, 1442, 1550, 1788, 1900, 2219, 2384, 2628, 2704],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['allow', '831/250'],
     ['deny', '404/125'],
     ['allow', '19/5'],
     ['allow', '481/125'],
     ['deny', '17/5'],
     ['allow', '3343/1000'],
     ['allow', '481/125'],
     ['deny', '779/250'],
     ['allow', '486/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 32], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1253, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '997/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2603, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3503, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1603, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2191/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 403, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '397/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [88, 165, 511, 523, 538, 1193, 1202, 1389, 1722, 1826, 2373, 2548, 2774, 2968],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['deny', '807/250'],
     ['deny', '399/125'],
     ['allow', '861/250'],
     ['allow', '389/125'],
     ['allow', '462/125'],
     ['allow', '2881/1000'],
     ['allow', '839/250'],
     ['allow', '1839/500'],
     ['deny', '387/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 33], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1254, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '498/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2604, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3504, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1604, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '547/250'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 404, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '99/20'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [113, 180, 253, 634, 1224, 1448, 1496, 1722, 1887, 2254, 2425, 2792, 2877, 2945],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '388/125'],
     ['allow', '401/125'],
     ['deny', '377/125'],
     ['allow', '389/125'],
     ['allow', '863/250'],
     ['allow', '1619/500'],
     ['allow', '149/40'],
     ['allow', '453/125'],
     ['deny', '3369/1000'],
     ['deny', '633/200']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 34], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1255, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '199/50'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2605, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3505, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1605, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '437/200'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 405, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '79/16'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [237, 850, 1324, 1370, 1559, 1744, 1852, 2112, 2117, 2141, 2288, 2346, 2510, 2979],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '294/125'],
     ['allow', '163/50'],
     ['allow', '1941/500'],
     ['deny', '439/125'],
     ['deny', '412/125'],
     ['allow', '458/125'],
     ['deny', '3649/1000'],
     ['deny', '3577/1000'],
     ['deny', '392/125'],
     ['allow', '1981/500'],
     ['deny', '347/100'],
     ['allow', '3063/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 35], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    L = x['limit']
    W = x['window_ms']
    idx, prev, cur = 0, 0, 0
    out = []
    for t in x['requests']:
        ci = t // W
        if ci == idx + 1:
            prev, cur = cur, 0
        elif ci > idx + 1:
            cur = 0
        idx = ci
        elapsed = t - idx * W
        est = prev * Fraction(W - elapsed, W) + cur
        if est + 1 <= L:
            cur += 1
            out.append(['allow', str(est + 1)])
        else:
            out.append(['deny', str(est)])
    return [out, [idx, prev, cur]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1251, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '999/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2601, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3501, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1601, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2197/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 401, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '399/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [762, 1183, 1614, 1772, 2334, 2411, 2425, 2509, 2551, 2560, 2651, 2748, 2860, 2881],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '1817/1000'],
     ['allow', '1193/500'],
     ['allow', '807/250'],
     ['allow', '1499/500'],
     ['allow', '3767/1000'],
     ['deny', '149/40'],
     ['deny', '3473/1000'],
     ['deny', '3347/1000'],
     ['deny', '83/25'],
     ['deny', '3047/1000'],
     ['allow', '939/250'],
     ['deny', '171/50'],
     ['deny', '3357/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 31], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1252, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '499/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2602, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3502, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1602, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '1097/500'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 402, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '199/40'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 284, 685, 716, 946, 1419, 1442, 1550, 1788, 1900, 2219, 2384, 2628, 2704],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['allow', '831/250'],
     ['deny', '404/125'],
     ['allow', '19/5'],
     ['allow', '481/125'],
     ['deny', '17/5'],
     ['allow', '3343/1000'],
     ['allow', '481/125'],
     ['deny', '779/250'],
     ['allow', '486/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 32], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1253, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '997/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2603, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3503, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1603, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2191/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 403, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '397/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [88, 165, 511, 523, 538, 1193, 1202, 1389, 1722, 1826, 2373, 2548, 2774, 2968],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['deny', '807/250'],
     ['deny', '399/125'],
     ['allow', '861/250'],
     ['allow', '389/125'],
     ['allow', '462/125'],
     ['allow', '2881/1000'],
     ['allow', '839/250'],
     ['allow', '1839/500'],
     ['deny', '387/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 33], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1254, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '498/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2604, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3504, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1604, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '547/250'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 404, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '99/20'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [113, 180, 253, 634, 1224, 1448, 1496, 1722, 1887, 2254, 2425, 2792, 2877, 2945],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '388/125'],
     ['allow', '401/125'],
     ['deny', '377/125'],
     ['allow', '389/125'],
     ['allow', '863/250'],
     ['allow', '1619/500'],
     ['allow', '149/40'],
     ['allow', '453/125'],
     ['deny', '3369/1000'],
     ['deny', '633/200']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 34], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1255, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '199/50'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2605, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3505, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1605, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '437/200'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 405, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '79/16'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [237, 850, 1324, 1370, 1559, 1744, 1852, 2112, 2117, 2141, 2288, 2346, 2510, 2979],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '294/125'],
     ['allow', '163/50'],
     ['allow', '1941/500'],
     ['deny', '439/125'],
     ['deny', '412/125'],
     ['allow', '458/125'],
     ['deny', '3649/1000'],
     ['deny', '3577/1000'],
     ['deny', '392/125'],
     ['allow', '1981/500'],
     ['deny', '347/100'],
     ['allow', '3063/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 35], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
After an idle gap an old window's traffic still throttles the client.

Input {limit, window_ms, requests [t]} with nondecreasing t. Keep counts for the current and previous epoch windows; moving to the next window rotates cur into prev, skipping more than one window clears both. The estimate is prev * (W - elapsed)/W + cur with elapsed = t - window start, exactly. Allow when est + 1 <= limit (reporting est + 1), else deny (reporting est). Return [[decision, estimate as fraction string]], [window, prev, cur]].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    L = x['limit']
    W = x['window_ms']
    idx, prev, cur = 0, 0, 0
    out = []
    for t in x['requests']:
        ci = t // W
        if ci == idx + 1:
            prev, cur = cur, 0
        elif ci > idx + 1:
            prev, cur = 0, 0
        idx = ci
        elapsed = t - idx * W
        est = prev * Fraction(W - elapsed, W) + cur
        if est < L:
            cur += 1
            out.append(['allow', str(est + 1)])
        else:
            out.append(['deny', str(est)])
    return [out, [idx, prev, cur]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1251, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '999/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2601, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3501, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1601, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2197/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 401, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '399/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [762, 1183, 1614, 1772, 2334, 2411, 2425, 2509, 2551, 2560, 2651, 2748, 2860, 2881],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '1817/1000'],
     ['allow', '1193/500'],
     ['allow', '807/250'],
     ['allow', '1499/500'],
     ['allow', '3767/1000'],
     ['deny', '149/40'],
     ['deny', '3473/1000'],
     ['deny', '3347/1000'],
     ['deny', '83/25'],
     ['deny', '3047/1000'],
     ['allow', '939/250'],
     ['deny', '171/50'],
     ['deny', '3357/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 31], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1252, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '499/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2602, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3502, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1602, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '1097/500'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 402, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '199/40'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 284, 685, 716, 946, 1419, 1442, 1550, 1788, 1900, 2219, 2384, 2628, 2704],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['allow', '831/250'],
     ['deny', '404/125'],
     ['allow', '19/5'],
     ['allow', '481/125'],
     ['deny', '17/5'],
     ['allow', '3343/1000'],
     ['allow', '481/125'],
     ['deny', '779/250'],
     ['allow', '486/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 32], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1253, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '997/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2603, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3503, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1603, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2191/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 403, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '397/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [88, 165, 511, 523, 538, 1193, 1202, 1389, 1722, 1826, 2373, 2548, 2774, 2968],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['deny', '807/250'],
     ['deny', '399/125'],
     ['allow', '861/250'],
     ['allow', '389/125'],
     ['allow', '462/125'],
     ['allow', '2881/1000'],
     ['allow', '839/250'],
     ['allow', '1839/500'],
     ['deny', '387/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 33], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1254, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '498/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2604, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3504, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1604, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '547/250'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 404, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '99/20'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [113, 180, 253, 634, 1224, 1448, 1496, 1722, 1887, 2254, 2425, 2792, 2877, 2945],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '388/125'],
     ['allow', '401/125'],
     ['deny', '377/125'],
     ['allow', '389/125'],
     ['allow', '863/250'],
     ['allow', '1619/500'],
     ['allow', '149/40'],
     ['allow', '453/125'],
     ['deny', '3369/1000'],
     ['deny', '633/200']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 34], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1255, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '199/50'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2605, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3505, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1605, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '437/200'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 405, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '79/16'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [237, 850, 1324, 1370, 1559, 1744, 1852, 2112, 2117, 2141, 2288, 2346, 2510, 2979],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '294/125'],
     ['allow', '163/50'],
     ['allow', '1941/500'],
     ['deny', '439/125'],
     ['deny', '412/125'],
     ['allow', '458/125'],
     ['deny', '3649/1000'],
     ['deny', '3577/1000'],
     ['deny', '392/125'],
     ['allow', '1981/500'],
     ['deny', '347/100'],
     ['allow', '3063/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 35], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    L = x['limit']
    W = x['window_ms']
    idx, prev, cur = 0, 0, 0
    out = []
    for t in x['requests']:
        ci = t // W
        if ci == idx + 1:
            prev, cur = cur, 0
        elif ci > idx + 1:
            prev, cur = 0, 0
        idx = ci
        elapsed = t - idx * W
        est = prev * Fraction(W - elapsed, W) + cur
        if est + 1 < L:
            cur += 1
            out.append(['allow', str(est + 1)])
        else:
            out.append(['deny', str(est)])
    return [out, [idx, prev, cur]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1251, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '999/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2601, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3501, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1601, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2197/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 401, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '399/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [762, 1183, 1614, 1772, 2334, 2411, 2425, 2509, 2551, 2560, 2651, 2748, 2860, 2881],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '1817/1000'],
     ['allow', '1193/500'],
     ['allow', '807/250'],
     ['allow', '1499/500'],
     ['allow', '3767/1000'],
     ['deny', '149/40'],
     ['deny', '3473/1000'],
     ['deny', '3347/1000'],
     ['deny', '83/25'],
     ['deny', '3047/1000'],
     ['allow', '939/250'],
     ['deny', '171/50'],
     ['deny', '3357/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 31], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1252, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '499/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2602, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3502, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1602, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '1097/500'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 402, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '199/40'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 284, 685, 716, 946, 1419, 1442, 1550, 1788, 1900, 2219, 2384, 2628, 2704],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['allow', '831/250'],
     ['deny', '404/125'],
     ['allow', '19/5'],
     ['allow', '481/125'],
     ['deny', '17/5'],
     ['allow', '3343/1000'],
     ['allow', '481/125'],
     ['deny', '779/250'],
     ['allow', '486/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 32], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1253, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '997/250'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2603, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3503, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1603, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '2191/1000'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 403, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '397/80'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [88, 165, 511, 523, 538, 1193, 1202, 1389, 1722, 1826, 2373, 2548, 2774, 2968],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '4'],
     ['deny', '807/250'],
     ['deny', '399/125'],
     ['allow', '861/250'],
     ['allow', '389/125'],
     ['allow', '462/125'],
     ['allow', '2881/1000'],
     ['allow', '839/250'],
     ['allow', '1839/500'],
     ['deny', '387/125']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 33], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1254, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '498/125'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2604, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3504, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1604, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '547/250'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 404, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '99/20'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [113, 180, 253, 634, 1224, 1448, 1496, 1722, 1887, 2254, 2425, 2792, 2877, 2945],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['deny', '388/125'],
     ['allow', '401/125'],
     ['deny', '377/125'],
     ['allow', '389/125'],
     ['allow', '863/250'],
     ['allow', '1619/500'],
     ['allow', '149/40'],
     ['allow', '453/125'],
     ['deny', '3369/1000'],
     ['deny', '633/200']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 34], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]],
 [['previous window weighting',
   {'limit': 4, 'requests': [100, 200, 300, 400, 1255, 1500, 1750, 1800], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '199/50'],
     ['allow', '4'],
     ['allow', '4'],
     ['deny', '19/5']],
    [1, 4, 3]]],
  ['gap clears history',
   {'limit': 3, 'requests': [0, 1, 2, 2605, 2700, 2800, 2900], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['deny', '3']],
    [2, 0, 3]]],
  ['stale previous after gap',
   {'limit': 3, 'requests': [100, 200, 1100, 1200, 3505, 3600, 3700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '14/5'],
     ['deny', '13/5'],
     ['allow', '1'],
     ['allow', '2'],
     ['allow', '3']],
    [3, 0, 3]]],
  ['fractional estimate boundary',
   {'limit': 3, 'requests': [0, 10, 20, 1500, 1605, 1700], 'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '5/2'],
     ['deny', '437/200'],
     ['allow', '29/10']],
    [1, 3, 2]]],
  ['early in window',
   {'limit': 5, 'requests': [0, 50, 100, 150, 200, 405, 410, 420, 800, 801], 'window_ms': 400},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '3'],
     ['allow', '4'],
     ['allow', '5'],
     ['deny', '79/16'],
     ['deny', '39/8'],
     ['deny', '19/4'],
     ['allow', '1'],
     ['allow', '2']],
    [2, 0, 2]]],
  ['random traffic',
   {'limit': 4,
    'requests': [237, 850, 1324, 1370, 1559, 1744, 1852, 2112, 2117, 2141, 2288, 2346, 2510, 2979],
    'window_ms': 1000},
   [[['allow', '1'],
     ['allow', '2'],
     ['allow', '294/125'],
     ['allow', '163/50'],
     ['allow', '1941/500'],
     ['deny', '439/125'],
     ['deny', '412/125'],
     ['allow', '458/125'],
     ['deny', '3649/1000'],
     ['deny', '3577/1000'],
     ['deny', '392/125'],
     ['allow', '1981/500'],
     ['deny', '347/100'],
     ['allow', '3063/1000']],
    [2, 3, 3]]],
  ['single window',
   {'limit': 2, 'requests': [10, 20, 35], 'window_ms': 1000},
   [[['allow', '1'], ['allow', '2'], ['deny', '2']], [0, 0, 2]]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
An estimate of 3.5 against a limit of 4 is admitted, pushing the rolling rate over the limit.

Input {limit, window_ms, requests [t]} with nondecreasing t. Keep counts for the current and previous epoch windows; moving to the next window rotates cur into prev, skipping more than one window clears both. The estimate is prev * (W - elapsed)/W + cur with elapsed = t - window start, exactly. Allow when est + 1 <= limit (reporting est + 1), else deny (reporting est). Return [[decision, estimate as fraction string]], [window, prev, cur]].

split: open-access