prompt:
Quotas reset at the mirror-image hour: customers east of UTC reset in the afternoon.

Input {quota, utc_offset_min, requests [[epoch_s, cost]]} with nondecreasing times. The quota day is floor((t + offset)/86400) with offset = utc_offset_min*60, so days roll over at local midnight. A new day resets usage. A request is allowed only if the whole cost fits (used + cost <= quota); a denied request consumes nothing. Report [decision, remaining, reset_at] where reset_at is the UTC epoch of the next local midnight, (day + 1)*86400 - offset.

split: open-access


meaning: Fixture-count band, not measured model difficulty

deps: stdlib

prompt:
Clients are told the quota resets at a local-midnight number interpreted as a UTC epoch.

Input {quota, utc_offset_min, requests [[epoch_s, cost]]} with nondecreasing times. The quota day is floor((t + offset)/86400) with offset = utc_offset_min*60, so days roll over at local midnight. A new day resets usage. A request is allowed only if the whole cost fits (used + cost <= quota); a denied request consumes nothing. Report [decision, remaining, reset_at] where reset_at is the UTC epoch of the next local midnight, (day + 1)*86400 - offset.

split: open-access


prompt:
A request slightly too large for the remaining quota wipes out the rest of the day.

Input {quota, utc_offset_min, requests [[epoch_s, cost]]} with nondecreasing times. The quota day is floor((t + offset)/86400) with offset = utc_offset_min*60, so days roll over at local midnight. A new day resets usage. A request is allowed only if the whole cost fits (used + cost <= quota); a denied request consumes nothing. Report [decision, remaining, reset_at] where reset_at is the UTC epoch of the next local midnight, (day + 1)*86400 - offset.

split: open-access


prompt:
Usage resets at UTC midnight while the advertised reset time is local midnight.

Input {quota, utc_offset_min, requests [[epoch_s, cost]]} with nondecreasing times. The quota day is floor((t + offset)/86400) with offset = utc_offset_min*60, so days roll over at local midnight. A new day resets usage. A request is allowed only if the whole cost fits (used + cost <= quota); a denied request consumes nothing. Report [decision, remaining, reset_at] where reset_at is the UTC epoch of the next local midnight, (day + 1)*86400 - offset.

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):
    rate = x['rate']
    I = Fraction(1000, rate)
    max_stored = Fraction(x['max_burst_s'] * rate)
    stored = Fraction(0)
    next_free = Fraction(0)
    out = []
    for t, p in x['requests']:
        if t > next_free:
            stored = min(max_stored, stored + (t - next_free) / I)
            next_free = Fraction(t)
        use = min(Fraction(p), stored)
        fresh = p - use
        next_free += fresh * I
        wait = max(Fraction(0), next_free - t)
        stored -= use
        out.append(math.ceil(wait))
    return [out, str(stored), str(next_free)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},
   [[0, 2000, 2099, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},
   [[0, 0, 500, 999], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},
   [[0, 0, 0, 499], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},
   [[0, 0, 0, 0, 0], '3', '4001']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},
   [[0, 334, 656, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[610, 3],
                 [1148, 4],
                 [1339, 3],
                 [2090, 3],
                 [2093, 2],
                 [2589, 1],
                 [2607, 4],
                 [2941, 2],
                 [3090, 2]]},
   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},
   [[0, 2000, 2098, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},
   [[0, 0, 500, 998], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},
   [[0, 0, 0, 498], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},
   [[0, 0, 0, 0, 0], '3', '4002']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},
   [[0, 334, 655, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[142, 4],
                 [325, 1],
                 [548, 2],
                 [901, 1],
                 [1366, 1],
                 [1827, 2],
                 [1998, 3],
                 [2374, 1],
                 [2914, 2]]},
   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},
   [[0, 2000, 2097, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},
   [[0, 0, 500, 997], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},
   [[0, 0, 0, 497], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},
   [[0, 0, 0, 0, 0], '3', '4003']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},
   [[0, 334, 654, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[644, 4],
                 [886, 4],
                 [910, 3],
                 [1485, 1],
                 [1585, 2],
                 [1776, 4],
                 [2163, 2],
                 [2628, 3],
                 [2698, 2]]},
   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},
   [[0, 2000, 2096, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},
   [[0, 0, 500, 996], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},
   [[0, 0, 0, 496], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},
   [[0, 0, 0, 0, 0], '3', '4004']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},
   [[0, 334, 653, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[106, 2],
                 [1122, 1],
                 [1604, 3],
                 [1998, 1],
                 [2099, 1],
                 [2549, 2],
                 [2752, 1],
                 [2983, 1],
                 [3690, 4]]},
   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},
   [[0, 2000, 2095, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},
   [[0, 0, 500, 995], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},
   [[0, 0, 0, 495], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},
   [[0, 0, 0, 0, 0], '3', '4005']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},
   [[0, 334, 652, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[2392, 4],
                 [2748, 2],
                 [3147, 1],
                 [3291, 2],
                 [3293, 2],
                 [3431, 2],
                 [3441, 1],
                 [3672, 1],
                 [3732, 4]]},
   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]
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):
    rate = x['rate']
    I = Fraction(1000, rate)
    max_stored = Fraction(x['max_burst_s'] * rate)
    stored = Fraction(0)
    next_free = Fraction(0)
    out = []
    for t, p in x['requests']:
        if t > next_free:
            stored = min(max_stored, stored + (t - next_free) / I)
            next_free = Fraction(t)
        use = min(Fraction(p), stored)
        fresh = p - use
        wait = fresh * I
        next_free += fresh * I
        stored -= use
        out.append(math.ceil(wait))
    return [out, str(stored), str(next_free)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},
   [[0, 2000, 2099, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},
   [[0, 0, 500, 999], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},
   [[0, 0, 0, 499], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},
   [[0, 0, 0, 0, 0], '3', '4001']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},
   [[0, 334, 656, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[610, 3],
                 [1148, 4],
                 [1339, 3],
                 [2090, 3],
                 [2093, 2],
                 [2589, 1],
                 [2607, 4],
                 [2941, 2],
                 [3090, 2]]},
   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},
   [[0, 2000, 2098, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},
   [[0, 0, 500, 998], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},
   [[0, 0, 0, 498], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},
   [[0, 0, 0, 0, 0], '3', '4002']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},
   [[0, 334, 655, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[142, 4],
                 [325, 1],
                 [548, 2],
                 [901, 1],
                 [1366, 1],
                 [1827, 2],
                 [1998, 3],
                 [2374, 1],
                 [2914, 2]]},
   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},
   [[0, 2000, 2097, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},
   [[0, 0, 500, 997], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},
   [[0, 0, 0, 497], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},
   [[0, 0, 0, 0, 0], '3', '4003']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},
   [[0, 334, 654, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[644, 4],
                 [886, 4],
                 [910, 3],
                 [1485, 1],
                 [1585, 2],
                 [1776, 4],
                 [2163, 2],
                 [2628, 3],
                 [2698, 2]]},
   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},
   [[0, 2000, 2096, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},
   [[0, 0, 500, 996], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},
   [[0, 0, 0, 496], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},
   [[0, 0, 0, 0, 0], '3', '4004']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},
   [[0, 334, 653, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[106, 2],
                 [1122, 1],
                 [1604, 3],
                 [1998, 1],
                 [2099, 1],
                 [2549, 2],
                 [2752, 1],
                 [2983, 1],
                 [3690, 4]]},
   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},
   [[0, 2000, 2095, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},
   [[0, 0, 500, 995], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},
   [[0, 0, 0, 495], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},
   [[0, 0, 0, 0, 0], '3', '4005']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},
   [[0, 334, 652, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[2392, 4],
                 [2748, 2],
                 [3147, 1],
                 [3291, 2],
                 [3293, 2],
                 [3431, 2],
                 [3441, 1],
                 [3672, 1],
                 [3732, 4]]},
   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]
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 large first request is delayed instead of the following caller, defeating the reservation design.

Input {rate (permits per second), max_burst_s, requests [[t_ms, permits]]} with nondecreasing t. The interval is I = 1000/rate ms. When t is past next_free, idle time is converted into stored permits (capped at max_burst_s*rate) and next_free moves to t. A request waits max(0, next_free - t), i.e. it pays for the previous reservation, then consumes stored permits first and pushes next_free by I per fresh permit. Return [ceil waits in ms, stored, next_free] with exact fractions as strings.

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):
    rate = x['rate']
    I = Fraction(1000, rate)
    max_stored = Fraction(x['max_burst_s'] * rate)
    stored = Fraction(0)
    next_free = Fraction(0)
    out = []
    for t, p in x['requests']:
        if t > next_free:
            stored = stored + (t - next_free) / I
            next_free = Fraction(t)
        wait = max(Fraction(0), next_free - t)
        use = min(Fraction(p), stored)
        fresh = p - use
        next_free += fresh * I
        stored -= use
        out.append(math.ceil(wait))
    return [out, str(stored), str(next_free)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},
   [[0, 2000, 2099, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},
   [[0, 0, 500, 999], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},
   [[0, 0, 0, 499], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},
   [[0, 0, 0, 0, 0], '3', '4001']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},
   [[0, 334, 656, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[610, 3],
                 [1148, 4],
                 [1339, 3],
                 [2090, 3],
                 [2093, 2],
                 [2589, 1],
                 [2607, 4],
                 [2941, 2],
                 [3090, 2]]},
   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},
   [[0, 2000, 2098, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},
   [[0, 0, 500, 998], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},
   [[0, 0, 0, 498], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},
   [[0, 0, 0, 0, 0], '3', '4002']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},
   [[0, 334, 655, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[142, 4],
                 [325, 1],
                 [548, 2],
                 [901, 1],
                 [1366, 1],
                 [1827, 2],
                 [1998, 3],
                 [2374, 1],
                 [2914, 2]]},
   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},
   [[0, 2000, 2097, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},
   [[0, 0, 500, 997], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},
   [[0, 0, 0, 497], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},
   [[0, 0, 0, 0, 0], '3', '4003']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},
   [[0, 334, 654, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[644, 4],
                 [886, 4],
                 [910, 3],
                 [1485, 1],
                 [1585, 2],
                 [1776, 4],
                 [2163, 2],
                 [2628, 3],
                 [2698, 2]]},
   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},
   [[0, 2000, 2096, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},
   [[0, 0, 500, 996], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},
   [[0, 0, 0, 496], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},
   [[0, 0, 0, 0, 0], '3', '4004']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},
   [[0, 334, 653, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[106, 2],
                 [1122, 1],
                 [1604, 3],
                 [1998, 1],
                 [2099, 1],
                 [2549, 2],
                 [2752, 1],
                 [2983, 1],
                 [3690, 4]]},
   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},
   [[0, 2000, 2095, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},
   [[0, 0, 500, 995], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},
   [[0, 0, 0, 495], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},
   [[0, 0, 0, 0, 0], '3', '4005']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},
   [[0, 334, 652, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[2392, 4],
                 [2748, 2],
                 [3147, 1],
                 [3291, 2],
                 [3293, 2],
                 [3431, 2],
                 [3441, 1],
                 [3672, 1],
                 [3732, 4]]},
   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]
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):
    rate = x['rate']
    I = Fraction(1000, rate)
    max_stored = Fraction(x['max_burst_s'] * rate)
    stored = Fraction(0)
    next_free = Fraction(0)
    out = []
    for t, p in x['requests']:
        if t > next_free:
            stored = min(Fraction(rate), stored + (t - next_free) / I)
            next_free = Fraction(t)
        wait = max(Fraction(0), next_free - t)
        use = min(Fraction(p), stored)
        fresh = p - use
        next_free += fresh * I
        stored -= use
        out.append(math.ceil(wait))
    return [out, str(stored), str(next_free)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},
   [[0, 2000, 2099, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},
   [[0, 0, 500, 999], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},
   [[0, 0, 0, 499], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},
   [[0, 0, 0, 0, 0], '3', '4001']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},
   [[0, 334, 656, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[610, 3],
                 [1148, 4],
                 [1339, 3],
                 [2090, 3],
                 [2093, 2],
                 [2589, 1],
                 [2607, 4],
                 [2941, 2],
                 [3090, 2]]},
   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},
   [[0, 2000, 2098, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},
   [[0, 0, 500, 998], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},
   [[0, 0, 0, 498], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},
   [[0, 0, 0, 0, 0], '3', '4002']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},
   [[0, 334, 655, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[142, 4],
                 [325, 1],
                 [548, 2],
                 [901, 1],
                 [1366, 1],
                 [1827, 2],
                 [1998, 3],
                 [2374, 1],
                 [2914, 2]]},
   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},
   [[0, 2000, 2097, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},
   [[0, 0, 500, 997], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},
   [[0, 0, 0, 497], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},
   [[0, 0, 0, 0, 0], '3', '4003']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},
   [[0, 334, 654, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[644, 4],
                 [886, 4],
                 [910, 3],
                 [1485, 1],
                 [1585, 2],
                 [1776, 4],
                 [2163, 2],
                 [2628, 3],
                 [2698, 2]]},
   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},
   [[0, 2000, 2096, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},
   [[0, 0, 500, 996], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},
   [[0, 0, 0, 496], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},
   [[0, 0, 0, 0, 0], '3', '4004']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},
   [[0, 334, 653, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[106, 2],
                 [1122, 1],
                 [1604, 3],
                 [1998, 1],
                 [2099, 1],
                 [2549, 2],
                 [2752, 1],
                 [2983, 1],
                 [3690, 4]]},
   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},
   [[0, 2000, 2095, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},
   [[0, 0, 500, 995], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},
   [[0, 0, 0, 495], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},
   [[0, 0, 0, 0, 0], '3', '4005']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},
   [[0, 334, 652, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[2392, 4],
                 [2748, 2],
                 [3147, 1],
                 [3291, 2],
                 [3293, 2],
                 [3431, 2],
                 [3441, 1],
                 [3672, 1],
                 [3732, 4]]},
   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]
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 long idle period the limiter releases an arbitrarily large burst.

Input {rate (permits per second), max_burst_s, requests [[t_ms, permits]]} with nondecreasing t. The interval is I = 1000/rate ms. When t is past next_free, idle time is converted into stored permits (capped at max_burst_s*rate) and next_free moves to t. A request waits max(0, next_free - t), i.e. it pays for the previous reservation, then consumes stored permits first and pushes next_free by I per fresh permit. Return [ceil waits in ms, stored, next_free] with exact fractions as strings.

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):
    rate = x['rate']
    I = Fraction(1000, rate)
    max_stored = Fraction(x['max_burst_s'] * rate)
    stored = Fraction(0)
    next_free = Fraction(0)
    out = []
    for t, p in x['requests']:
        if t > next_free:
            stored = min(max_stored, stored + (t - next_free) / I)
            next_free = Fraction(t)
        wait = max(Fraction(0), next_free - t)
        use = min(Fraction(p), stored)
        fresh = p - use
        next_free += fresh * I
        out.append(math.ceil(wait))
    return [out, str(stored), str(next_free)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},
   [[0, 2000, 2099, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},
   [[0, 0, 500, 999], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},
   [[0, 0, 0, 499], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},
   [[0, 0, 0, 0, 0], '3', '4001']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},
   [[0, 334, 656, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[610, 3],
                 [1148, 4],
                 [1339, 3],
                 [2090, 3],
                 [2093, 2],
                 [2589, 1],
                 [2607, 4],
                 [2941, 2],
                 [3090, 2]]},
   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},
   [[0, 2000, 2098, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},
   [[0, 0, 500, 998], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},
   [[0, 0, 0, 498], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},
   [[0, 0, 0, 0, 0], '3', '4002']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},
   [[0, 334, 655, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[142, 4],
                 [325, 1],
                 [548, 2],
                 [901, 1],
                 [1366, 1],
                 [1827, 2],
                 [1998, 3],
                 [2374, 1],
                 [2914, 2]]},
   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},
   [[0, 2000, 2097, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},
   [[0, 0, 500, 997], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},
   [[0, 0, 0, 497], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},
   [[0, 0, 0, 0, 0], '3', '4003']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},
   [[0, 334, 654, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[644, 4],
                 [886, 4],
                 [910, 3],
                 [1485, 1],
                 [1585, 2],
                 [1776, 4],
                 [2163, 2],
                 [2628, 3],
                 [2698, 2]]},
   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},
   [[0, 2000, 2096, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},
   [[0, 0, 500, 996], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},
   [[0, 0, 0, 496], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},
   [[0, 0, 0, 0, 0], '3', '4004']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},
   [[0, 334, 653, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[106, 2],
                 [1122, 1],
                 [1604, 3],
                 [1998, 1],
                 [2099, 1],
                 [2549, 2],
                 [2752, 1],
                 [2983, 1],
                 [3690, 4]]},
   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},
   [[0, 2000, 2095, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},
   [[0, 0, 500, 995], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},
   [[0, 0, 0, 495], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},
   [[0, 0, 0, 0, 0], '3', '4005']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},
   [[0, 334, 652, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[2392, 4],
                 [2748, 2],
                 [3147, 1],
                 [3291, 2],
                 [3293, 2],
                 [3431, 2],
                 [3441, 1],
                 [3672, 1],
                 [3732, 4]]},
   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]
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):
    rate = x['rate']
    I = Fraction(1000, rate)
    max_stored = Fraction(x['max_burst_s'] * rate)
    stored = Fraction(0)
    next_free = Fraction(0)
    out = []
    for t, p in x['requests']:
        if t > next_free:
            stored = min(max_stored, stored + (t - next_free) / I)
            next_free = Fraction(t)
        wait = max(Fraction(0), next_free - t)
        use = min(Fraction(p), stored)
        fresh = p - use
        next_free += fresh * I
        stored -= p
        out.append(math.ceil(wait))
    return [out, str(stored), str(next_free)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},
   [[0, 2000, 2099, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},
   [[0, 0, 500, 999], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},
   [[0, 0, 0, 499], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},
   [[0, 0, 0, 0, 0], '3', '4001']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},
   [[0, 334, 656, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[610, 3],
                 [1148, 4],
                 [1339, 3],
                 [2090, 3],
                 [2093, 2],
                 [2589, 1],
                 [2607, 4],
                 [2941, 2],
                 [3090, 2]]},
   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},
   [[0, 2000, 2098, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},
   [[0, 0, 500, 998], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},
   [[0, 0, 0, 498], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},
   [[0, 0, 0, 0, 0], '3', '4002']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},
   [[0, 334, 655, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[142, 4],
                 [325, 1],
                 [548, 2],
                 [901, 1],
                 [1366, 1],
                 [1827, 2],
                 [1998, 3],
                 [2374, 1],
                 [2914, 2]]},
   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},
   [[0, 2000, 2097, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},
   [[0, 0, 500, 997], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},
   [[0, 0, 0, 497], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},
   [[0, 0, 0, 0, 0], '3', '4003']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},
   [[0, 334, 654, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[644, 4],
                 [886, 4],
                 [910, 3],
                 [1485, 1],
                 [1585, 2],
                 [1776, 4],
                 [2163, 2],
                 [2628, 3],
                 [2698, 2]]},
   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},
   [[0, 2000, 2096, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},
   [[0, 0, 500, 996], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},
   [[0, 0, 0, 496], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},
   [[0, 0, 0, 0, 0], '3', '4004']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},
   [[0, 334, 653, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[106, 2],
                 [1122, 1],
                 [1604, 3],
                 [1998, 1],
                 [2099, 1],
                 [2549, 2],
                 [2752, 1],
                 [2983, 1],
                 [3690, 4]]},
   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},
   [[0, 2000, 2095, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},
   [[0, 0, 500, 995], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},
   [[0, 0, 0, 495], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},
   [[0, 0, 0, 0, 0], '3', '4005']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},
   [[0, 334, 652, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[2392, 4],
                 [2748, 2],
                 [3147, 1],
                 [3291, 2],
                 [3293, 2],
                 [3431, 2],
                 [3441, 1],
                 [3672, 1],
                 [3732, 4]]},
   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]
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 burst allowance is reused by every request, so the limiter never throttles after idleness.

Input {rate (permits per second), max_burst_s, requests [[t_ms, permits]]} with nondecreasing t. The interval is I = 1000/rate ms. When t is past next_free, idle time is converted into stored permits (capped at max_burst_s*rate) and next_free moves to t. A request waits max(0, next_free - t), i.e. it pays for the previous reservation, then consumes stored permits first and pushes next_free by I per fresh permit. Return [ceil waits in ms, stored, next_free] with exact fractions as strings.

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):
    rate = x['rate']
    I = Fraction(1000, rate)
    max_stored = Fraction(x['max_burst_s'] * rate)
    stored = Fraction(0)
    next_free = Fraction(0)
    out = []
    for t, p in x['requests']:
        if t > next_free:
            stored = min(max_stored, stored + (t - next_free) / I)
        wait = max(Fraction(0), next_free - t)
        use = min(Fraction(p), stored)
        fresh = p - use
        next_free += fresh * I
        stored -= use
        out.append(math.ceil(wait))
    return [out, str(stored), str(next_free)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},
   [[0, 2000, 2099, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},
   [[0, 0, 500, 999], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},
   [[0, 0, 0, 499], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},
   [[0, 0, 0, 0, 0], '3', '4001']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},
   [[0, 334, 656, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[610, 3],
                 [1148, 4],
                 [1339, 3],
                 [2090, 3],
                 [2093, 2],
                 [2589, 1],
                 [2607, 4],
                 [2941, 2],
                 [3090, 2]]},
   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},
   [[0, 2000, 2098, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},
   [[0, 0, 500, 998], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},
   [[0, 0, 0, 498], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},
   [[0, 0, 0, 0, 0], '3', '4002']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},
   [[0, 334, 655, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[142, 4],
                 [325, 1],
                 [548, 2],
                 [901, 1],
                 [1366, 1],
                 [1827, 2],
                 [1998, 3],
                 [2374, 1],
                 [2914, 2]]},
   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},
   [[0, 2000, 2097, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},
   [[0, 0, 500, 997], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},
   [[0, 0, 0, 497], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},
   [[0, 0, 0, 0, 0], '3', '4003']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},
   [[0, 334, 654, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[644, 4],
                 [886, 4],
                 [910, 3],
                 [1485, 1],
                 [1585, 2],
                 [1776, 4],
                 [2163, 2],
                 [2628, 3],
                 [2698, 2]]},
   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},
   [[0, 2000, 2096, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},
   [[0, 0, 500, 996], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},
   [[0, 0, 0, 496], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},
   [[0, 0, 0, 0, 0], '3', '4004']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},
   [[0, 334, 653, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[106, 2],
                 [1122, 1],
                 [1604, 3],
                 [1998, 1],
                 [2099, 1],
                 [2549, 2],
                 [2752, 1],
                 [2983, 1],
                 [3690, 4]]},
   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},
   [[0, 2000, 2095, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},
   [[0, 0, 500, 995], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},
   [[0, 0, 0, 495], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},
   [[0, 0, 0, 0, 0], '3', '4005']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},
   [[0, 334, 652, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[2392, 4],
                 [2748, 2],
                 [3147, 1],
                 [3291, 2],
                 [3293, 2],
                 [3431, 2],
                 [3441, 1],
                 [3672, 1],
                 [3732, 4]]},
   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]
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):
    rate = x['rate']
    I = Fraction(1000, rate)
    max_stored = Fraction(x['max_burst_s'] * rate)
    stored = Fraction(0)
    next_free = Fraction(0)
    out = []
    for t, p in x['requests']:
        if t > next_free:
            stored = min(max_stored, stored + (t - next_free) / I)
            next_free = Fraction(t) + I
        wait = max(Fraction(0), next_free - t)
        use = min(Fraction(p), stored)
        fresh = p - use
        next_free += fresh * I
        stored -= use
        out.append(math.ceil(wait))
    return [out, str(stored), str(next_free)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},
   [[0, 2000, 2099, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},
   [[0, 0, 500, 999], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},
   [[0, 0, 0, 499], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},
   [[0, 0, 0, 0, 0], '3', '4001']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},
   [[0, 334, 656, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[610, 3],
                 [1148, 4],
                 [1339, 3],
                 [2090, 3],
                 [2093, 2],
                 [2589, 1],
                 [2607, 4],
                 [2941, 2],
                 [3090, 2]]},
   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},
   [[0, 2000, 2098, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},
   [[0, 0, 500, 998], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},
   [[0, 0, 0, 498], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},
   [[0, 0, 0, 0, 0], '3', '4002']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},
   [[0, 334, 655, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[142, 4],
                 [325, 1],
                 [548, 2],
                 [901, 1],
                 [1366, 1],
                 [1827, 2],
                 [1998, 3],
                 [2374, 1],
                 [2914, 2]]},
   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},
   [[0, 2000, 2097, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},
   [[0, 0, 500, 997], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},
   [[0, 0, 0, 497], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},
   [[0, 0, 0, 0, 0], '3', '4003']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},
   [[0, 334, 654, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[644, 4],
                 [886, 4],
                 [910, 3],
                 [1485, 1],
                 [1585, 2],
                 [1776, 4],
                 [2163, 2],
                 [2628, 3],
                 [2698, 2]]},
   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},
   [[0, 2000, 2096, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},
   [[0, 0, 500, 996], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},
   [[0, 0, 0, 496], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},
   [[0, 0, 0, 0, 0], '3', '4004']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},
   [[0, 334, 653, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[106, 2],
                 [1122, 1],
                 [1604, 3],
                 [1998, 1],
                 [2099, 1],
                 [2549, 2],
                 [2752, 1],
                 [2983, 1],
                 [3690, 4]]},
   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},
   [[0, 2000, 2095, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},
   [[0, 0, 500, 995], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},
   [[0, 0, 0, 495], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},
   [[0, 0, 0, 0, 0], '3', '4005']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},
   [[0, 334, 652, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[2392, 4],
                 [2748, 2],
                 [3147, 1],
                 [3291, 2],
                 [3293, 2],
                 [3431, 2],
                 [3441, 1],
                 [3672, 1],
                 [3732, 4]]},
   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]
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:
Idle time is credited again at the next request and fresh permits are scheduled in the past.

Input {rate (permits per second), max_burst_s, requests [[t_ms, permits]]} with nondecreasing t. The interval is I = 1000/rate ms. When t is past next_free, idle time is converted into stored permits (capped at max_burst_s*rate) and next_free moves to t. A request waits max(0, next_free - t), i.e. it pays for the previous reservation, then consumes stored permits first and pushes next_free by I per fresh permit. Return [ceil waits in ms, stored, next_free] with exact fractions as strings.

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):
    rate = x['rate']
    I = Fraction(1000, rate)
    max_stored = Fraction(x['max_burst_s'] * rate)
    stored = Fraction(0)
    next_free = Fraction(0)
    out = []
    for t, p in x['requests']:
        if t > next_free:
            stored = min(max_stored, stored + (t - next_free) / I)
            next_free = Fraction(t)
        wait = max(Fraction(0), next_free - t)
        use = min(Fraction(p), stored)
        fresh = p - use
        next_free += fresh * I
        stored -= use
        out.append(int(wait))
    return [out, str(stored), str(next_free)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},
   [[0, 2000, 2099, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},
   [[0, 0, 500, 999], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},
   [[0, 0, 0, 499], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},
   [[0, 0, 0, 0, 0], '3', '4001']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},
   [[0, 334, 656, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[610, 3],
                 [1148, 4],
                 [1339, 3],
                 [2090, 3],
                 [2093, 2],
                 [2589, 1],
                 [2607, 4],
                 [2941, 2],
                 [3090, 2]]},
   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},
   [[0, 2000, 2098, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},
   [[0, 0, 500, 998], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},
   [[0, 0, 0, 498], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},
   [[0, 0, 0, 0, 0], '3', '4002']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},
   [[0, 334, 655, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[142, 4],
                 [325, 1],
                 [548, 2],
                 [901, 1],
                 [1366, 1],
                 [1827, 2],
                 [1998, 3],
                 [2374, 1],
                 [2914, 2]]},
   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},
   [[0, 2000, 2097, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},
   [[0, 0, 500, 997], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},
   [[0, 0, 0, 497], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},
   [[0, 0, 0, 0, 0], '3', '4003']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},
   [[0, 334, 654, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[644, 4],
                 [886, 4],
                 [910, 3],
                 [1485, 1],
                 [1585, 2],
                 [1776, 4],
                 [2163, 2],
                 [2628, 3],
                 [2698, 2]]},
   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},
   [[0, 2000, 2096, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},
   [[0, 0, 500, 996], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},
   [[0, 0, 0, 496], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},
   [[0, 0, 0, 0, 0], '3', '4004']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},
   [[0, 334, 653, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[106, 2],
                 [1122, 1],
                 [1604, 3],
                 [1998, 1],
                 [2099, 1],
                 [2549, 2],
                 [2752, 1],
                 [2983, 1],
                 [3690, 4]]},
   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},
   [[0, 2000, 2095, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},
   [[0, 0, 500, 995], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},
   [[0, 0, 0, 495], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},
   [[0, 0, 0, 0, 0], '3', '4005']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},
   [[0, 334, 652, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[2392, 4],
                 [2748, 2],
                 [3147, 1],
                 [3291, 2],
                 [3293, 2],
                 [3431, 2],
                 [3441, 1],
                 [3672, 1],
                 [3732, 4]]},
   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]
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):
    rate = x['rate']
    I = Fraction(1000, rate)
    max_stored = Fraction(x['max_burst_s'] * rate)
    stored = Fraction(0)
    next_free = Fraction(0)
    out = []
    for t, p in x['requests']:
        if t > next_free:
            stored = min(max_stored, stored + (t - next_free) / I)
            next_free = Fraction(t)
        wait = max(Fraction(0), next_free - t)
        use = min(Fraction(p), stored)
        fresh = p - use
        next_free += fresh * I
        stored -= use
        out.append(round(wait))
    return [out, str(stored), str(next_free)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},
   [[0, 2000, 2099, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},
   [[0, 0, 500, 999], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},
   [[0, 0, 0, 499], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},
   [[0, 0, 0, 0, 0], '3', '4001']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},
   [[0, 334, 656, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[610, 3],
                 [1148, 4],
                 [1339, 3],
                 [2090, 3],
                 [2093, 2],
                 [2589, 1],
                 [2607, 4],
                 [2941, 2],
                 [3090, 2]]},
   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},
   [[0, 2000, 2098, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},
   [[0, 0, 500, 998], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},
   [[0, 0, 0, 498], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},
   [[0, 0, 0, 0, 0], '3', '4002']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},
   [[0, 334, 655, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[142, 4],
                 [325, 1],
                 [548, 2],
                 [901, 1],
                 [1366, 1],
                 [1827, 2],
                 [1998, 3],
                 [2374, 1],
                 [2914, 2]]},
   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},
   [[0, 2000, 2097, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},
   [[0, 0, 500, 997], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},
   [[0, 0, 0, 497], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},
   [[0, 0, 0, 0, 0], '3', '4003']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},
   [[0, 334, 654, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[644, 4],
                 [886, 4],
                 [910, 3],
                 [1485, 1],
                 [1585, 2],
                 [1776, 4],
                 [2163, 2],
                 [2628, 3],
                 [2698, 2]]},
   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},
   [[0, 2000, 2096, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},
   [[0, 0, 500, 996], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},
   [[0, 0, 0, 496], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},
   [[0, 0, 0, 0, 0], '3', '4004']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},
   [[0, 334, 653, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[106, 2],
                 [1122, 1],
                 [1604, 3],
                 [1998, 1],
                 [2099, 1],
                 [2549, 2],
                 [2752, 1],
                 [2983, 1],
                 [3690, 4]]},
   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},
   [[0, 2000, 2095, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},
   [[0, 0, 500, 995], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},
   [[0, 0, 0, 495], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},
   [[0, 0, 0, 0, 0], '3', '4005']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},
   [[0, 334, 652, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[2392, 4],
                 [2748, 2],
                 [3147, 1],
                 [3291, 2],
                 [3293, 2],
                 [3431, 2],
                 [3441, 1],
                 [3672, 1],
                 [3732, 4]]},
   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]
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:
Callers sleep slightly too little and run ahead of the configured rate.

Input {rate (permits per second), max_burst_s, requests [[t_ms, permits]]} with nondecreasing t. The interval is I = 1000/rate ms. When t is past next_free, idle time is converted into stored permits (capped at max_burst_s*rate) and next_free moves to t. A request waits max(0, next_free - t), i.e. it pays for the previous reservation, then consumes stored permits first and pushes next_free by I per fresh permit. Return [ceil waits in ms, stored, next_free] with exact fractions as strings.

split: open-access