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

N = 1
observations = []
def solve(x):
    W = x['W']
    buckets = []
    out = []
    for t, bit in enumerate(x['bits'], 1):
        while buckets and buckets[-1][1] <= t - W:
            buckets.pop()
        if bit:
            buckets.insert(0, [1, t])
            size = 1
            while True:
                idx = [i for i, bk in enumerate(buckets) if bk[0] == size]
                if len(idx) <= 2:
                    break
                a, z = idx[-2], idx[-1]
                buckets[a] = [size * 2, buckets[a][1]]
                del buckets[z]
                size *= 2
        if t in x['queries']:
            if buckets:
                total = sum(bk[0] for bk in buckets)
                out.append([t, total - buckets[0][0] // 2])
            else:
                out.append([t, 0])
    return [out, buckets]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 W=10',
   {'W': 10,
    'bits': [1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 15]},
   [[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 10]},
   [[[4, 3], [8, 1], [10, 0]], []]],
  ['empty window', {'W': 3, 'bits': [0, 0, 0, 0, 0], 'queries': [2, 4]}, [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 3], [27, 4], [30, 6]], [[1, 30], [1, 29], [2, 28], [4, 22]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 4], [25, 5]], [[1, 25], [1, 24], [2, 23], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 12], [40, 8]], [[1, 40], [1, 38], [2, 33], [2, 30], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 2], [20, 4]], [[1, 19], [2, 18], [2, 16]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 16]},
   [[[7, 5], [16, 12]], [[1, 16], [1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 11]},
   [[[4, 3], [8, 1], [11, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 6], [30, 5]], [[1, 29], [1, 28], [2, 27], [2, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 7], [22, 6], [25, 4]], [[1, 24], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 13], [37, 12], [40, 8]], [[1, 40], [1, 39], [2, 37], [2, 33], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 3]], [[1, 20], [1, 19], [2, 18]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 17]},
   [[[7, 5], [17, 13]], [[1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 12]},
   [[[4, 3], [8, 1], [12, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             0,
             1],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 5]], [[1, 30], [1, 27], [2, 24], [2, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 4], [22, 7], [25, 5]], [[1, 25], [1, 22], [2, 21], [2, 19]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             0],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 9], [40, 11]], [[1, 39], [2, 38], [2, 36], [4, 31], [4, 25]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 4], [17, 6], [20, 5]], [[1, 20], [1, 19], [2, 17], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 18]},
   [[[7, 5], [18, 14]], [[1, 18], [1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 13]},
   [[[4, 3], [8, 1], [13, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 8]], [[1, 29], [1, 27], [2, 26], [2, 23], [4, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 7], [25, 5]], [[1, 24], [1, 22], [2, 20], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 10], [40, 8]], [[1, 40], [1, 38], [2, 37], [2, 35], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 3], [20, 2]], [[1, 20], [2, 19]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 19]},
   [[[7, 5], [19, 15]], [[1, 19], [2, 18], [4, 16], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 14]},
   [[[4, 3], [8, 1], [14, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]]]
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):
    W = x['W']
    buckets = []
    out = []
    for t, bit in enumerate(x['bits'], 1):
        while buckets and buckets[-1][1] <= t - W:
            buckets.pop()
        if bit:
            buckets.insert(0, [1, t])
            size = 1
            while True:
                idx = [i for i, bk in enumerate(buckets) if bk[0] == size]
                if len(idx) <= 2:
                    break
                a, z = idx[-2], idx[-1]
                buckets[a] = [size * 2, buckets[a][1]]
                del buckets[z]
                size *= 2
        if t in x['queries']:
            if buckets:
                total = sum(bk[0] for bk in buckets)
                out.append([t, total - buckets[-1][0]])
            else:
                out.append([t, 0])
    return [out, buckets]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 W=10',
   {'W': 10,
    'bits': [1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 6], [27, 9], [30, 7]], [[1, 30], [2, 29], [2, 26], [4, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 3], [22, 6], [25, 4]], [[1, 25], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 4], [37, 11], [40, 10]], [[1, 40], [1, 39], [2, 38], [4, 33], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 4]], [[1, 20], [2, 18], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 15]},
   [[[7, 5], [15, 11]], [[1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 10]},
   [[[4, 3], [8, 1], [10, 0]], []]],
  ['empty window', {'W': 3, 'bits': [0, 0, 0, 0, 0], 'queries': [2, 4]}, [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1],
    'queries': [15, 27, 30]},
   [[[15, 3], [27, 4], [30, 6]], [[1, 30], [1, 29], [2, 28], [4, 22]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 4], [25, 5]], [[1, 25], [1, 24], [2, 23], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             0,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 12], [40, 8]], [[1, 40], [1, 38], [2, 33], [2, 30], [4, 27]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 2], [20, 4]], [[1, 19], [2, 18], [2, 16]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 16]},
   [[[7, 5], [16, 12]], [[1, 16], [1, 15], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 11]},
   [[[4, 3], [8, 1], [11, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 6], [30, 5]], [[1, 29], [1, 28], [2, 27], [2, 24]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 7], [22, 6], [25, 4]], [[1, 24], [2, 22], [2, 20]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             1,
             0,
             1,
             1],
    'queries': [20, 37, 40]},
   [[[20, 13], [37, 12], [40, 8]], [[1, 40], [1, 39], [2, 37], [2, 33], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 2], [17, 2], [20, 3]], [[1, 20], [1, 19], [2, 18]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 17]},
   [[[7, 5], [17, 13]], [[1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 12]},
   [[[4, 3], [8, 1], [12, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             1,
             1,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             0,
             0,
             1,
             0,
             0,
             1],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 5]], [[1, 30], [1, 27], [2, 24], [2, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1],
    'queries': [12, 22, 25]},
   [[[12, 4], [22, 7], [25, 5]], [[1, 25], [1, 22], [2, 21], [2, 19]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             1,
             0,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             0],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 9], [40, 11]], [[1, 39], [2, 38], [2, 36], [4, 31], [4, 25]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 4], [17, 6], [20, 5]], [[1, 20], [1, 19], [2, 17], [2, 15]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 18]},
   [[[7, 5], [18, 14]], [[1, 18], [1, 17], [2, 16], [2, 14], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 13]},
   [[[4, 3], [8, 1], [13, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]],
 [['stream 0 W=10',
   {'W': 10,
    'bits': [0,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             0,
             0,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             1,
             0],
    'queries': [15, 27, 30]},
   [[[15, 5], [27, 7], [30, 8]], [[1, 29], [1, 27], [2, 26], [2, 23], [4, 21]]]],
  ['stream 1 W=8',
   {'W': 8,
    'bits': [0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0],
    'queries': [12, 22, 25]},
   [[[12, 2], [22, 7], [25, 5]], [[1, 24], [1, 22], [2, 20], [2, 18]]]],
  ['stream 2 W=16',
   {'W': 16,
    'bits': [0,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             1,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             1,
             1,
             1,
             0,
             1,
             1,
             1,
             0,
             0,
             0,
             1,
             0,
             1,
             0,
             1,
             1,
             1,
             1,
             0,
             1],
    'queries': [20, 37, 40]},
   [[[20, 11], [37, 10], [40, 8]], [[1, 40], [1, 38], [2, 37], [2, 35], [4, 31]]]],
  ['stream 3 W=6',
   {'W': 6,
    'bits': [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
    'queries': [10, 17, 20]},
   [[[10, 3], [17, 3], [20, 2]], [[1, 20], [2, 19]]]],
  ['all ones',
   {'W': 12, 'bits': [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 'queries': [7, 19]},
   [[[7, 5], [19, 15]], [[1, 19], [2, 18], [4, 16], [4, 12], [8, 8]]]],
  ['trailing zeros expire',
   {'W': 5, 'bits': [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [4, 8, 14]},
   [[[4, 3], [8, 1], [14, 0]], []]],
  ['empty window',
   {'W': 3, 'bits': [0, 0, 0, 0, 0, 0, 0, 0, 0], 'queries': [2, 4]},
   [[[2, 0], [4, 0]], []]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
The uncertainty correction is applied to the fully-inside newest bucket instead of the straddling oldest one.

Input {W, bits, queries}; timestamps start at 1. Buckets are [size, timestamp of most recent 1], newest first. Before processing time t, buckets with timestamp <= t - W expire. A 1 bit adds [1, t]; while more than two buckets share a size, the two oldest of that size merge into one of double size keeping the more recent timestamp, cascading upward. At a query time the estimate is the total size minus floor(oldest size / 2). Return [[t, estimate] per query, final buckets].

split: open-access


meaning: Fixture-count band, not measured model difficulty

deps: stdlib

prompt:
An established leader keeps its entry score and is evicted by newer, smaller keys.

Input {w, k, stream of [key, count]}. A three-row Count-Min sketch (fixed hash family) is updated first; the key's estimate is then the minimum of its cells. A tracked key's score is refreshed to the new estimate; an untracked key enters while fewer than k are tracked; otherwise it replaces the victim with the smallest score (ties: smallest key) only if its estimate is strictly larger. Return [key, score] rows sorted by score descending then key.

split: open-access


prompt:
Keys with equal estimates churn the table, and the reported leader set depends on arrival order.

Input {w, k, stream of [key, count]}. A three-row Count-Min sketch (fixed hash family) is updated first; the key's estimate is then the minimum of its cells. A tracked key's score is refreshed to the new estimate; an untracked key enters while fewer than k are tracked; otherwise it replaces the victim with the smallest score (ties: smallest key) only if its estimate is strictly larger. Return [key, score] rows sorted by score descending then key.

split: open-access


prompt:
Which minimum-score key survives depends on insertion history instead of the stated tie-break.

Input {w, k, stream of [key, count]}. A three-row Count-Min sketch (fixed hash family) is updated first; the key's estimate is then the minimum of its cells. A tracked key's score is refreshed to the new estimate; an untracked key enters while fewer than k are tracked; otherwise it replaces the victim with the smallest score (ties: smallest key) only if its estimate is strictly larger. Return [key, score] rows sorted by score descending then key.

split: open-access


prompt:
Each key is scored without its current occurrence, so newcomers can never beat equal incumbents.

Input {w, k, stream of [key, count]}. A three-row Count-Min sketch (fixed hash family) is updated first; the key's estimate is then the minimum of its cells. A tracked key's score is refreshed to the new estimate; an untracked key enters while fewer than k are tracked; otherwise it replaces the victim with the smallest score (ties: smallest key) only if its estimate is strictly larger. Return [key, score] rows sorted by score descending then key.

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 = 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 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:
After an idle period a client can burst far beyond the configured capacity.

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 = 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 = abs(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 stamped slightly earlier than the previous one removes tokens it never spent.

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 = 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 = t if t >= last - 1000 else last
        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:
After a late timestamp the next request is credited again for time already refilled.

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