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

N = 1
observations = []
def solve(x):
    Q = x['quota']
    W = x['window_s']
    L = x['chunk']
    win = None
    remaining = 0
    local = {}
    out = []
    for t, node, op in x['events']:
        w = t // W
        if w != win:
            win, remaining, local = w, Q, {}
        if op == 'return':
            local.pop(node, 0)
            out.append(remaining)
            continue
        if local.get(node, 0) == 0:
            grant = min(L, remaining)
            remaining -= grant
            local[node] = grant
        if local[node] > 0:
            local[node] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, remaining, sorted([k, v] for k, v in local.items())]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [3, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [14, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [2, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [5, 'a', 'req'],
               [6, 'b', 'req'],
               [10, 'a', 'return'],
               [14, 'a', 'return'],
               [20, 'b', 'req'],
               [23, 'b', 'req'],
               [24, 'b', 'req'],
               [24, 'b', 'return'],
               [25, 'a', 'req'],
               [25, 'b', 'req'],
               [31, 'b', 'return'],
               [38, 'a', 'req'],
               [38, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     3,
     3,
     'allow',
     'allow',
     'allow',
     2,
     'allow',
     'deny',
     8,
     'allow',
     'allow'],
    2,
    [['a', 2], ['b', 2]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [4, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [15, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [3, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[1, 'a', 'req'],
               [13, 'a', 'req'],
               [15, 'b', 'req'],
               [22, 'a', 'req'],
               [25, 'a', 'req'],
               [25, 'a', 'return'],
               [26, 'b', 'req'],
               [26, 'b', 'return'],
               [29, 'b', 'req'],
               [39, 'b', 'req'],
               [44, 'a', 'req'],
               [48, 'a', 'req'],
               [48, 'a', 'return'],
               [49, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow',
     2,
     'allow',
     'allow',
     'allow',
     'allow',
     3,
     'allow'],
    3,
    [['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [16, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [4, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'return'],
               [9, 'a', 'req'],
               [9, 'a', 'return'],
               [16, 'a', 'req'],
               [22, 'a', 'req'],
               [24, 'a', 'req'],
               [32, 'b', 'req'],
               [34, 'a', 'req'],
               [35, 'b', 'return'],
               [36, 'b', 'req'],
               [40, 'a', 'req'],
               [44, 'a', 'return'],
               [45, 'b', 'req'],
               [48, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     2,
     'allow',
     'allow'],
    0,
    [['a', 1], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [8, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [17, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [5, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[4, 'b', 'req'],
               [8, 'a', 'req'],
               [17, 'b', 'req'],
               [20, 'b', 'req'],
               [26, 'a', 'return'],
               [28, 'b', 'req'],
               [32, 'b', 'req'],
               [36, 'a', 'req'],
               [38, 'b', 'req'],
               [40, 'a', 'req'],
               [41, 'a', 'req'],
               [42, 'a', 'req'],
               [42, 'a', 'return'],
               [43, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow'],
    0,
    [['a', 0], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [9, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [18, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [6, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[8, 'b', 'return'],
               [10, 'b', 'req'],
               [11, 'a', 'req'],
               [11, 'a', 'return'],
               [14, 'b', 'req'],
               [25, 'a', 'req'],
               [26, 'b', 'req'],
               [35, 'a', 'req'],
               [35, 'a', 'return'],
               [39, 'a', 'req'],
               [40, 'a', 'req'],
               [43, 'b', 'req'],
               [44, 'b', 'return'],
               [47, 'a', 'return']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     3,
     4],
    4,
    []]]]]
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):
    Q = x['quota']
    W = x['window_s']
    L = x['chunk']
    win = None
    remaining = 0
    local = {}
    out = []
    for t, node, op in x['events']:
        w = t // W
        if w != win:
            win, remaining, local = w, Q, {}
        if op == 'return':
            remaining += L
            local.pop(node, 0)
            out.append(remaining)
            continue
        if local.get(node, 0) == 0:
            grant = min(L, remaining)
            remaining -= grant
            local[node] = grant
        if local[node] > 0:
            local[node] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, remaining, sorted([k, v] for k, v in local.items())]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [3, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [14, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [2, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [5, 'a', 'req'],
               [6, 'b', 'req'],
               [10, 'a', 'return'],
               [14, 'a', 'return'],
               [20, 'b', 'req'],
               [23, 'b', 'req'],
               [24, 'b', 'req'],
               [24, 'b', 'return'],
               [25, 'a', 'req'],
               [25, 'b', 'req'],
               [31, 'b', 'return'],
               [38, 'a', 'req'],
               [38, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     3,
     3,
     'allow',
     'allow',
     'allow',
     2,
     'allow',
     'deny',
     8,
     'allow',
     'allow'],
    2,
    [['a', 2], ['b', 2]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [4, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [15, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [3, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[1, 'a', 'req'],
               [13, 'a', 'req'],
               [15, 'b', 'req'],
               [22, 'a', 'req'],
               [25, 'a', 'req'],
               [25, 'a', 'return'],
               [26, 'b', 'req'],
               [26, 'b', 'return'],
               [29, 'b', 'req'],
               [39, 'b', 'req'],
               [44, 'a', 'req'],
               [48, 'a', 'req'],
               [48, 'a', 'return'],
               [49, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow',
     2,
     'allow',
     'allow',
     'allow',
     'allow',
     3,
     'allow'],
    3,
    [['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [16, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [4, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'return'],
               [9, 'a', 'req'],
               [9, 'a', 'return'],
               [16, 'a', 'req'],
               [22, 'a', 'req'],
               [24, 'a', 'req'],
               [32, 'b', 'req'],
               [34, 'a', 'req'],
               [35, 'b', 'return'],
               [36, 'b', 'req'],
               [40, 'a', 'req'],
               [44, 'a', 'return'],
               [45, 'b', 'req'],
               [48, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     2,
     'allow',
     'allow'],
    0,
    [['a', 1], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [8, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [17, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [5, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[4, 'b', 'req'],
               [8, 'a', 'req'],
               [17, 'b', 'req'],
               [20, 'b', 'req'],
               [26, 'a', 'return'],
               [28, 'b', 'req'],
               [32, 'b', 'req'],
               [36, 'a', 'req'],
               [38, 'b', 'req'],
               [40, 'a', 'req'],
               [41, 'a', 'req'],
               [42, 'a', 'req'],
               [42, 'a', 'return'],
               [43, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow'],
    0,
    [['a', 0], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [9, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [18, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [6, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[8, 'b', 'return'],
               [10, 'b', 'req'],
               [11, 'a', 'req'],
               [11, 'a', 'return'],
               [14, 'b', 'req'],
               [25, 'a', 'req'],
               [26, 'b', 'req'],
               [35, 'a', 'req'],
               [35, 'a', 'return'],
               [39, 'a', 'req'],
               [40, 'a', 'req'],
               [43, 'b', 'req'],
               [44, 'b', 'return'],
               [47, 'a', 'return']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     3,
     4],
    4,
    []]]]]
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:
Quota returned by draining nodes is lost for the rest of the window.

Input {quota, window_s, chunk, events [[t, node, "req"|"return"]]} with nondecreasing t. Each epoch window starts with the full global quota and voids all node leases. A node with an empty lease fetches min(chunk, remaining) from the coordinator; each request spends one leased unit or is denied when none is available. "return" credits the node's unused lease back and reports the new remaining. Return [results, remaining, sorted [node, lease]].

split: open-access


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

N = 1
observations = []
def solve(x):
    Q = x['quota']
    W = x['window_s']
    L = x['chunk']
    win = None
    remaining = 0
    local = {}
    out = []
    for t, node, op in x['events']:
        w = t // W
        if w != win:
            win, remaining = w, Q
        if op == 'return':
            remaining += local.pop(node, 0)
            out.append(remaining)
            continue
        if local.get(node, 0) == 0:
            grant = min(L, remaining)
            remaining -= grant
            local[node] = grant
        if local[node] > 0:
            local[node] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, remaining, sorted([k, v] for k, v in local.items())]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [3, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [14, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [2, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [5, 'a', 'req'],
               [6, 'b', 'req'],
               [10, 'a', 'return'],
               [14, 'a', 'return'],
               [20, 'b', 'req'],
               [23, 'b', 'req'],
               [24, 'b', 'req'],
               [24, 'b', 'return'],
               [25, 'a', 'req'],
               [25, 'b', 'req'],
               [31, 'b', 'return'],
               [38, 'a', 'req'],
               [38, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     3,
     3,
     'allow',
     'allow',
     'allow',
     2,
     'allow',
     'deny',
     8,
     'allow',
     'allow'],
    2,
    [['a', 2], ['b', 2]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [4, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [15, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [3, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[1, 'a', 'req'],
               [13, 'a', 'req'],
               [15, 'b', 'req'],
               [22, 'a', 'req'],
               [25, 'a', 'req'],
               [25, 'a', 'return'],
               [26, 'b', 'req'],
               [26, 'b', 'return'],
               [29, 'b', 'req'],
               [39, 'b', 'req'],
               [44, 'a', 'req'],
               [48, 'a', 'req'],
               [48, 'a', 'return'],
               [49, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow',
     2,
     'allow',
     'allow',
     'allow',
     'allow',
     3,
     'allow'],
    3,
    [['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [16, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [4, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'return'],
               [9, 'a', 'req'],
               [9, 'a', 'return'],
               [16, 'a', 'req'],
               [22, 'a', 'req'],
               [24, 'a', 'req'],
               [32, 'b', 'req'],
               [34, 'a', 'req'],
               [35, 'b', 'return'],
               [36, 'b', 'req'],
               [40, 'a', 'req'],
               [44, 'a', 'return'],
               [45, 'b', 'req'],
               [48, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     2,
     'allow',
     'allow'],
    0,
    [['a', 1], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [8, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [17, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [5, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[4, 'b', 'req'],
               [8, 'a', 'req'],
               [17, 'b', 'req'],
               [20, 'b', 'req'],
               [26, 'a', 'return'],
               [28, 'b', 'req'],
               [32, 'b', 'req'],
               [36, 'a', 'req'],
               [38, 'b', 'req'],
               [40, 'a', 'req'],
               [41, 'a', 'req'],
               [42, 'a', 'req'],
               [42, 'a', 'return'],
               [43, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow'],
    0,
    [['a', 0], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [9, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [18, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [6, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[8, 'b', 'return'],
               [10, 'b', 'req'],
               [11, 'a', 'req'],
               [11, 'a', 'return'],
               [14, 'b', 'req'],
               [25, 'a', 'req'],
               [26, 'b', 'req'],
               [35, 'a', 'req'],
               [35, 'a', 'return'],
               [39, 'a', 'req'],
               [40, 'a', 'req'],
               [43, 'b', 'req'],
               [44, 'b', 'return'],
               [47, 'a', 'return']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     3,
     4],
    4,
    []]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

N = 1
observations = []
def solve(x):
    Q = x['quota']
    W = x['window_s']
    L = x['chunk']
    win = None
    remaining = 0
    local = {}
    out = []
    for t, node, op in x['events']:
        w = t // W
        if w != win:
            win, local = w, {}
        if op == 'return':
            remaining += local.pop(node, 0)
            out.append(remaining)
            continue
        if local.get(node, 0) == 0:
            grant = min(L, remaining)
            remaining -= grant
            local[node] = grant
        if local[node] > 0:
            local[node] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, remaining, sorted([k, v] for k, v in local.items())]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [3, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [14, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [2, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [5, 'a', 'req'],
               [6, 'b', 'req'],
               [10, 'a', 'return'],
               [14, 'a', 'return'],
               [20, 'b', 'req'],
               [23, 'b', 'req'],
               [24, 'b', 'req'],
               [24, 'b', 'return'],
               [25, 'a', 'req'],
               [25, 'b', 'req'],
               [31, 'b', 'return'],
               [38, 'a', 'req'],
               [38, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     3,
     3,
     'allow',
     'allow',
     'allow',
     2,
     'allow',
     'deny',
     8,
     'allow',
     'allow'],
    2,
    [['a', 2], ['b', 2]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [4, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [15, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [3, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[1, 'a', 'req'],
               [13, 'a', 'req'],
               [15, 'b', 'req'],
               [22, 'a', 'req'],
               [25, 'a', 'req'],
               [25, 'a', 'return'],
               [26, 'b', 'req'],
               [26, 'b', 'return'],
               [29, 'b', 'req'],
               [39, 'b', 'req'],
               [44, 'a', 'req'],
               [48, 'a', 'req'],
               [48, 'a', 'return'],
               [49, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow',
     2,
     'allow',
     'allow',
     'allow',
     'allow',
     3,
     'allow'],
    3,
    [['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [16, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [4, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'return'],
               [9, 'a', 'req'],
               [9, 'a', 'return'],
               [16, 'a', 'req'],
               [22, 'a', 'req'],
               [24, 'a', 'req'],
               [32, 'b', 'req'],
               [34, 'a', 'req'],
               [35, 'b', 'return'],
               [36, 'b', 'req'],
               [40, 'a', 'req'],
               [44, 'a', 'return'],
               [45, 'b', 'req'],
               [48, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     2,
     'allow',
     'allow'],
    0,
    [['a', 1], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [8, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [17, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [5, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[4, 'b', 'req'],
               [8, 'a', 'req'],
               [17, 'b', 'req'],
               [20, 'b', 'req'],
               [26, 'a', 'return'],
               [28, 'b', 'req'],
               [32, 'b', 'req'],
               [36, 'a', 'req'],
               [38, 'b', 'req'],
               [40, 'a', 'req'],
               [41, 'a', 'req'],
               [42, 'a', 'req'],
               [42, 'a', 'return'],
               [43, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow'],
    0,
    [['a', 0], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [9, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [18, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [6, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[8, 'b', 'return'],
               [10, 'b', 'req'],
               [11, 'a', 'req'],
               [11, 'a', 'return'],
               [14, 'b', 'req'],
               [25, 'a', 'req'],
               [26, 'b', 'req'],
               [35, 'a', 'req'],
               [35, 'a', 'return'],
               [39, 'a', 'req'],
               [40, 'a', 'req'],
               [43, 'b', 'req'],
               [44, 'b', 'return'],
               [47, 'a', 'return']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     3,
     4],
    4,
    []]]]]
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:
Nodes spend last window's leftover lease on top of the new window's full quota.

Input {quota, window_s, chunk, events [[t, node, "req"|"return"]]} with nondecreasing t. Each epoch window starts with the full global quota and voids all node leases. A node with an empty lease fetches min(chunk, remaining) from the coordinator; each request spends one leased unit or is denied when none is available. "return" credits the node's unused lease back and reports the new remaining. Return [results, remaining, sorted [node, lease]].

split: open-access


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

N = 1
observations = []
def solve(x):
    Q = x['quota']
    W = x['window_s']
    L = x['chunk']
    win = None
    remaining = 0
    local = {}
    out = []
    for t, node, op in x['events']:
        w = t // W
        if w != win:
            win, remaining, local = w, Q, {}
        if op == 'return':
            remaining += local.pop(node, 0)
            out.append(remaining)
            continue
        if node not in local:
            grant = min(L, remaining)
            remaining -= grant
            local[node] = grant
        if local[node] > 0:
            local[node] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, remaining, sorted([k, v] for k, v in local.items())]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [3, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [14, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [2, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [5, 'a', 'req'],
               [6, 'b', 'req'],
               [10, 'a', 'return'],
               [14, 'a', 'return'],
               [20, 'b', 'req'],
               [23, 'b', 'req'],
               [24, 'b', 'req'],
               [24, 'b', 'return'],
               [25, 'a', 'req'],
               [25, 'b', 'req'],
               [31, 'b', 'return'],
               [38, 'a', 'req'],
               [38, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     3,
     3,
     'allow',
     'allow',
     'allow',
     2,
     'allow',
     'deny',
     8,
     'allow',
     'allow'],
    2,
    [['a', 2], ['b', 2]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [4, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [15, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [3, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[1, 'a', 'req'],
               [13, 'a', 'req'],
               [15, 'b', 'req'],
               [22, 'a', 'req'],
               [25, 'a', 'req'],
               [25, 'a', 'return'],
               [26, 'b', 'req'],
               [26, 'b', 'return'],
               [29, 'b', 'req'],
               [39, 'b', 'req'],
               [44, 'a', 'req'],
               [48, 'a', 'req'],
               [48, 'a', 'return'],
               [49, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow',
     2,
     'allow',
     'allow',
     'allow',
     'allow',
     3,
     'allow'],
    3,
    [['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [16, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [4, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'return'],
               [9, 'a', 'req'],
               [9, 'a', 'return'],
               [16, 'a', 'req'],
               [22, 'a', 'req'],
               [24, 'a', 'req'],
               [32, 'b', 'req'],
               [34, 'a', 'req'],
               [35, 'b', 'return'],
               [36, 'b', 'req'],
               [40, 'a', 'req'],
               [44, 'a', 'return'],
               [45, 'b', 'req'],
               [48, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     2,
     'allow',
     'allow'],
    0,
    [['a', 1], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [8, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [17, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [5, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[4, 'b', 'req'],
               [8, 'a', 'req'],
               [17, 'b', 'req'],
               [20, 'b', 'req'],
               [26, 'a', 'return'],
               [28, 'b', 'req'],
               [32, 'b', 'req'],
               [36, 'a', 'req'],
               [38, 'b', 'req'],
               [40, 'a', 'req'],
               [41, 'a', 'req'],
               [42, 'a', 'req'],
               [42, 'a', 'return'],
               [43, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow'],
    0,
    [['a', 0], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [9, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [18, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [6, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[8, 'b', 'return'],
               [10, 'b', 'req'],
               [11, 'a', 'req'],
               [11, 'a', 'return'],
               [14, 'b', 'req'],
               [25, 'a', 'req'],
               [26, 'b', 'req'],
               [35, 'a', 'req'],
               [35, 'a', 'return'],
               [39, 'a', 'req'],
               [40, 'a', 'req'],
               [43, 'b', 'req'],
               [44, 'b', 'return'],
               [47, 'a', 'return']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     3,
     4],
    4,
    []]]]]
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):
    Q = x['quota']
    W = x['window_s']
    L = x['chunk']
    win = None
    remaining = 0
    local = {}
    out = []
    for t, node, op in x['events']:
        w = t // W
        if w != win:
            win, remaining, local = w, Q, {}
        if op == 'return':
            remaining += local.pop(node, 0)
            out.append(remaining)
            continue
        if local.get(node, 0) <= 1:
            grant = min(L, remaining)
            remaining -= grant
            local[node] = grant
        if local[node] > 0:
            local[node] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, remaining, sorted([k, v] for k, v in local.items())]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [3, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [14, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [2, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [5, 'a', 'req'],
               [6, 'b', 'req'],
               [10, 'a', 'return'],
               [14, 'a', 'return'],
               [20, 'b', 'req'],
               [23, 'b', 'req'],
               [24, 'b', 'req'],
               [24, 'b', 'return'],
               [25, 'a', 'req'],
               [25, 'b', 'req'],
               [31, 'b', 'return'],
               [38, 'a', 'req'],
               [38, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     3,
     3,
     'allow',
     'allow',
     'allow',
     2,
     'allow',
     'deny',
     8,
     'allow',
     'allow'],
    2,
    [['a', 2], ['b', 2]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [4, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [15, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [3, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[1, 'a', 'req'],
               [13, 'a', 'req'],
               [15, 'b', 'req'],
               [22, 'a', 'req'],
               [25, 'a', 'req'],
               [25, 'a', 'return'],
               [26, 'b', 'req'],
               [26, 'b', 'return'],
               [29, 'b', 'req'],
               [39, 'b', 'req'],
               [44, 'a', 'req'],
               [48, 'a', 'req'],
               [48, 'a', 'return'],
               [49, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow',
     2,
     'allow',
     'allow',
     'allow',
     'allow',
     3,
     'allow'],
    3,
    [['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [16, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [4, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'return'],
               [9, 'a', 'req'],
               [9, 'a', 'return'],
               [16, 'a', 'req'],
               [22, 'a', 'req'],
               [24, 'a', 'req'],
               [32, 'b', 'req'],
               [34, 'a', 'req'],
               [35, 'b', 'return'],
               [36, 'b', 'req'],
               [40, 'a', 'req'],
               [44, 'a', 'return'],
               [45, 'b', 'req'],
               [48, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     2,
     'allow',
     'allow'],
    0,
    [['a', 1], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [8, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [17, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [5, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[4, 'b', 'req'],
               [8, 'a', 'req'],
               [17, 'b', 'req'],
               [20, 'b', 'req'],
               [26, 'a', 'return'],
               [28, 'b', 'req'],
               [32, 'b', 'req'],
               [36, 'a', 'req'],
               [38, 'b', 'req'],
               [40, 'a', 'req'],
               [41, 'a', 'req'],
               [42, 'a', 'req'],
               [42, 'a', 'return'],
               [43, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow'],
    0,
    [['a', 0], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [9, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [18, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [6, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[8, 'b', 'return'],
               [10, 'b', 'req'],
               [11, 'a', 'req'],
               [11, 'a', 'return'],
               [14, 'b', 'req'],
               [25, 'a', 'req'],
               [26, 'b', 'req'],
               [35, 'a', 'req'],
               [35, 'a', 'return'],
               [39, 'a', 'req'],
               [40, 'a', 'req'],
               [43, 'b', 'req'],
               [44, 'b', 'return'],
               [47, 'a', 'return']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     3,
     4],
    4,
    []]]]]
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 node that used up its first chunk denies everything for the rest of the window although quota remains.

Input {quota, window_s, chunk, events [[t, node, "req"|"return"]]} with nondecreasing t. Each epoch window starts with the full global quota and voids all node leases. A node with an empty lease fetches min(chunk, remaining) from the coordinator; each request spends one leased unit or is denied when none is available. "return" credits the node's unused lease back and reports the new remaining. Return [results, remaining, sorted [node, lease]].

split: open-access