broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    C = x['capacity']
    rate = x['rate']
    tokens = Fraction(C)
    last = 0
    out = []
    for t, cost in x['requests']:
        elapsed = max(0, t - last)
        tokens = min(Fraction(C), tokens + Fraction(elapsed * rate, 1000))
        last = max(last, t)
        if tokens >= cost:
            tokens -= cost
            out.append(['allow', 0])
        else:
            out.append(['deny', math.ceil((cost - tokens) * 1000 / rate)])
    return [out, str(tokens)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [100, 1], [1000, 2], [1401, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 400],
     ['allow', 0],
     ['deny', 99]],
    '401/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10001, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3100, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3710, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3001, 3], [3001, 5]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2334, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [901, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1025, 1],
                 [1038, 3],
                 [1399, 1],
                 [1944, 3],
                 [2745, 1],
                 [2753, 1],
                 [3169, 1],
                 [4025, 1],
                 [4086, 3],
                 [4305, 3]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 126],
     ['deny', 581],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 439],
     ['deny', 220]],
    '64/25']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [200, 1], [1000, 2], [1402, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 300],
     ['allow', 0],
     ['deny', 98]],
    '201/250']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10002, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 332], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3200, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3720, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3002, 3], [3002, 6]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2668, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '251/250']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [902, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '353/500']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[679, 3],
                 [889, 1],
                 [1479, 1],
                 [1523, 1],
                 [1681, 1],
                 [2074, 3],
                 [2401, 2],
                 [2669, 3],
                 [4187, 3],
                 [4538, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 156],
     ['allow', 0],
     ['deny', 1105],
     ['deny', 278],
     ['deny', 510],
     ['allow', 0],
     ['allow', 0]],
    '351/500']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [300, 1], [1000, 2], [1403, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 200],
     ['allow', 0],
     ['deny', 97]],
    '403/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10003, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 331], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3300, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3730, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3003, 3], [3003, 7]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3002, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1003/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [903, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '709/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[476, 2],
                 [1005, 3],
                 [1092, 1],
                 [1140, 2],
                 [2416, 2],
                 [2727, 2],
                 [3540, 3],
                 [3809, 1],
                 [3822, 1],
                 [4130, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 384],
     ['deny', 836],
     ['allow', 0],
     ['deny', 249],
     ['allow', 0],
     ['deny', 167],
     ['deny', 154],
     ['allow', 0]],
    '77/250']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [400, 1], [1000, 2], [1404, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 100],
     ['allow', 0],
     ['deny', 96]],
    '101/125']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10004, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 330], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3400, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3740, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3004, 3], [3004, 8]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3336, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '376/125']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [904, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '89/125']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[295, 3],
                 [481, 2],
                 [603, 2],
                 [1079, 3],
                 [1690, 3],
                 [1700, 3],
                 [2433, 3],
                 [3280, 3],
                 [4573, 3],
                 [4680, 3]]},
   [[['allow', 0],
     ['deny', 314],
     ['deny', 192],
     ['deny', 216],
     ['allow', 0],
     ['deny', 1095],
     ['deny', 362],
     ['allow', 0],
     ['allow', 0],
     ['deny', 1115]],
    '77/100']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [500, 1], [1000, 2], [1405, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 500],
     ['allow', 0]],
    '81/100']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10005, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 329], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3500, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3750, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3005, 3], [3005, 9]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3670, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '401/100']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [905, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '143/200']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1144, 3],
                 [1657, 3],
                 [1896, 3],
                 [2302, 2],
                 [2570, 2],
                 [3012, 1],
                 [3025, 1],
                 [3251, 1],
                 [4294, 1],
                 [4860, 2]]},
   [[['allow', 0],
     ['deny', 487],
     ['deny', 248],
     ['allow', 0],
     ['deny', 74],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0]],
    '54/125']]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    C = x['capacity']
    rate = x['rate']
    tokens = Fraction(C)
    last = 0
    out = []
    for t, cost in x['requests']:
        elapsed = max(0, t - last)
        tokens = min(Fraction(C), tokens + Fraction(elapsed * rate, 1000))
        last = max(last, t)
        if cost >= C:
            out.append(['never', 0])
        elif tokens >= cost:
            tokens -= cost
            out.append(['allow', 0])
        else:
            out.append(['deny', math.ceil((cost - tokens) * 1000 / rate)])
    return [out, str(tokens)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [100, 1], [1000, 2], [1401, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 400],
     ['allow', 0],
     ['deny', 99]],
    '401/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10001, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3100, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3710, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3001, 3], [3001, 5]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2334, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [901, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1025, 1],
                 [1038, 3],
                 [1399, 1],
                 [1944, 3],
                 [2745, 1],
                 [2753, 1],
                 [3169, 1],
                 [4025, 1],
                 [4086, 3],
                 [4305, 3]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 126],
     ['deny', 581],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 439],
     ['deny', 220]],
    '64/25']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [200, 1], [1000, 2], [1402, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 300],
     ['allow', 0],
     ['deny', 98]],
    '201/250']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10002, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 332], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3200, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3720, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3002, 3], [3002, 6]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2668, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '251/250']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [902, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '353/500']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[679, 3],
                 [889, 1],
                 [1479, 1],
                 [1523, 1],
                 [1681, 1],
                 [2074, 3],
                 [2401, 2],
                 [2669, 3],
                 [4187, 3],
                 [4538, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 156],
     ['allow', 0],
     ['deny', 1105],
     ['deny', 278],
     ['deny', 510],
     ['allow', 0],
     ['allow', 0]],
    '351/500']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [300, 1], [1000, 2], [1403, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 200],
     ['allow', 0],
     ['deny', 97]],
    '403/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10003, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 331], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3300, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3730, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3003, 3], [3003, 7]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3002, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1003/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [903, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '709/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[476, 2],
                 [1005, 3],
                 [1092, 1],
                 [1140, 2],
                 [2416, 2],
                 [2727, 2],
                 [3540, 3],
                 [3809, 1],
                 [3822, 1],
                 [4130, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 384],
     ['deny', 836],
     ['allow', 0],
     ['deny', 249],
     ['allow', 0],
     ['deny', 167],
     ['deny', 154],
     ['allow', 0]],
    '77/250']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [400, 1], [1000, 2], [1404, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 100],
     ['allow', 0],
     ['deny', 96]],
    '101/125']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10004, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 330], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3400, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3740, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3004, 3], [3004, 8]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3336, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '376/125']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [904, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '89/125']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[295, 3],
                 [481, 2],
                 [603, 2],
                 [1079, 3],
                 [1690, 3],
                 [1700, 3],
                 [2433, 3],
                 [3280, 3],
                 [4573, 3],
                 [4680, 3]]},
   [[['allow', 0],
     ['deny', 314],
     ['deny', 192],
     ['deny', 216],
     ['allow', 0],
     ['deny', 1095],
     ['deny', 362],
     ['allow', 0],
     ['allow', 0],
     ['deny', 1115]],
    '77/100']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [500, 1], [1000, 2], [1405, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 500],
     ['allow', 0]],
    '81/100']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10005, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 329], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3500, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3750, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3005, 3], [3005, 9]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3670, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '401/100']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [905, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '143/200']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1144, 3],
                 [1657, 3],
                 [1896, 3],
                 [2302, 2],
                 [2570, 2],
                 [3012, 1],
                 [3025, 1],
                 [3251, 1],
                 [4294, 1],
                 [4860, 2]]},
   [[['allow', 0],
     ['deny', 487],
     ['deny', 248],
     ['allow', 0],
     ['deny', 74],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0]],
    '54/125']]]]
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:
A request larger than the bucket is told to retry after a wait that can never be satisfied.

Input {capacity, rate (tokens per second), requests [[t_ms, cost]]}. The bucket starts full at t=0. At each request, elapsed = max(0, t - last); tokens = min(capacity, tokens + elapsed*rate/1000) in exact rational arithmetic; last = max(last, t) so a regressing clock neither drains nor re-credits. A cost above capacity can never succeed ("never"). Otherwise allow when tokens >= cost and deduct; else deny with wait = ceil((cost - tokens) * 1000 / rate) ms. Return [[decision, wait]], final tokens].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    C = x['capacity']
    rate = x['rate']
    tokens = Fraction(C)
    last = 0
    out = []
    for t, cost in x['requests']:
        elapsed = max(0, t - last)
        tokens = min(Fraction(C), tokens + Fraction(elapsed * rate, 1000))
        last = max(last, t)
        if cost > C:
            out.append(['never', 0])
        elif tokens >= cost:
            tokens -= cost
            out.append(['allow', 0])
        else:
            out.append(['deny', int((cost - tokens) * 1000 / rate)])
    return [out, str(tokens)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [100, 1], [1000, 2], [1401, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 400],
     ['allow', 0],
     ['deny', 99]],
    '401/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10001, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3100, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3710, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3001, 3], [3001, 5]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2334, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [901, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1025, 1],
                 [1038, 3],
                 [1399, 1],
                 [1944, 3],
                 [2745, 1],
                 [2753, 1],
                 [3169, 1],
                 [4025, 1],
                 [4086, 3],
                 [4305, 3]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 126],
     ['deny', 581],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 439],
     ['deny', 220]],
    '64/25']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [200, 1], [1000, 2], [1402, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 300],
     ['allow', 0],
     ['deny', 98]],
    '201/250']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10002, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 332], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3200, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3720, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3002, 3], [3002, 6]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2668, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '251/250']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [902, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '353/500']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[679, 3],
                 [889, 1],
                 [1479, 1],
                 [1523, 1],
                 [1681, 1],
                 [2074, 3],
                 [2401, 2],
                 [2669, 3],
                 [4187, 3],
                 [4538, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 156],
     ['allow', 0],
     ['deny', 1105],
     ['deny', 278],
     ['deny', 510],
     ['allow', 0],
     ['allow', 0]],
    '351/500']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [300, 1], [1000, 2], [1403, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 200],
     ['allow', 0],
     ['deny', 97]],
    '403/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10003, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 331], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3300, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3730, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3003, 3], [3003, 7]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3002, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1003/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [903, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '709/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[476, 2],
                 [1005, 3],
                 [1092, 1],
                 [1140, 2],
                 [2416, 2],
                 [2727, 2],
                 [3540, 3],
                 [3809, 1],
                 [3822, 1],
                 [4130, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 384],
     ['deny', 836],
     ['allow', 0],
     ['deny', 249],
     ['allow', 0],
     ['deny', 167],
     ['deny', 154],
     ['allow', 0]],
    '77/250']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [400, 1], [1000, 2], [1404, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 100],
     ['allow', 0],
     ['deny', 96]],
    '101/125']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10004, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 330], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3400, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3740, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3004, 3], [3004, 8]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3336, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '376/125']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [904, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '89/125']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[295, 3],
                 [481, 2],
                 [603, 2],
                 [1079, 3],
                 [1690, 3],
                 [1700, 3],
                 [2433, 3],
                 [3280, 3],
                 [4573, 3],
                 [4680, 3]]},
   [[['allow', 0],
     ['deny', 314],
     ['deny', 192],
     ['deny', 216],
     ['allow', 0],
     ['deny', 1095],
     ['deny', 362],
     ['allow', 0],
     ['allow', 0],
     ['deny', 1115]],
    '77/100']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [500, 1], [1000, 2], [1405, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 500],
     ['allow', 0]],
    '81/100']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10005, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 329], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3500, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3750, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3005, 3], [3005, 9]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3670, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '401/100']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [905, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '143/200']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1144, 3],
                 [1657, 3],
                 [1896, 3],
                 [2302, 2],
                 [2570, 2],
                 [3012, 1],
                 [3025, 1],
                 [3251, 1],
                 [4294, 1],
                 [4860, 2]]},
   [[['allow', 0],
     ['deny', 487],
     ['deny', 248],
     ['allow', 0],
     ['deny', 74],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0]],
    '54/125']]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    C = x['capacity']
    rate = x['rate']
    tokens = Fraction(C)
    last = 0
    out = []
    for t, cost in x['requests']:
        elapsed = max(0, t - last)
        tokens = min(Fraction(C), tokens + Fraction(elapsed * rate, 1000))
        last = max(last, t)
        if cost > C:
            out.append(['never', 0])
        elif tokens >= cost:
            tokens -= cost
            out.append(['allow', 0])
        else:
            out.append(['deny', math.ceil((cost - tokens) / rate) * 1000])
    return [out, str(tokens)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [100, 1], [1000, 2], [1401, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 400],
     ['allow', 0],
     ['deny', 99]],
    '401/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10001, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3100, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3710, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3001, 3], [3001, 5]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2334, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [901, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1025, 1],
                 [1038, 3],
                 [1399, 1],
                 [1944, 3],
                 [2745, 1],
                 [2753, 1],
                 [3169, 1],
                 [4025, 1],
                 [4086, 3],
                 [4305, 3]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 126],
     ['deny', 581],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 439],
     ['deny', 220]],
    '64/25']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [200, 1], [1000, 2], [1402, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 300],
     ['allow', 0],
     ['deny', 98]],
    '201/250']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10002, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 332], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3200, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3720, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3002, 3], [3002, 6]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2668, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '251/250']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [902, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '353/500']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[679, 3],
                 [889, 1],
                 [1479, 1],
                 [1523, 1],
                 [1681, 1],
                 [2074, 3],
                 [2401, 2],
                 [2669, 3],
                 [4187, 3],
                 [4538, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 156],
     ['allow', 0],
     ['deny', 1105],
     ['deny', 278],
     ['deny', 510],
     ['allow', 0],
     ['allow', 0]],
    '351/500']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [300, 1], [1000, 2], [1403, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 200],
     ['allow', 0],
     ['deny', 97]],
    '403/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10003, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 331], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3300, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3730, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3003, 3], [3003, 7]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3002, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1003/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [903, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '709/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[476, 2],
                 [1005, 3],
                 [1092, 1],
                 [1140, 2],
                 [2416, 2],
                 [2727, 2],
                 [3540, 3],
                 [3809, 1],
                 [3822, 1],
                 [4130, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 384],
     ['deny', 836],
     ['allow', 0],
     ['deny', 249],
     ['allow', 0],
     ['deny', 167],
     ['deny', 154],
     ['allow', 0]],
    '77/250']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [400, 1], [1000, 2], [1404, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 100],
     ['allow', 0],
     ['deny', 96]],
    '101/125']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10004, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 330], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3400, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3740, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3004, 3], [3004, 8]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3336, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '376/125']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [904, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '89/125']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[295, 3],
                 [481, 2],
                 [603, 2],
                 [1079, 3],
                 [1690, 3],
                 [1700, 3],
                 [2433, 3],
                 [3280, 3],
                 [4573, 3],
                 [4680, 3]]},
   [[['allow', 0],
     ['deny', 314],
     ['deny', 192],
     ['deny', 216],
     ['allow', 0],
     ['deny', 1095],
     ['deny', 362],
     ['allow', 0],
     ['allow', 0],
     ['deny', 1115]],
    '77/100']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [500, 1], [1000, 2], [1405, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 500],
     ['allow', 0]],
    '81/100']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10005, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 329], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3500, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3750, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3005, 3], [3005, 9]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3670, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '401/100']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [905, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '143/200']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1144, 3],
                 [1657, 3],
                 [1896, 3],
                 [2302, 2],
                 [2570, 2],
                 [3012, 1],
                 [3025, 1],
                 [3251, 1],
                 [4294, 1],
                 [4860, 2]]},
   [[['allow', 0],
     ['deny', 487],
     ['deny', 248],
     ['allow', 0],
     ['deny', 74],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0]],
    '54/125']]]]
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:
Clients that honour the advertised wait arrive a fraction of a millisecond early and are denied again.

Input {capacity, rate (tokens per second), requests [[t_ms, cost]]}. The bucket starts full at t=0. At each request, elapsed = max(0, t - last); tokens = min(capacity, tokens + elapsed*rate/1000) in exact rational arithmetic; last = max(last, t) so a regressing clock neither drains nor re-credits. A cost above capacity can never succeed ("never"). Otherwise allow when tokens >= cost and deduct; else deny with wait = ceil((cost - tokens) * 1000 / rate) ms. Return [[decision, wait]], final tokens].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    C = x['capacity']
    rate = x['rate']
    tokens = Fraction(C)
    last = 0
    out = []
    for t, cost in x['requests']:
        elapsed = max(0, t - last)
        tokens = min(Fraction(C), tokens + Fraction(elapsed * rate, 1000))
        last = max(last, t)
        if cost > C:
            out.append(['never', 0])
        elif tokens > cost:
            tokens -= cost
            out.append(['allow', 0])
        else:
            out.append(['deny', math.ceil((cost - tokens) * 1000 / rate)])
    return [out, str(tokens)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [100, 1], [1000, 2], [1401, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 400],
     ['allow', 0],
     ['deny', 99]],
    '401/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10001, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3100, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3710, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3001, 3], [3001, 5]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2334, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [901, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1025, 1],
                 [1038, 3],
                 [1399, 1],
                 [1944, 3],
                 [2745, 1],
                 [2753, 1],
                 [3169, 1],
                 [4025, 1],
                 [4086, 3],
                 [4305, 3]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 126],
     ['deny', 581],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 439],
     ['deny', 220]],
    '64/25']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [200, 1], [1000, 2], [1402, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 300],
     ['allow', 0],
     ['deny', 98]],
    '201/250']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10002, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 332], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3200, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3720, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3002, 3], [3002, 6]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2668, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '251/250']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [902, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '353/500']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[679, 3],
                 [889, 1],
                 [1479, 1],
                 [1523, 1],
                 [1681, 1],
                 [2074, 3],
                 [2401, 2],
                 [2669, 3],
                 [4187, 3],
                 [4538, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 156],
     ['allow', 0],
     ['deny', 1105],
     ['deny', 278],
     ['deny', 510],
     ['allow', 0],
     ['allow', 0]],
    '351/500']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [300, 1], [1000, 2], [1403, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 200],
     ['allow', 0],
     ['deny', 97]],
    '403/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10003, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 331], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3300, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3730, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3003, 3], [3003, 7]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3002, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1003/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [903, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '709/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[476, 2],
                 [1005, 3],
                 [1092, 1],
                 [1140, 2],
                 [2416, 2],
                 [2727, 2],
                 [3540, 3],
                 [3809, 1],
                 [3822, 1],
                 [4130, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 384],
     ['deny', 836],
     ['allow', 0],
     ['deny', 249],
     ['allow', 0],
     ['deny', 167],
     ['deny', 154],
     ['allow', 0]],
    '77/250']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [400, 1], [1000, 2], [1404, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 100],
     ['allow', 0],
     ['deny', 96]],
    '101/125']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10004, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 330], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3400, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3740, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3004, 3], [3004, 8]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3336, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '376/125']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [904, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '89/125']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[295, 3],
                 [481, 2],
                 [603, 2],
                 [1079, 3],
                 [1690, 3],
                 [1700, 3],
                 [2433, 3],
                 [3280, 3],
                 [4573, 3],
                 [4680, 3]]},
   [[['allow', 0],
     ['deny', 314],
     ['deny', 192],
     ['deny', 216],
     ['allow', 0],
     ['deny', 1095],
     ['deny', 362],
     ['allow', 0],
     ['allow', 0],
     ['deny', 1115]],
    '77/100']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [500, 1], [1000, 2], [1405, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 500],
     ['allow', 0]],
    '81/100']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10005, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 329], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3500, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3750, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3005, 3], [3005, 9]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3670, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '401/100']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [905, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '143/200']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1144, 3],
                 [1657, 3],
                 [1896, 3],
                 [2302, 2],
                 [2570, 2],
                 [3012, 1],
                 [3025, 1],
                 [3251, 1],
                 [4294, 1],
                 [4860, 2]]},
   [[['allow', 0],
     ['deny', 487],
     ['deny', 248],
     ['allow', 0],
     ['deny', 74],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0]],
    '54/125']]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    C = x['capacity']
    rate = x['rate']
    tokens = Fraction(C)
    last = 0
    out = []
    for t, cost in x['requests']:
        elapsed = max(0, t - last)
        tokens = min(Fraction(C), tokens + Fraction(elapsed * rate, 1000))
        last = max(last, t)
        if cost > C:
            out.append(['never', 0])
        elif round(tokens) >= cost:
            tokens -= cost
            out.append(['allow', 0])
        else:
            out.append(['deny', math.ceil((cost - tokens) * 1000 / rate)])
    return [out, str(tokens)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [100, 1], [1000, 2], [1401, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 400],
     ['allow', 0],
     ['deny', 99]],
    '401/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10001, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3100, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3710, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3001, 3], [3001, 5]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2334, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [901, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1025, 1],
                 [1038, 3],
                 [1399, 1],
                 [1944, 3],
                 [2745, 1],
                 [2753, 1],
                 [3169, 1],
                 [4025, 1],
                 [4086, 3],
                 [4305, 3]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 126],
     ['deny', 581],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 439],
     ['deny', 220]],
    '64/25']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [200, 1], [1000, 2], [1402, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 300],
     ['allow', 0],
     ['deny', 98]],
    '201/250']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10002, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 332], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3200, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3720, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3002, 3], [3002, 6]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2668, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '251/250']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [902, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '353/500']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[679, 3],
                 [889, 1],
                 [1479, 1],
                 [1523, 1],
                 [1681, 1],
                 [2074, 3],
                 [2401, 2],
                 [2669, 3],
                 [4187, 3],
                 [4538, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 156],
     ['allow', 0],
     ['deny', 1105],
     ['deny', 278],
     ['deny', 510],
     ['allow', 0],
     ['allow', 0]],
    '351/500']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [300, 1], [1000, 2], [1403, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 200],
     ['allow', 0],
     ['deny', 97]],
    '403/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10003, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 331], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3300, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3730, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3003, 3], [3003, 7]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3002, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1003/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [903, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '709/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[476, 2],
                 [1005, 3],
                 [1092, 1],
                 [1140, 2],
                 [2416, 2],
                 [2727, 2],
                 [3540, 3],
                 [3809, 1],
                 [3822, 1],
                 [4130, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 384],
     ['deny', 836],
     ['allow', 0],
     ['deny', 249],
     ['allow', 0],
     ['deny', 167],
     ['deny', 154],
     ['allow', 0]],
    '77/250']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [400, 1], [1000, 2], [1404, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 100],
     ['allow', 0],
     ['deny', 96]],
    '101/125']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10004, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 330], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3400, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3740, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3004, 3], [3004, 8]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3336, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '376/125']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [904, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '89/125']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[295, 3],
                 [481, 2],
                 [603, 2],
                 [1079, 3],
                 [1690, 3],
                 [1700, 3],
                 [2433, 3],
                 [3280, 3],
                 [4573, 3],
                 [4680, 3]]},
   [[['allow', 0],
     ['deny', 314],
     ['deny', 192],
     ['deny', 216],
     ['allow', 0],
     ['deny', 1095],
     ['deny', 362],
     ['allow', 0],
     ['allow', 0],
     ['deny', 1115]],
    '77/100']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [500, 1], [1000, 2], [1405, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 500],
     ['allow', 0]],
    '81/100']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10005, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 329], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3500, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3750, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3005, 3], [3005, 9]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3670, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '401/100']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [905, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '143/200']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1144, 3],
                 [1657, 3],
                 [1896, 3],
                 [2302, 2],
                 [2570, 2],
                 [3012, 1],
                 [3025, 1],
                 [3251, 1],
                 [4294, 1],
                 [4860, 2]]},
   [[['allow', 0],
     ['deny', 487],
     ['deny', 248],
     ['allow', 0],
     ['deny', 74],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0]],
    '54/125']]]]
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:
A request whose cost exactly equals the refilled balance is denied.

Input {capacity, rate (tokens per second), requests [[t_ms, cost]]}. The bucket starts full at t=0. At each request, elapsed = max(0, t - last); tokens = min(capacity, tokens + elapsed*rate/1000) in exact rational arithmetic; last = max(last, t) so a regressing clock neither drains nor re-credits. A cost above capacity can never succeed ("never"). Otherwise allow when tokens >= cost and deduct; else deny with wait = ceil((cost - tokens) * 1000 / rate) ms. Return [[decision, wait]], final tokens].

split: open-access


prompt:
After a quiet period the limiter admits an unbounded burst because TAT lags far behind now.

Input {period_ms T, burst B, requests [[t, quantity]]}. State TAT starts at 0. A quantity above B is ["never", 0, 0]. Otherwise tat = max(TAT, t) and new_tat = tat + q*T; the request is allowed iff new_tat - t <= B*T, in which case TAT = new_tat and remaining = floor((B*T - (TAT - t))/T). A denied request leaves TAT unchanged and reports retry_after = new_tat - B*T - t and remaining floor((B*T - (tat - t))/T). Return [[decision, retry_after, remaining]].

split: open-access


prompt:
A client that keeps retrying is locked out indefinitely because rejected requests consume future capacity.

Input {period_ms T, burst B, requests [[t, quantity]]}. State TAT starts at 0. A quantity above B is ["never", 0, 0]. Otherwise tat = max(TAT, t) and new_tat = tat + q*T; the request is allowed iff new_tat - t <= B*T, in which case TAT = new_tat and remaining = floor((B*T - (TAT - t))/T). A denied request leaves TAT unchanged and reports retry_after = new_tat - B*T - t and remaining floor((B*T - (tat - t))/T). Return [[decision, retry_after, remaining]].

split: open-access


prompt:
Clients receive one request less than the configured burst.

Input {period_ms T, burst B, requests [[t, quantity]]}. State TAT starts at 0. A quantity above B is ["never", 0, 0]. Otherwise tat = max(TAT, t) and new_tat = tat + q*T; the request is allowed iff new_tat - t <= B*T, in which case TAT = new_tat and remaining = floor((B*T - (TAT - t))/T). A denied request leaves TAT unchanged and reports retry_after = new_tat - B*T - t and remaining floor((B*T - (tat - t))/T). Return [[decision, retry_after, remaining]].

split: open-access


prompt:
Denied clients are told to wait far longer than necessary.

Input {period_ms T, burst B, requests [[t, quantity]]}. State TAT starts at 0. A quantity above B is ["never", 0, 0]. Otherwise tat = max(TAT, t) and new_tat = tat + q*T; the request is allowed iff new_tat - t <= B*T, in which case TAT = new_tat and remaining = floor((B*T - (TAT - t))/T). A denied request leaves TAT unchanged and reports retry_after = new_tat - B*T - t and remaining floor((B*T - (tat - t))/T). Return [[decision, retry_after, remaining]].

split: open-access


prompt:
A request for several units consumes only one emission interval, multiplying the admitted rate.

Input {period_ms T, burst B, requests [[t, quantity]]}. State TAT starts at 0. A quantity above B is ["never", 0, 0]. Otherwise tat = max(TAT, t) and new_tat = tat + q*T; the request is allowed iff new_tat - t <= B*T, in which case TAT = new_tat and remaining = floor((B*T - (TAT - t))/T). A denied request leaves TAT unchanged and reports retry_after = new_tat - B*T - t and remaining floor((B*T - (tat - t))/T). Return [[decision, retry_after, remaining]].

split: open-access


prompt:
Requests larger than the burst receive retry hints that can never succeed.

Input {period_ms T, burst B, requests [[t, quantity]]}. State TAT starts at 0. A quantity above B is ["never", 0, 0]. Otherwise tat = max(TAT, t) and new_tat = tat + q*T; the request is allowed iff new_tat - t <= B*T, in which case TAT = new_tat and remaining = floor((B*T - (TAT - t))/T). A denied request leaves TAT unchanged and reports retry_after = new_tat - B*T - t and remaining floor((B*T - (tat - t))/T). Return [[decision, retry_after, remaining]].

split: open-access


prompt:
Clients are told they have a request left when the next one will be denied.

Input {period_ms T, burst B, requests [[t, quantity]]}. State TAT starts at 0. A quantity above B is ["never", 0, 0]. Otherwise tat = max(TAT, t) and new_tat = tat + q*T; the request is allowed iff new_tat - t <= B*T, in which case TAT = new_tat and remaining = floor((B*T - (TAT - t))/T). A denied request leaves TAT unchanged and reports retry_after = new_tat - B*T - t and remaining floor((B*T - (tat - t))/T). Return [[decision, retry_after, remaining]].

split: open-access


prompt:
Window boundaries differ from the advertised epoch-aligned reset times.

Input {limit, window_ms, requests [[t, key]]}. Windows are epoch-aligned: index t div W. Each (case-sensitive) key keeps [window, count]; a request in a later window resets the count, while a late request from an earlier window is charged to the current window. Allow while count < limit and report remaining = limit - count after charging; denials are not counted. reset = ms until the end of the key's current window. Return [[decision, remaining, reset]].

split: open-access


prompt:
A key idle for more than one window keeps its exhausted count forever.

Input {limit, window_ms, requests [[t, key]]}. Windows are epoch-aligned: index t div W. Each (case-sensitive) key keeps [window, count]; a request in a later window resets the count, while a late request from an earlier window is charged to the current window. Allow while count < limit and report remaining = limit - count after charging; denials are not counted. reset = ms until the end of the key's current window. Return [[decision, remaining, reset]].

split: open-access


prompt:
One tenant exhausts the quota for everyone.

Input {limit, window_ms, requests [[t, key]]}. Windows are epoch-aligned: index t div W. Each (case-sensitive) key keeps [window, count]; a request in a later window resets the count, while a late request from an earlier window is charged to the current window. Allow while count < limit and report remaining = limit - count after charging; denials are not counted. reset = ms until the end of the key's current window. Return [[decision, remaining, reset]].

split: open-access


prompt:
Clients interpret an epoch timestamp as a delay and back off for decades.

Input {limit, window_ms, requests [[t, key]]}. Windows are epoch-aligned: index t div W. Each (case-sensitive) key keeps [window, count]; a request in a later window resets the count, while a late request from an earlier window is charged to the current window. Allow while count < limit and report remaining = limit - count after charging; denials are not counted. reset = ms until the end of the key's current window. Return [[decision, remaining, reset]].

split: open-access


prompt:
The last permitted request is advertised as leaving one more.

Input {limit, window_ms, requests [[t, key]]}. Windows are epoch-aligned: index t div W. Each (case-sensitive) key keeps [window, count]; a request in a later window resets the count, while a late request from an earlier window is charged to the current window. Allow while count < limit and report remaining = limit - count after charging; denials are not counted. reset = ms until the end of the key's current window. Return [[decision, remaining, reset]].

split: open-access


prompt:
Each window admits limit + 1 requests.

Input {limit, window_ms, requests [[t, key]]}. Windows are epoch-aligned: index t div W. Each (case-sensitive) key keeps [window, count]; a request in a later window resets the count, while a late request from an earlier window is charged to the current window. Allow while count < limit and report remaining = limit - count after charging; denials are not counted. reset = ms until the end of the key's current window. Return [[decision, remaining, reset]].

split: open-access


prompt:
A client retrying exactly at the advertised time is denied again.

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

split: open-access


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

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

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

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

prompt:
A client that keeps retrying never recovers because every denial is logged.

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

split: open-access


prompt:
Clients back off longer than necessary.

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

split: open-access


prompt:
A delayed request is evaluated in the past and resurrects expired entries.

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

split: open-access