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

N = 1
observations = []
def solve(x):
    N = x['slots']
    B = x['slot_ms']
    lim = x['limit']
    cnt = [0] * N
    ep = [-1] * N
    out = []
    for t in x['requests']:
        e = t // B
        s = e % N
        ep[s] = e
        total = sum(cnt[i] for i in range(N) if e - N < ep[i] <= e)
        if total < lim:
            cnt[s] += 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, cnt, ep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 401, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 501, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5001, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 252, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 201, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [46, 120, 415, 554, 645, 818, 865, 1373, 1525, 1554, 1664, 1801, 1833, 1867],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny'],
    [2, 1, 0, 1, 1],
    [15, 16, -1, 18, 4]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 402, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 502, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5002, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 253, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 202, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [98, 199, 284, 322, 376, 477, 477, 489, 1105, 1133, 1150, 1440, 1769, 1950],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 3, 1, 1, 1],
    [0, 11, 17, 3, 19]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 403, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 503, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5003, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 254, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 203, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [81, 356, 399, 715, 737, 761, 1248, 1286, 1450, 1484, 1518, 1539, 1635, 1691],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny'],
    [0, 0, 2, 2, 2],
    [15, 16, 12, 3, 14]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 404, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 504, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5004, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 255, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 204, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [39, 260, 414, 610, 686, 731, 892, 1075, 1107, 1491, 1496, 1594, 1832, 1860],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny'],
    [1, 1, 1, 1, 2],
    [15, 11, 7, 18, 14]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 405, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 505, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5005, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 256, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 205, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 79, 224, 260, 340, 480, 497, 648, 755, 916, 1103, 1554, 1762, 1944],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 1, 1, 0, 1],
    [15, 11, 17, 3, 19]]]]]
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

N = 1
observations = []
def solve(x):
    N = x['slots']
    B = x['slot_ms']
    lim = x['limit']
    cnt = [0] * N
    ep = [-1] * N
    out = []
    for t in x['requests']:
        e = t // B
        s = e % N
        if ep[s] != e and cnt[s] >= lim:
            cnt[s] = 0
        ep[s] = e
        total = sum(cnt[i] for i in range(N) if e - N < ep[i] <= e)
        if total < lim:
            cnt[s] += 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, cnt, ep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 401, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 501, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5001, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 252, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 201, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [46, 120, 415, 554, 645, 818, 865, 1373, 1525, 1554, 1664, 1801, 1833, 1867],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny'],
    [2, 1, 0, 1, 1],
    [15, 16, -1, 18, 4]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 402, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 502, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5002, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 253, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 202, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [98, 199, 284, 322, 376, 477, 477, 489, 1105, 1133, 1150, 1440, 1769, 1950],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 3, 1, 1, 1],
    [0, 11, 17, 3, 19]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 403, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 503, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5003, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 254, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 203, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [81, 356, 399, 715, 737, 761, 1248, 1286, 1450, 1484, 1518, 1539, 1635, 1691],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny'],
    [0, 0, 2, 2, 2],
    [15, 16, 12, 3, 14]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 404, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 504, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5004, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 255, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 204, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [39, 260, 414, 610, 686, 731, 892, 1075, 1107, 1491, 1496, 1594, 1832, 1860],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny'],
    [1, 1, 1, 1, 2],
    [15, 11, 7, 18, 14]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 405, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 505, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5005, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 256, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 205, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 79, 224, 260, 340, 480, 497, 648, 755, 916, 1103, 1554, 1762, 1944],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 1, 1, 0, 1],
    [15, 11, 17, 3, 19]]]]]
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:
Traffic from one full window ago is counted again when its slot comes around.

Input {slots N, slot_ms B, limit, requests [t]} with nondecreasing t. Epoch e = t div B maps to slot e mod N; each slot remembers the epoch it counts and is zeroed when reused for a newer epoch. The rolling total sums slots whose epoch lies in (e - N, e]. Admit while total < limit and count the request in the current slot. Return [decisions, slot counts, slot epochs].

split: open-access


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

N = 1
observations = []
def solve(x):
    N = x['slots']
    B = x['slot_ms']
    lim = x['limit']
    cnt = [0] * N
    ep = [-1] * N
    out = []
    for t in x['requests']:
        e = t // B
        s = e % N
        if ep[s] != e:
            ep[s] = e
            cnt[s] = 0
        total = sum(cnt)
        if total < lim:
            cnt[s] += 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, cnt, ep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 401, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 501, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5001, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 252, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 201, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [46, 120, 415, 554, 645, 818, 865, 1373, 1525, 1554, 1664, 1801, 1833, 1867],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny'],
    [2, 1, 0, 1, 1],
    [15, 16, -1, 18, 4]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 402, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 502, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5002, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 253, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 202, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [98, 199, 284, 322, 376, 477, 477, 489, 1105, 1133, 1150, 1440, 1769, 1950],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 3, 1, 1, 1],
    [0, 11, 17, 3, 19]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 403, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 503, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5003, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 254, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 203, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [81, 356, 399, 715, 737, 761, 1248, 1286, 1450, 1484, 1518, 1539, 1635, 1691],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny'],
    [0, 0, 2, 2, 2],
    [15, 16, 12, 3, 14]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 404, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 504, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5004, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 255, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 204, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [39, 260, 414, 610, 686, 731, 892, 1075, 1107, 1491, 1496, 1594, 1832, 1860],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny'],
    [1, 1, 1, 1, 2],
    [15, 11, 7, 18, 14]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 405, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 505, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5005, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 256, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 205, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 79, 224, 260, 340, 480, 497, 648, 755, 916, 1103, 1554, 1762, 1944],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 1, 1, 0, 1],
    [15, 11, 17, 3, 19]]]]]
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

N = 1
observations = []
def solve(x):
    N = x['slots']
    B = x['slot_ms']
    lim = x['limit']
    cnt = [0] * N
    ep = [-1] * N
    out = []
    for t in x['requests']:
        e = t // B
        s = e % N
        if ep[s] != e:
            ep[s] = e
            cnt[s] = 0
        total = sum(cnt[i] for i in range(N) if e - N // 2 <= ep[i] <= e)
        if total < lim:
            cnt[s] += 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, cnt, ep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 401, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 501, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5001, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 252, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 201, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [46, 120, 415, 554, 645, 818, 865, 1373, 1525, 1554, 1664, 1801, 1833, 1867],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny'],
    [2, 1, 0, 1, 1],
    [15, 16, -1, 18, 4]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 402, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 502, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5002, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 253, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 202, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [98, 199, 284, 322, 376, 477, 477, 489, 1105, 1133, 1150, 1440, 1769, 1950],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 3, 1, 1, 1],
    [0, 11, 17, 3, 19]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 403, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 503, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5003, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 254, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 203, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [81, 356, 399, 715, 737, 761, 1248, 1286, 1450, 1484, 1518, 1539, 1635, 1691],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny'],
    [0, 0, 2, 2, 2],
    [15, 16, 12, 3, 14]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 404, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 504, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5004, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 255, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 204, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [39, 260, 414, 610, 686, 731, 892, 1075, 1107, 1491, 1496, 1594, 1832, 1860],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny'],
    [1, 1, 1, 1, 2],
    [15, 11, 7, 18, 14]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 405, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 505, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5005, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 256, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 205, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 79, 224, 260, 340, 480, 497, 648, 755, 916, 1103, 1554, 1762, 1944],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 1, 1, 0, 1],
    [15, 11, 17, 3, 19]]]]]
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 period, slots from long ago still count toward the limit.

Input {slots N, slot_ms B, limit, requests [t]} with nondecreasing t. Epoch e = t div B maps to slot e mod N; each slot remembers the epoch it counts and is zeroed when reused for a newer epoch. The rolling total sums slots whose epoch lies in (e - N, e]. Admit while total < limit and count the request in the current slot. Return [decisions, slot counts, slot epochs].

split: open-access


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

N = 1
observations = []
def solve(x):
    N = x['slots']
    B = x['slot_ms']
    lim = x['limit']
    cnt = [0] * N
    ep = [-1] * N
    out = []
    for t in x['requests']:
        e = t // B
        s = t % N
        if ep[s] != e:
            ep[s] = e
            cnt[s] = 0
        total = sum(cnt[i] for i in range(N) if e - N < ep[i] <= e)
        if total < lim:
            cnt[s] += 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, cnt, ep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 401, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 501, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5001, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 252, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 201, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [46, 120, 415, 554, 645, 818, 865, 1373, 1525, 1554, 1664, 1801, 1833, 1867],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny'],
    [2, 1, 0, 1, 1],
    [15, 16, -1, 18, 4]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 402, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 502, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5002, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 253, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 202, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [98, 199, 284, 322, 376, 477, 477, 489, 1105, 1133, 1150, 1440, 1769, 1950],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 3, 1, 1, 1],
    [0, 11, 17, 3, 19]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 403, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 503, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5003, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 254, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 203, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [81, 356, 399, 715, 737, 761, 1248, 1286, 1450, 1484, 1518, 1539, 1635, 1691],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny'],
    [0, 0, 2, 2, 2],
    [15, 16, 12, 3, 14]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 404, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 504, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5004, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 255, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 204, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [39, 260, 414, 610, 686, 731, 892, 1075, 1107, 1491, 1496, 1594, 1832, 1860],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny'],
    [1, 1, 1, 1, 2],
    [15, 11, 7, 18, 14]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 405, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 505, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5005, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 256, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 205, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 79, 224, 260, 340, 480, 497, 648, 755, 916, 1103, 1554, 1762, 1944],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 1, 1, 0, 1],
    [15, 11, 17, 3, 19]]]]]
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

N = 1
observations = []
def solve(x):
    N = x['slots']
    B = x['slot_ms']
    lim = x['limit']
    cnt = [0] * N
    ep = [-1] * N
    out = []
    for t in x['requests']:
        e = t // B
        s = e % (N - 1)
        if ep[s] != e:
            ep[s] = e
            cnt[s] = 0
        total = sum(cnt[i] for i in range(N) if e - N < ep[i] <= e)
        if total < lim:
            cnt[s] += 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, cnt, ep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 401, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 501, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5001, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 252, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 201, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [46, 120, 415, 554, 645, 818, 865, 1373, 1525, 1554, 1664, 1801, 1833, 1867],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny'],
    [2, 1, 0, 1, 1],
    [15, 16, -1, 18, 4]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 402, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 502, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5002, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 253, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 202, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [98, 199, 284, 322, 376, 477, 477, 489, 1105, 1133, 1150, 1440, 1769, 1950],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 3, 1, 1, 1],
    [0, 11, 17, 3, 19]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 403, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 503, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5003, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 254, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 203, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [81, 356, 399, 715, 737, 761, 1248, 1286, 1450, 1484, 1518, 1539, 1635, 1691],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny'],
    [0, 0, 2, 2, 2],
    [15, 16, 12, 3, 14]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 404, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 504, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5004, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 255, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 204, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [39, 260, 414, 610, 686, 731, 892, 1075, 1107, 1491, 1496, 1594, 1832, 1860],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny'],
    [1, 1, 1, 1, 2],
    [15, 11, 7, 18, 14]]]],
 [['slot reused after a lap',
   {'limit': 3, 'requests': [0, 10, 20, 405, 410, 420, 430], 'slot_ms': 100, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],
  ['old slots leave the window',
   {'limit': 4, 'requests': [0, 100, 200, 300, 505, 610, 620, 630], 'slot_ms': 100, 'slots': 5},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],
    [1, 1, 1, 1, 0],
    [5, 6, 2, 3, -1]]],
  ['long idle gap',
   {'limit': 2, 'requests': [0, 250, 5005, 5010, 5020], 'slot_ms': 200, 'slots': 3},
   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],
  ['slot index uses epoch',
   {'limit': 5, 'requests': [0, 1, 2, 3, 256, 252, 503, 999], 'slot_ms': 250, 'slots': 4},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],
    [4, 1, 0, 0],
    [0, 1, 2, 3]]],
  ['partial saturation reuse',
   {'limit': 5, 'requests': [0, 1, 150, 205, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],
  ['random traffic',
   {'limit': 4,
    'requests': [2, 79, 224, 260, 340, 480, 497, 648, 755, 916, 1103, 1554, 1762, 1944],
    'slot_ms': 100,
    'slots': 5},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 1, 1, 0, 1],
    [15, 11, 17, 3, 19]]]]]
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:
Requests in the same sub-window scatter across slots and reset each other.

Input {slots N, slot_ms B, limit, requests [t]} with nondecreasing t. Epoch e = t div B maps to slot e mod N; each slot remembers the epoch it counts and is zeroed when reused for a newer epoch. The rolling total sums slots whose epoch lies in (e - N, e]. Admit while total < limit and count the request in the current slot. Return [decisions, slot counts, slot epochs].

split: open-access


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

N = 1
observations = []
def solve(x):
    ls, lm = x['per_second'], x['per_minute']
    sw = mw = None
    sc = mc = 0
    out = []
    for t in x['requests']:
        s, m = t // 1000, t // 60000
        if s != sw:
            sw, sc = s, 0
            mw, mc = m, 0
        if sc >= ls:
            out.append('deny-second')
        elif mc >= lm:
            out.append('deny-minute')
        else:
            sc += 1
            mc += 1
            out.append('allow')
    return [out, sc, mc]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3001, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1001, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60001, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1001, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2003, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [1062,
                 8418,
                 9273,
                 34515,
                 47777,
                 65888,
                 67598,
                 89351,
                 103730,
                 110167,
                 110678,
                 120637,
                 122553,
                 128547]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    3]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3002, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1002, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60002, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1002, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2004, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [4406,
                 11048,
                 15610,
                 37272,
                 37553,
                 45326,
                 49676,
                 64905,
                 66877,
                 80916,
                 104479,
                 105515,
                 113188,
                 115762]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3003, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1003, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60003, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1003, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2005, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [12496,
                 13001,
                 16785,
                 17435,
                 41410,
                 44765,
                 45872,
                 51289,
                 69195,
                 73570,
                 101381,
                 106192,
                 110461,
                 126847]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3004, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1004, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60004, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1004, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2006, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [35872,
                 47171,
                 57795,
                 66404,
                 69658,
                 83185,
                 86836,
                 87855,
                 88307,
                 96707,
                 97802,
                 102613,
                 119928,
                 129412]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3005, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1005, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60005, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1005, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2007, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [2584,
                 8339,
                 26804,
                 29473,
                 39448,
                 51111,
                 57796,
                 65951,
                 70268,
                 73982,
                 76067,
                 80339,
                 81264,
                 102821]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]]]
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

N = 1
observations = []
def solve(x):
    ls, lm = x['per_second'], x['per_minute']
    sw = mw = None
    sc = mc = 0
    out = []
    for t in x['requests']:
        s, m = t // 1000, t // 60000
        if m != mw:
            mw, mc = m, 0
            sw, sc = s, 0
        if sc >= ls:
            out.append('deny-second')
        elif mc >= lm:
            out.append('deny-minute')
        else:
            sc += 1
            mc += 1
            out.append('allow')
    return [out, sc, mc]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3001, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1001, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60001, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1001, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2003, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [1062,
                 8418,
                 9273,
                 34515,
                 47777,
                 65888,
                 67598,
                 89351,
                 103730,
                 110167,
                 110678,
                 120637,
                 122553,
                 128547]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    3]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3002, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1002, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60002, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1002, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2004, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [4406,
                 11048,
                 15610,
                 37272,
                 37553,
                 45326,
                 49676,
                 64905,
                 66877,
                 80916,
                 104479,
                 105515,
                 113188,
                 115762]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3003, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1003, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60003, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1003, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2005, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [12496,
                 13001,
                 16785,
                 17435,
                 41410,
                 44765,
                 45872,
                 51289,
                 69195,
                 73570,
                 101381,
                 106192,
                 110461,
                 126847]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3004, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1004, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60004, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1004, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2006, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [35872,
                 47171,
                 57795,
                 66404,
                 69658,
                 83185,
                 86836,
                 87855,
                 88307,
                 96707,
                 97802,
                 102613,
                 119928,
                 129412]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3005, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1005, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60005, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1005, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2007, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [2584,
                 8339,
                 26804,
                 29473,
                 39448,
                 51111,
                 57796,
                 65951,
                 70268,
                 73982,
                 76067,
                 80339,
                 81264,
                 102821]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]]]
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 per-minute limit is never reached because it is cleared whenever a new second starts.

Input {per_second, per_minute, requests [t_ms]} with nondecreasing t. Second windows are t div 1000 and minute windows t div 60000, each resetting its own counter only when its own window changes. The second limit is checked first ("deny-second"), then the minute limit ("deny-minute"); only admitted requests are counted, in both windows. Return [decisions, second count, minute count].

split: open-access


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

N = 1
observations = []
def solve(x):
    ls, lm = x['per_second'], x['per_minute']
    sw = mw = None
    sc = mc = 0
    out = []
    for t in x['requests']:
        s, m = t // 1000, t // 60000
        if s != sw:
            sw, sc = s, 0
        if m != mw:
            mw, mc = m, 0
        if sc >= ls:
            out.append('deny-second')
        elif mc >= lm:
            sc += 1
            out.append('deny-minute')
        else:
            sc += 1
            mc += 1
            out.append('allow')
    return [out, sc, mc]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3001, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1001, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60001, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1001, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2003, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [1062,
                 8418,
                 9273,
                 34515,
                 47777,
                 65888,
                 67598,
                 89351,
                 103730,
                 110167,
                 110678,
                 120637,
                 122553,
                 128547]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    3]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3002, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1002, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60002, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1002, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2004, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [4406,
                 11048,
                 15610,
                 37272,
                 37553,
                 45326,
                 49676,
                 64905,
                 66877,
                 80916,
                 104479,
                 105515,
                 113188,
                 115762]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3003, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1003, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60003, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1003, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2005, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [12496,
                 13001,
                 16785,
                 17435,
                 41410,
                 44765,
                 45872,
                 51289,
                 69195,
                 73570,
                 101381,
                 106192,
                 110461,
                 126847]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3004, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1004, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60004, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1004, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2006, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [35872,
                 47171,
                 57795,
                 66404,
                 69658,
                 83185,
                 86836,
                 87855,
                 88307,
                 96707,
                 97802,
                 102613,
                 119928,
                 129412]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3005, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1005, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60005, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1005, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2007, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [2584,
                 8339,
                 26804,
                 29473,
                 39448,
                 51111,
                 57796,
                 65951,
                 70268,
                 73982,
                 76067,
                 80339,
                 81264,
                 102821]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]]]
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

N = 1
observations = []
def solve(x):
    ls, lm = x['per_second'], x['per_minute']
    sw = mw = None
    sc = mc = 0
    out = []
    for t in x['requests']:
        s, m = t // 1000, t // 60000
        if s != sw:
            sw, sc = s, 0
        if m != mw:
            mw, mc = m, 0
        if sc >= ls:
            out.append('deny-second')
        elif mc >= lm:
            mc += 1
            out.append('deny-minute')
        else:
            sc += 1
            mc += 1
            out.append('allow')
    return [out, sc, mc]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3001, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1001, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60001, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1001, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2003, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [1062,
                 8418,
                 9273,
                 34515,
                 47777,
                 65888,
                 67598,
                 89351,
                 103730,
                 110167,
                 110678,
                 120637,
                 122553,
                 128547]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    3]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3002, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1002, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60002, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1002, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2004, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [4406,
                 11048,
                 15610,
                 37272,
                 37553,
                 45326,
                 49676,
                 64905,
                 66877,
                 80916,
                 104479,
                 105515,
                 113188,
                 115762]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3003, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1003, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60003, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1003, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2005, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [12496,
                 13001,
                 16785,
                 17435,
                 41410,
                 44765,
                 45872,
                 51289,
                 69195,
                 73570,
                 101381,
                 106192,
                 110461,
                 126847]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3004, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1004, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60004, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1004, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2006, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [35872,
                 47171,
                 57795,
                 66404,
                 69658,
                 83185,
                 86836,
                 87855,
                 88307,
                 96707,
                 97802,
                 102613,
                 119928,
                 129412]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow'],
    1,
    1]]],
 [['minute budget spans seconds',
   {'per_minute': 5, 'per_second': 2, 'requests': [0, 1, 1000, 1001, 2000, 2001, 3005, 59999]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny-minute', 'deny-minute', 'deny-minute'],
    0,
    5]],
  ['second limit inside minute',
   {'per_minute': 10, 'per_second': 1, 'requests': [0, 10, 20, 1005, 1010]},
   [['allow', 'deny-second', 'deny-second', 'allow', 'deny-second'], 1, 2]],
  ['minute rollover',
   {'per_minute': 3, 'per_second': 3, 'requests': [59000, 59001, 59002, 59500, 60005, 60001]},
   [['allow', 'allow', 'allow', 'deny-second', 'allow', 'allow'], 2, 2]],
  ['both exhausted reports second',
   {'per_minute': 1, 'per_second': 1, 'requests': [0, 1, 1005, 1001]},
   [['allow', 'deny-second', 'deny-minute', 'deny-minute'], 0, 1]],
  ['minute denials keep second budget',
   {'per_minute': 2, 'per_second': 2, 'requests': [0, 1000, 2000, 2001, 2007, 60000, 60001, 60002]},
   [['allow',
     'allow',
     'deny-minute',
     'deny-minute',
     'deny-minute',
     'allow',
     'allow',
     'deny-second'],
    2,
    2]],
  ['random traffic',
   {'per_minute': 6,
    'per_second': 2,
    'requests': [2584,
                 8339,
                 26804,
                 29473,
                 39448,
                 51111,
                 57796,
                 65951,
                 70268,
                 73982,
                 76067,
                 80339,
                 81264,
                 102821]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny-minute'],
    0,
    6]]]]
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:
Requests rejected by the minute limit also exhaust the per-second allowance.

Input {per_second, per_minute, requests [t_ms]} with nondecreasing t. Second windows are t div 1000 and minute windows t div 60000, each resetting its own counter only when its own window changes. The second limit is checked first ("deny-second"), then the minute limit ("deny-minute"); only admitted requests are counted, in both windows. Return [decisions, second count, minute count].

split: open-access