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

N = 1
observations = []
def solve(x):
    cap = x['max_concurrent']
    D = x['lease_ms']
    held = {}
    out = []
    for t, op, ident in x['events']:
        for k in [k for k, s in held.items() if s + D <= t]:
            del held[k]
        if op == 'acquire':
            if ident in held:
                out.append('duplicate')
            elif len(held) < cap:
                held[ident] = t
                out.append('granted')
            else:
                out.append('rejected')
        else:
            if ident in held:
                del held[ident]
                out.append('released')
            else:
                if held:
                    del held[min(held, key=held.get)]
                out.append('released')
    return [out, sorted(held)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1501, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [41, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1001, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [301, 'release', 'a'], [302, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[8, 'acquire', 'b'],
               [172, 'acquire', 'c'],
               [317, 'acquire', 'd'],
               [462, 'acquire', 'a'],
               [606, 'acquire', 'c'],
               [769, 'acquire', 'd'],
               [900, 'acquire', 'a'],
               [1064, 'release', 'a'],
               [1238, 'release', 'b'],
               [1372, 'acquire', 'c'],
               [1516, 'acquire', 'c'],
               [1668, 'acquire', 'd']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'granted',
     'rejected',
     'rejected',
     'duplicate',
     'granted',
     'granted',
     'released',
     'unknown',
     'granted',
     'duplicate',
     'granted'],
    ['c', 'd']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [5, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1502, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [42, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1002, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [302, 'release', 'a'], [303, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[20, 'acquire', 'a'],
               [161, 'acquire', 'a'],
               [304, 'release', 'b'],
               [482, 'acquire', 'c'],
               [635, 'acquire', 'b'],
               [780, 'acquire', 'd'],
               [922, 'release', 'c'],
               [1055, 'acquire', 'a'],
               [1209, 'release', 'b'],
               [1366, 'release', 'a'],
               [1534, 'acquire', 'a'],
               [1689, 'acquire', 'b']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'duplicate',
     'unknown',
     'granted',
     'granted',
     'rejected',
     'released',
     'granted',
     'released',
     'released',
     'granted',
     'granted'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [6, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1503, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [43, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1003, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [303, 'release', 'a'], [304, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[7, 'acquire', 'a'],
               [186, 'release', 'a'],
               [319, 'acquire', 'a'],
               [456, 'acquire', 'c'],
               [610, 'acquire', 'a'],
               [778, 'acquire', 'd'],
               [935, 'acquire', 'c'],
               [1055, 'acquire', 'a'],
               [1219, 'release', 'a'],
               [1368, 'acquire', 'b'],
               [1500, 'acquire', 'a'],
               [1677, 'acquire', 'b']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'released',
     'granted',
     'granted',
     'duplicate',
     'rejected',
     'duplicate',
     'granted',
     'released',
     'granted',
     'granted',
     'duplicate'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [7, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1504, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [44, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1004, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [304, 'release', 'a'], [305, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[9, 'acquire', 'c'],
               [172, 'acquire', 'd'],
               [315, 'acquire', 'a'],
               [473, 'acquire', 'a'],
               [611, 'acquire', 'd'],
               [785, 'acquire', 'c'],
               [926, 'release', 'd'],
               [1088, 'release', 'd'],
               [1239, 'acquire', 'a'],
               [1373, 'release', 'b'],
               [1536, 'release', 'a'],
               [1672, 'acquire', 'a']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'granted',
     'rejected',
     'rejected',
     'duplicate',
     'granted',
     'unknown',
     'unknown',
     'granted',
     'unknown',
     'released',
     'granted'],
    ['a']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [8, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1505, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [45, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1005, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [305, 'release', 'a'], [306, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[14, 'acquire', 'b'],
               [177, 'release', 'a'],
               [334, 'release', 'd'],
               [476, 'acquire', 'a'],
               [631, 'release', 'a'],
               [764, 'acquire', 'b'],
               [901, 'acquire', 'a'],
               [1084, 'release', 'b'],
               [1200, 'acquire', 'b'],
               [1376, 'release', 'd'],
               [1506, 'release', 'a'],
               [1680, 'acquire', 'a']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'unknown',
     'unknown',
     'granted',
     'released',
     'granted',
     'granted',
     'released',
     'granted',
     'unknown',
     'unknown',
     'granted'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [9, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]]]
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):
    cap = x['max_concurrent']
    D = x['lease_ms']
    held = {}
    out = []
    for t, op, ident in x['events']:
        for k in [k for k, s in held.items() if s + D <= t]:
            del held[k]
        if op == 'acquire':
            if ident in held:
                out.append('duplicate')
            elif len(held) < cap:
                held[ident] = t
                out.append('granted')
            else:
                out.append('rejected')
        else:
            if ident in held:
                del held[ident]
                out.append('released')
            else:
                out.append('released')
    return [out, sorted(held)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1501, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [41, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1001, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [301, 'release', 'a'], [302, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[8, 'acquire', 'b'],
               [172, 'acquire', 'c'],
               [317, 'acquire', 'd'],
               [462, 'acquire', 'a'],
               [606, 'acquire', 'c'],
               [769, 'acquire', 'd'],
               [900, 'acquire', 'a'],
               [1064, 'release', 'a'],
               [1238, 'release', 'b'],
               [1372, 'acquire', 'c'],
               [1516, 'acquire', 'c'],
               [1668, 'acquire', 'd']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'granted',
     'rejected',
     'rejected',
     'duplicate',
     'granted',
     'granted',
     'released',
     'unknown',
     'granted',
     'duplicate',
     'granted'],
    ['c', 'd']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [5, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1502, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [42, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1002, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [302, 'release', 'a'], [303, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[20, 'acquire', 'a'],
               [161, 'acquire', 'a'],
               [304, 'release', 'b'],
               [482, 'acquire', 'c'],
               [635, 'acquire', 'b'],
               [780, 'acquire', 'd'],
               [922, 'release', 'c'],
               [1055, 'acquire', 'a'],
               [1209, 'release', 'b'],
               [1366, 'release', 'a'],
               [1534, 'acquire', 'a'],
               [1689, 'acquire', 'b']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'duplicate',
     'unknown',
     'granted',
     'granted',
     'rejected',
     'released',
     'granted',
     'released',
     'released',
     'granted',
     'granted'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [6, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1503, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [43, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1003, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [303, 'release', 'a'], [304, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[7, 'acquire', 'a'],
               [186, 'release', 'a'],
               [319, 'acquire', 'a'],
               [456, 'acquire', 'c'],
               [610, 'acquire', 'a'],
               [778, 'acquire', 'd'],
               [935, 'acquire', 'c'],
               [1055, 'acquire', 'a'],
               [1219, 'release', 'a'],
               [1368, 'acquire', 'b'],
               [1500, 'acquire', 'a'],
               [1677, 'acquire', 'b']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'released',
     'granted',
     'granted',
     'duplicate',
     'rejected',
     'duplicate',
     'granted',
     'released',
     'granted',
     'granted',
     'duplicate'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [7, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1504, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [44, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1004, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [304, 'release', 'a'], [305, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[9, 'acquire', 'c'],
               [172, 'acquire', 'd'],
               [315, 'acquire', 'a'],
               [473, 'acquire', 'a'],
               [611, 'acquire', 'd'],
               [785, 'acquire', 'c'],
               [926, 'release', 'd'],
               [1088, 'release', 'd'],
               [1239, 'acquire', 'a'],
               [1373, 'release', 'b'],
               [1536, 'release', 'a'],
               [1672, 'acquire', 'a']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'granted',
     'rejected',
     'rejected',
     'duplicate',
     'granted',
     'unknown',
     'unknown',
     'granted',
     'unknown',
     'released',
     'granted'],
    ['a']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [8, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1505, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [45, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1005, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [305, 'release', 'a'], [306, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[14, 'acquire', 'b'],
               [177, 'release', 'a'],
               [334, 'release', 'd'],
               [476, 'acquire', 'a'],
               [631, 'release', 'a'],
               [764, 'acquire', 'b'],
               [901, 'acquire', 'a'],
               [1084, 'release', 'b'],
               [1200, 'acquire', 'b'],
               [1376, 'release', 'd'],
               [1506, 'release', 'a'],
               [1680, 'acquire', 'a']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'unknown',
     'unknown',
     'granted',
     'released',
     'granted',
     'granted',
     'released',
     'granted',
     'unknown',
     'unknown',
     'granted'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [9, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]]]
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 stray release from a client that never acquired evicts the oldest legitimate holder.

Input {max_concurrent, lease_ms, events [[t, op, id]]}. Before every event, leases with start + lease_ms <= t expire. acquire returns "duplicate" (no change) for a held id, "granted" (recording t) when fewer than max_concurrent leases are held, else "rejected". release returns "released" for a held id and "unknown" otherwise, changing nothing. Return [results, sorted held ids].

split: open-access


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

N = 1
observations = []
def solve(x):
    cap = x['max_concurrent']
    D = x['lease_ms']
    held = {}
    out = []
    for t, op, ident in x['events']:
        for k in [k for k, s in held.items() if s + D <= t]:
            del held[k]
        if op == 'acquire':
            if ident in held and len(held) >= cap:
                out.append('duplicate')
            elif len(held) < cap:
                held[ident] = t
                out.append('granted')
            else:
                out.append('rejected')
        else:
            if ident in held:
                del held[ident]
                out.append('released')
            else:
                out.append('unknown')
    return [out, sorted(held)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1501, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [41, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1001, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [301, 'release', 'a'], [302, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[8, 'acquire', 'b'],
               [172, 'acquire', 'c'],
               [317, 'acquire', 'd'],
               [462, 'acquire', 'a'],
               [606, 'acquire', 'c'],
               [769, 'acquire', 'd'],
               [900, 'acquire', 'a'],
               [1064, 'release', 'a'],
               [1238, 'release', 'b'],
               [1372, 'acquire', 'c'],
               [1516, 'acquire', 'c'],
               [1668, 'acquire', 'd']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'granted',
     'rejected',
     'rejected',
     'duplicate',
     'granted',
     'granted',
     'released',
     'unknown',
     'granted',
     'duplicate',
     'granted'],
    ['c', 'd']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [5, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1502, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [42, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1002, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [302, 'release', 'a'], [303, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[20, 'acquire', 'a'],
               [161, 'acquire', 'a'],
               [304, 'release', 'b'],
               [482, 'acquire', 'c'],
               [635, 'acquire', 'b'],
               [780, 'acquire', 'd'],
               [922, 'release', 'c'],
               [1055, 'acquire', 'a'],
               [1209, 'release', 'b'],
               [1366, 'release', 'a'],
               [1534, 'acquire', 'a'],
               [1689, 'acquire', 'b']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'duplicate',
     'unknown',
     'granted',
     'granted',
     'rejected',
     'released',
     'granted',
     'released',
     'released',
     'granted',
     'granted'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [6, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1503, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [43, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1003, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [303, 'release', 'a'], [304, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[7, 'acquire', 'a'],
               [186, 'release', 'a'],
               [319, 'acquire', 'a'],
               [456, 'acquire', 'c'],
               [610, 'acquire', 'a'],
               [778, 'acquire', 'd'],
               [935, 'acquire', 'c'],
               [1055, 'acquire', 'a'],
               [1219, 'release', 'a'],
               [1368, 'acquire', 'b'],
               [1500, 'acquire', 'a'],
               [1677, 'acquire', 'b']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'released',
     'granted',
     'granted',
     'duplicate',
     'rejected',
     'duplicate',
     'granted',
     'released',
     'granted',
     'granted',
     'duplicate'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [7, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1504, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [44, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1004, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [304, 'release', 'a'], [305, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[9, 'acquire', 'c'],
               [172, 'acquire', 'd'],
               [315, 'acquire', 'a'],
               [473, 'acquire', 'a'],
               [611, 'acquire', 'd'],
               [785, 'acquire', 'c'],
               [926, 'release', 'd'],
               [1088, 'release', 'd'],
               [1239, 'acquire', 'a'],
               [1373, 'release', 'b'],
               [1536, 'release', 'a'],
               [1672, 'acquire', 'a']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'granted',
     'rejected',
     'rejected',
     'duplicate',
     'granted',
     'unknown',
     'unknown',
     'granted',
     'unknown',
     'released',
     'granted'],
    ['a']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [8, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1505, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [45, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1005, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [305, 'release', 'a'], [306, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[14, 'acquire', 'b'],
               [177, 'release', 'a'],
               [334, 'release', 'd'],
               [476, 'acquire', 'a'],
               [631, 'release', 'a'],
               [764, 'acquire', 'b'],
               [901, 'acquire', 'a'],
               [1084, 'release', 'b'],
               [1200, 'acquire', 'b'],
               [1376, 'release', 'd'],
               [1506, 'release', 'a'],
               [1680, 'acquire', 'a']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'unknown',
     'unknown',
     'granted',
     'released',
     'granted',
     'granted',
     'released',
     'granted',
     'unknown',
     'unknown',
     'granted'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [9, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]]]
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):
    cap = x['max_concurrent']
    D = x['lease_ms']
    held = {}
    out = []
    for t, op, ident in x['events']:
        for k in [k for k, s in held.items() if s + D <= t]:
            del held[k]
        if op == 'acquire':
            if ident in held:
                held[ident] = t
                out.append('duplicate')
            elif len(held) < cap:
                held[ident] = t
                out.append('granted')
            else:
                out.append('rejected')
        else:
            if ident in held:
                del held[ident]
                out.append('released')
            else:
                out.append('unknown')
    return [out, sorted(held)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1501, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [41, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1001, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [301, 'release', 'a'], [302, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[8, 'acquire', 'b'],
               [172, 'acquire', 'c'],
               [317, 'acquire', 'd'],
               [462, 'acquire', 'a'],
               [606, 'acquire', 'c'],
               [769, 'acquire', 'd'],
               [900, 'acquire', 'a'],
               [1064, 'release', 'a'],
               [1238, 'release', 'b'],
               [1372, 'acquire', 'c'],
               [1516, 'acquire', 'c'],
               [1668, 'acquire', 'd']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'granted',
     'rejected',
     'rejected',
     'duplicate',
     'granted',
     'granted',
     'released',
     'unknown',
     'granted',
     'duplicate',
     'granted'],
    ['c', 'd']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [5, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1502, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [42, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1002, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [302, 'release', 'a'], [303, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[20, 'acquire', 'a'],
               [161, 'acquire', 'a'],
               [304, 'release', 'b'],
               [482, 'acquire', 'c'],
               [635, 'acquire', 'b'],
               [780, 'acquire', 'd'],
               [922, 'release', 'c'],
               [1055, 'acquire', 'a'],
               [1209, 'release', 'b'],
               [1366, 'release', 'a'],
               [1534, 'acquire', 'a'],
               [1689, 'acquire', 'b']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'duplicate',
     'unknown',
     'granted',
     'granted',
     'rejected',
     'released',
     'granted',
     'released',
     'released',
     'granted',
     'granted'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [6, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1503, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [43, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1003, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [303, 'release', 'a'], [304, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[7, 'acquire', 'a'],
               [186, 'release', 'a'],
               [319, 'acquire', 'a'],
               [456, 'acquire', 'c'],
               [610, 'acquire', 'a'],
               [778, 'acquire', 'd'],
               [935, 'acquire', 'c'],
               [1055, 'acquire', 'a'],
               [1219, 'release', 'a'],
               [1368, 'acquire', 'b'],
               [1500, 'acquire', 'a'],
               [1677, 'acquire', 'b']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'released',
     'granted',
     'granted',
     'duplicate',
     'rejected',
     'duplicate',
     'granted',
     'released',
     'granted',
     'granted',
     'duplicate'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [7, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1504, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [44, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1004, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [304, 'release', 'a'], [305, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[9, 'acquire', 'c'],
               [172, 'acquire', 'd'],
               [315, 'acquire', 'a'],
               [473, 'acquire', 'a'],
               [611, 'acquire', 'd'],
               [785, 'acquire', 'c'],
               [926, 'release', 'd'],
               [1088, 'release', 'd'],
               [1239, 'acquire', 'a'],
               [1373, 'release', 'b'],
               [1536, 'release', 'a'],
               [1672, 'acquire', 'a']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'granted',
     'rejected',
     'rejected',
     'duplicate',
     'granted',
     'unknown',
     'unknown',
     'granted',
     'unknown',
     'released',
     'granted'],
    ['a']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [8, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1505, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [45, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1005, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [305, 'release', 'a'], [306, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[14, 'acquire', 'b'],
               [177, 'release', 'a'],
               [334, 'release', 'd'],
               [476, 'acquire', 'a'],
               [631, 'release', 'a'],
               [764, 'acquire', 'b'],
               [901, 'acquire', 'a'],
               [1084, 'release', 'b'],
               [1200, 'acquire', 'b'],
               [1376, 'release', 'd'],
               [1506, 'release', 'a'],
               [1680, 'acquire', 'a']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'unknown',
     'unknown',
     'granted',
     'released',
     'granted',
     'granted',
     'released',
     'granted',
     'unknown',
     'unknown',
     'granted'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [9, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]]]
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 holder re-acquiring extends its lease indefinitely and is told it was granted a new slot.

Input {max_concurrent, lease_ms, events [[t, op, id]]}. Before every event, leases with start + lease_ms <= t expire. acquire returns "duplicate" (no change) for a held id, "granted" (recording t) when fewer than max_concurrent leases are held, else "rejected". release returns "released" for a held id and "unknown" otherwise, changing nothing. Return [results, sorted held ids].

split: open-access


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

N = 1
observations = []
def solve(x):
    cap = x['max_concurrent']
    D = x['lease_ms']
    held = {}
    out = []
    for t, op, ident in x['events']:
        if op == 'acquire':
            for k in [k for k, s in held.items() if s + D <= t]:
                del held[k]
            if ident in held:
                out.append('duplicate')
            elif len(held) < cap:
                held[ident] = t
                out.append('granted')
            else:
                out.append('rejected')
        else:
            if ident in held:
                del held[ident]
                out.append('released')
            else:
                out.append('unknown')
    return [out, sorted(held)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1501, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [41, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1001, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [301, 'release', 'a'], [302, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[8, 'acquire', 'b'],
               [172, 'acquire', 'c'],
               [317, 'acquire', 'd'],
               [462, 'acquire', 'a'],
               [606, 'acquire', 'c'],
               [769, 'acquire', 'd'],
               [900, 'acquire', 'a'],
               [1064, 'release', 'a'],
               [1238, 'release', 'b'],
               [1372, 'acquire', 'c'],
               [1516, 'acquire', 'c'],
               [1668, 'acquire', 'd']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'granted',
     'rejected',
     'rejected',
     'duplicate',
     'granted',
     'granted',
     'released',
     'unknown',
     'granted',
     'duplicate',
     'granted'],
    ['c', 'd']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [5, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1502, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [42, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1002, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [302, 'release', 'a'], [303, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[20, 'acquire', 'a'],
               [161, 'acquire', 'a'],
               [304, 'release', 'b'],
               [482, 'acquire', 'c'],
               [635, 'acquire', 'b'],
               [780, 'acquire', 'd'],
               [922, 'release', 'c'],
               [1055, 'acquire', 'a'],
               [1209, 'release', 'b'],
               [1366, 'release', 'a'],
               [1534, 'acquire', 'a'],
               [1689, 'acquire', 'b']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'duplicate',
     'unknown',
     'granted',
     'granted',
     'rejected',
     'released',
     'granted',
     'released',
     'released',
     'granted',
     'granted'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [6, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1503, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [43, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1003, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [303, 'release', 'a'], [304, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[7, 'acquire', 'a'],
               [186, 'release', 'a'],
               [319, 'acquire', 'a'],
               [456, 'acquire', 'c'],
               [610, 'acquire', 'a'],
               [778, 'acquire', 'd'],
               [935, 'acquire', 'c'],
               [1055, 'acquire', 'a'],
               [1219, 'release', 'a'],
               [1368, 'acquire', 'b'],
               [1500, 'acquire', 'a'],
               [1677, 'acquire', 'b']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'released',
     'granted',
     'granted',
     'duplicate',
     'rejected',
     'duplicate',
     'granted',
     'released',
     'granted',
     'granted',
     'duplicate'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [7, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1504, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [44, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1004, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [304, 'release', 'a'], [305, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[9, 'acquire', 'c'],
               [172, 'acquire', 'd'],
               [315, 'acquire', 'a'],
               [473, 'acquire', 'a'],
               [611, 'acquire', 'd'],
               [785, 'acquire', 'c'],
               [926, 'release', 'd'],
               [1088, 'release', 'd'],
               [1239, 'acquire', 'a'],
               [1373, 'release', 'b'],
               [1536, 'release', 'a'],
               [1672, 'acquire', 'a']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'granted',
     'rejected',
     'rejected',
     'duplicate',
     'granted',
     'unknown',
     'unknown',
     'granted',
     'unknown',
     'released',
     'granted'],
    ['a']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [8, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1505, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [45, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1005, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [305, 'release', 'a'], [306, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[14, 'acquire', 'b'],
               [177, 'release', 'a'],
               [334, 'release', 'd'],
               [476, 'acquire', 'a'],
               [631, 'release', 'a'],
               [764, 'acquire', 'b'],
               [901, 'acquire', 'a'],
               [1084, 'release', 'b'],
               [1200, 'acquire', 'b'],
               [1376, 'release', 'd'],
               [1506, 'release', 'a'],
               [1680, 'acquire', 'a']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'unknown',
     'unknown',
     'granted',
     'released',
     'granted',
     'granted',
     'released',
     'granted',
     'unknown',
     'unknown',
     'granted'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [9, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]]]
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):
    cap = x['max_concurrent']
    D = x['lease_ms']
    held = {}
    out = []
    for t, op, ident in x['events']:
        for k in [k for k, s in held.items() if s + D <= t and k != ident]:
            del held[k]
        if op == 'acquire':
            if ident in held:
                out.append('duplicate')
            elif len(held) < cap:
                held[ident] = t
                out.append('granted')
            else:
                out.append('rejected')
        else:
            if ident in held:
                del held[ident]
                out.append('released')
            else:
                out.append('unknown')
    return [out, sorted(held)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1501, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [41, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1001, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [301, 'release', 'a'], [302, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[8, 'acquire', 'b'],
               [172, 'acquire', 'c'],
               [317, 'acquire', 'd'],
               [462, 'acquire', 'a'],
               [606, 'acquire', 'c'],
               [769, 'acquire', 'd'],
               [900, 'acquire', 'a'],
               [1064, 'release', 'a'],
               [1238, 'release', 'b'],
               [1372, 'acquire', 'c'],
               [1516, 'acquire', 'c'],
               [1668, 'acquire', 'd']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'granted',
     'rejected',
     'rejected',
     'duplicate',
     'granted',
     'granted',
     'released',
     'unknown',
     'granted',
     'duplicate',
     'granted'],
    ['c', 'd']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [5, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1502, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [42, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1002, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [302, 'release', 'a'], [303, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[20, 'acquire', 'a'],
               [161, 'acquire', 'a'],
               [304, 'release', 'b'],
               [482, 'acquire', 'c'],
               [635, 'acquire', 'b'],
               [780, 'acquire', 'd'],
               [922, 'release', 'c'],
               [1055, 'acquire', 'a'],
               [1209, 'release', 'b'],
               [1366, 'release', 'a'],
               [1534, 'acquire', 'a'],
               [1689, 'acquire', 'b']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'duplicate',
     'unknown',
     'granted',
     'granted',
     'rejected',
     'released',
     'granted',
     'released',
     'released',
     'granted',
     'granted'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [6, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1503, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [43, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1003, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [303, 'release', 'a'], [304, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[7, 'acquire', 'a'],
               [186, 'release', 'a'],
               [319, 'acquire', 'a'],
               [456, 'acquire', 'c'],
               [610, 'acquire', 'a'],
               [778, 'acquire', 'd'],
               [935, 'acquire', 'c'],
               [1055, 'acquire', 'a'],
               [1219, 'release', 'a'],
               [1368, 'acquire', 'b'],
               [1500, 'acquire', 'a'],
               [1677, 'acquire', 'b']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'released',
     'granted',
     'granted',
     'duplicate',
     'rejected',
     'duplicate',
     'granted',
     'released',
     'granted',
     'granted',
     'duplicate'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [7, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1504, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [44, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1004, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [304, 'release', 'a'], [305, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[9, 'acquire', 'c'],
               [172, 'acquire', 'd'],
               [315, 'acquire', 'a'],
               [473, 'acquire', 'a'],
               [611, 'acquire', 'd'],
               [785, 'acquire', 'c'],
               [926, 'release', 'd'],
               [1088, 'release', 'd'],
               [1239, 'acquire', 'a'],
               [1373, 'release', 'b'],
               [1536, 'release', 'a'],
               [1672, 'acquire', 'a']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'granted',
     'rejected',
     'rejected',
     'duplicate',
     'granted',
     'unknown',
     'unknown',
     'granted',
     'unknown',
     'released',
     'granted'],
    ['a']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [8, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],
 [['lease expires exactly',
   {'events': [[0, 'acquire', 'a'],
               [999, 'acquire', 'b'],
               [1000, 'acquire', 'b'],
               [1505, 'release', 'b']],
    'lease_ms': 1000,
    'max_concurrent': 1},
   [['granted', 'rejected', 'granted', 'released'], []]],
  ['unknown release',
   {'events': [[0, 'acquire', 'a'],
               [10, 'acquire', 'b'],
               [20, 'release', 'zz'],
               [30, 'acquire', 'c'],
               [45, 'release', 'a']],
    'lease_ms': 5000,
    'max_concurrent': 2},
   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],
  ['duplicate acquire',
   {'events': [[0, 'acquire', 'a'],
               [800, 'acquire', 'a'],
               [1005, 'acquire', 'b'],
               [1100, 'acquire', 'c']],
    'lease_ms': 1000,
    'max_concurrent': 2},
   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],
  ['release after expiry',
   {'events': [[0, 'acquire', 'a'], [305, 'release', 'a'], [306, 'acquire', 'b']],
    'lease_ms': 300,
    'max_concurrent': 1},
   [['granted', 'unknown', 'granted'], ['b']]],
  ['random leases',
   {'events': [[14, 'acquire', 'b'],
               [177, 'release', 'a'],
               [334, 'release', 'd'],
               [476, 'acquire', 'a'],
               [631, 'release', 'a'],
               [764, 'acquire', 'b'],
               [901, 'acquire', 'a'],
               [1084, 'release', 'b'],
               [1200, 'acquire', 'b'],
               [1376, 'release', 'd'],
               [1506, 'release', 'a'],
               [1680, 'acquire', 'a']],
    'lease_ms': 600,
    'max_concurrent': 2},
   [['granted',
     'unknown',
     'unknown',
     'granted',
     'released',
     'granted',
     'granted',
     'released',
     'granted',
     'unknown',
     'unknown',
     'granted'],
    ['a', 'b']]],
  ['full pool',
   {'events': [[0, 'acquire', 'a'],
               [1, 'acquire', 'b'],
               [2, 'acquire', 'c'],
               [3, 'release', 'a'],
               [9, 'acquire', 'c']],
    'lease_ms': 10000,
    'max_concurrent': 2},
   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]]]
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:
Releasing an already expired lease is reported as a successful release.

Input {max_concurrent, lease_ms, events [[t, op, id]]}. Before every event, leases with start + lease_ms <= t expire. acquire returns "duplicate" (no change) for a held id, "granted" (recording t) when fewer than max_concurrent leases are held, else "rejected". release returns "released" for a held id and "unknown" otherwise, changing nothing. Return [results, sorted held ids].

split: open-access


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

N = 1
observations = []
def solve(x):
    th = x['threshold']
    Wn = x['window_s']
    base = x['ban_s']
    fails = []
    until = None
    strikes = 0
    out = []
    for t, ok in x['events']:
        if until is not None and t <= until:
            out.append('banned')
            continue
        if ok:
            out.append('ok')
            continue
        fails = [f for f in fails if f > t - Wn] + [t]
        if len(fails) >= th:
            until = t + base * 2 ** strikes
            strikes += 1
            fails = []
            out.append('ban-until-%d' % until)
        else:
            out.append('fail')
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['ban and escalate',
   {'ban_s': 10,
    'events': [[0, False],
               [1, False],
               [2, False],
               [5, False],
               [12, False],
               [13, False],
               [14, False],
               [31, False],
               [40, True]],
    'threshold': 3,
    'window_s': 60},
   ['fail', 'fail', 'ban-until-12', 'banned', 'fail', 'fail', 'ban-until-34', 'banned', 'ok']],
  ['third ban escalates',
   {'ban_s': 10,
    'events': [[0, False], [10, False], [30, False], [65, True], [71, True]],
    'threshold': 1,
    'window_s': 5},
   ['ban-until-10', 'ban-until-30', 'ban-until-70', 'banned', 'ok']],
  ['ban end instant',
   {'ban_s': 20,
    'events': [[0, False], [1, False], [20, True], [21, True], [23, False]],
    'threshold': 2,
    'window_s': 30},
   ['fail', 'ban-until-21', 'banned', 'ok', 'fail']],
  ['window prune boundary',
   {'ban_s': 5,
    'events': [[0, False], [10, False], [12, False], [30, False]],
    'threshold': 2,
    'window_s': 10},
   ['fail', 'fail', 'ban-until-17', 'fail']],
  ['failures cleared by ban',
   {'ban_s': 5,
    'events': [[0, False], [1, False], [2, False], [7, False], [9, False], [10, True]],
    'threshold': 3,
    'window_s': 100},
   ['fail', 'fail', 'ban-until-7', 'fail', 'fail', 'ok']],
  ['banned failures ignored',
   {'ban_s': 10,
    'events': [[0, False], [1, False], [5, False], [6, False], [11, False], [13, True]],
    'threshold': 2,
    'window_s': 100},
   ['fail', 'ban-until-11', 'banned', 'banned', 'fail', 'ok']],
  ['random attempts',
   {'ban_s': 15,
    'events': [[10, False],
               [13, False],
               [16, False],
               [20, False],
               [52, False],
               [53, False],
               [57, False],
               [74, False],
               [80, False],
               [87, False],
               [106, False],
               [115, True],
               [116, False],
               [119, True]],
    'threshold': 3,
    'window_s': 20},
   ['fail',
    'fail',
    'ban-until-31',
    'banned',
    'fail',
    'fail',
    'ban-until-87',
    'banned',
    'banned',
    'fail',
    'fail',
    'ok',
    'fail',
    'ok']]],
 [['ban and escalate',
   {'ban_s': 10,
    'events': [[0, False],
               [1, False],
               [2, False],
               [5, False],
               [12, False],
               [13, False],
               [14, False],
               [32, False],
               [40, True]],
    'threshold': 3,
    'window_s': 60},
   ['fail', 'fail', 'ban-until-12', 'banned', 'fail', 'fail', 'ban-until-34', 'banned', 'ok']],
  ['third ban escalates',
   {'ban_s': 10,
    'events': [[0, False], [10, False], [30, False], [65, True], [72, True]],
    'threshold': 1,
    'window_s': 5},
   ['ban-until-10', 'ban-until-30', 'ban-until-70', 'banned', 'ok']],
  ['ban end instant',
   {'ban_s': 20,
    'events': [[0, False], [1, False], [20, True], [21, True], [24, False]],
    'threshold': 2,
    'window_s': 30},
   ['fail', 'ban-until-21', 'banned', 'ok', 'fail']],
  ['window prune boundary',
   {'ban_s': 5,
    'events': [[0, False], [10, False], [13, False], [30, False]],
    'threshold': 2,
    'window_s': 10},
   ['fail', 'fail', 'ban-until-18', 'fail']],
  ['failures cleared by ban',
   {'ban_s': 5,
    'events': [[0, False], [1, False], [2, False], [7, False], [10, False], [11, True]],
    'threshold': 3,
    'window_s': 100},
   ['fail', 'fail', 'ban-until-7', 'fail', 'fail', 'ok']],
  ['banned failures ignored',
   {'ban_s': 10,
    'events': [[0, False], [1, False], [5, False], [6, False], [11, False], [14, True]],
    'threshold': 2,
    'window_s': 100},
   ['fail', 'ban-until-11', 'banned', 'banned', 'fail', 'ok']],
  ['random attempts',
   {'ban_s': 15,
    'events': [[0, False],
               [23, False],
               [25, True],
               [34, False],
               [35, False],
               [49, False],
               [49, True],
               [60, False],
               [71, False],
               [83, False],
               [87, False],
               [87, False],
               [89, False],
               [117, False]],
    'threshold': 3,
    'window_s': 20},
   ['fail',
    'fail',
    'ok',
    'fail',
    'ban-until-50',
    'banned',
    'banned',
    'fail',
    'fail',
    'fail',
    'ban-until-117',
    'banned',
    'banned',
    'fail']]],
 [['ban and escalate',
   {'ban_s': 10,
    'events': [[0, False],
               [1, False],
               [2, False],
               [5, False],
               [12, False],
               [13, False],
               [14, False],
               [33, False],
               [40, True]],
    'threshold': 3,
    'window_s': 60},
   ['fail', 'fail', 'ban-until-12', 'banned', 'fail', 'fail', 'ban-until-34', 'banned', 'ok']],
  ['third ban escalates',
   {'ban_s': 10,
    'events': [[0, False], [10, False], [30, False], [65, True], [73, True]],
    'threshold': 1,
    'window_s': 5},
   ['ban-until-10', 'ban-until-30', 'ban-until-70', 'banned', 'ok']],
  ['ban end instant',
   {'ban_s': 20,
    'events': [[0, False], [1, False], [20, True], [21, True], [25, False]],
    'threshold': 2,
    'window_s': 30},
   ['fail', 'ban-until-21', 'banned', 'ok', 'fail']],
  ['window prune boundary',
   {'ban_s': 5,
    'events': [[0, False], [10, False], [14, False], [30, False]],
    'threshold': 2,
    'window_s': 10},
   ['fail', 'fail', 'ban-until-19', 'fail']],
  ['failures cleared by ban',
   {'ban_s': 5,
    'events': [[0, False], [1, False], [2, False], [7, False], [11, False], [12, True]],
    'threshold': 3,
    'window_s': 100},
   ['fail', 'fail', 'ban-until-7', 'fail', 'fail', 'ok']],
  ['banned failures ignored',
   {'ban_s': 10,
    'events': [[0, False], [1, False], [5, False], [6, False], [11, False], [15, True]],
    'threshold': 2,
    'window_s': 100},
   ['fail', 'ban-until-11', 'banned', 'banned', 'fail', 'ok']],
  ['random attempts',
   {'ban_s': 15,
    'events': [[8, False],
               [30, False],
               [30, False],
               [39, True],
               [44, False],
               [45, True],
               [47, False],
               [58, True],
               [78, False],
               [78, False],
               [82, False],
               [90, False],
               [107, False],
               [119, False]],
    'threshold': 3,
    'window_s': 20},
   ['fail',
    'fail',
    'fail',
    'ok',
    'ban-until-59',
    'banned',
    'banned',
    'banned',
    'fail',
    'fail',
    'ban-until-112',
    'banned',
    'banned',
    'fail']]],
 [['ban and escalate',
   {'ban_s': 10,
    'events': [[0, False],
               [1, False],
               [2, False],
               [5, False],
               [12, False],
               [13, False],
               [14, False],
               [34, False],
               [40, True]],
    'threshold': 3,
    'window_s': 60},
   ['fail', 'fail', 'ban-until-12', 'banned', 'fail', 'fail', 'ban-until-34', 'fail', 'ok']],
  ['third ban escalates',
   {'ban_s': 10,
    'events': [[0, False], [10, False], [30, False], [65, True], [74, True]],
    'threshold': 1,
    'window_s': 5},
   ['ban-until-10', 'ban-until-30', 'ban-until-70', 'banned', 'ok']],
  ['ban end instant',
   {'ban_s': 20,
    'events': [[0, False], [1, False], [20, True], [21, True], [26, False]],
    'threshold': 2,
    'window_s': 30},
   ['fail', 'ban-until-21', 'banned', 'ok', 'fail']],
  ['window prune boundary',
   {'ban_s': 5,
    'events': [[0, False], [10, False], [15, False], [30, False]],
    'threshold': 2,
    'window_s': 10},
   ['fail', 'fail', 'ban-until-20', 'fail']],
  ['failures cleared by ban',
   {'ban_s': 5,
    'events': [[0, False], [1, False], [2, False], [7, False], [12, False], [13, True]],
    'threshold': 3,
    'window_s': 100},
   ['fail', 'fail', 'ban-until-7', 'fail', 'fail', 'ok']],
  ['banned failures ignored',
   {'ban_s': 10,
    'events': [[0, False], [1, False], [5, False], [6, False], [11, False], [16, True]],
    'threshold': 2,
    'window_s': 100},
   ['fail', 'ban-until-11', 'banned', 'banned', 'fail', 'ok']],
  ['random attempts',
   {'ban_s': 15,
    'events': [[6, False],
               [17, False],
               [25, False],
               [51, False],
               [52, True],
               [68, True],
               [78, True],
               [79, False],
               [86, True],
               [90, False],
               [92, True],
               [96, False],
               [100, False],
               [110, False]],
    'threshold': 3,
    'window_s': 20},
   ['fail',
    'fail',
    'ban-until-40',
    'fail',
    'ok',
    'ok',
    'ok',
    'fail',
    'ok',
    'fail',
    'ok',
    'ban-until-126',
    'banned',
    'banned']]],
 [['ban and escalate',
   {'ban_s': 10,
    'events': [[0, False],
               [1, False],
               [2, False],
               [5, False],
               [12, False],
               [13, False],
               [14, False],
               [35, False],
               [40, True]],
    'threshold': 3,
    'window_s': 60},
   ['fail', 'fail', 'ban-until-12', 'banned', 'fail', 'fail', 'ban-until-34', 'fail', 'ok']],
  ['third ban escalates',
   {'ban_s': 10,
    'events': [[0, False], [10, False], [30, False], [65, True], [75, True]],
    'threshold': 1,
    'window_s': 5},
   ['ban-until-10', 'ban-until-30', 'ban-until-70', 'banned', 'ok']],
  ['ban end instant',
   {'ban_s': 20,
    'events': [[0, False], [1, False], [20, True], [21, True], [27, False]],
    'threshold': 2,
    'window_s': 30},
   ['fail', 'ban-until-21', 'banned', 'ok', 'fail']],
  ['window prune boundary',
   {'ban_s': 5,
    'events': [[0, False], [10, False], [16, False], [30, False]],
    'threshold': 2,
    'window_s': 10},
   ['fail', 'fail', 'ban-until-21', 'fail']],
  ['failures cleared by ban',
   {'ban_s': 5,
    'events': [[0, False], [1, False], [2, False], [7, False], [13, False], [14, True]],
    'threshold': 3,
    'window_s': 100},
   ['fail', 'fail', 'ban-until-7', 'fail', 'fail', 'ok']],
  ['banned failures ignored',
   {'ban_s': 10,
    'events': [[0, False], [1, False], [5, False], [6, False], [11, False], [17, True]],
    'threshold': 2,
    'window_s': 100},
   ['fail', 'ban-until-11', 'banned', 'banned', 'fail', 'ok']],
  ['random attempts',
   {'ban_s': 15,
    'events': [[11, True],
               [15, True],
               [29, False],
               [39, False],
               [45, False],
               [45, False],
               [46, False],
               [50, True],
               [54, False],
               [56, False],
               [58, True],
               [60, False],
               [83, False],
               [92, False]],
    'threshold': 3,
    'window_s': 20},
   ['ok',
    'ok',
    'fail',
    'fail',
    'ban-until-60',
    'banned',
    'banned',
    'banned',
    'banned',
    'banned',
    'banned',
    'fail',
    'fail',
    'fail']]]]
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):
    th = x['threshold']
    Wn = x['window_s']
    base = x['ban_s']
    fails = []
    until = None
    strikes = 0
    out = []
    for t, ok in x['events']:
        if until is not None and t - until < base:
            out.append('banned')
            continue
        if ok:
            out.append('ok')
            continue
        fails = [f for f in fails if f > t - Wn] + [t]
        if len(fails) >= th:
            until = t + base * 2 ** strikes
            strikes += 1
            fails = []
            out.append('ban-until-%d' % until)
        else:
            out.append('fail')
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['ban and escalate',
   {'ban_s': 10,
    'events': [[0, False],
               [1, False],
               [2, False],
               [5, False],
               [12, False],
               [13, False],
               [14, False],
               [31, False],
               [40, True]],
    'threshold': 3,
    'window_s': 60},
   ['fail', 'fail', 'ban-until-12', 'banned', 'fail', 'fail', 'ban-until-34', 'banned', 'ok']],
  ['third ban escalates',
   {'ban_s': 10,
    'events': [[0, False], [10, False], [30, False], [65, True], [71, True]],
    'threshold': 1,
    'window_s': 5},
   ['ban-until-10', 'ban-until-30', 'ban-until-70', 'banned', 'ok']],
  ['ban end instant',
   {'ban_s': 20,
    'events': [[0, False], [1, False], [20, True], [21, True], [23, False]],
    'threshold': 2,
    'window_s': 30},
   ['fail', 'ban-until-21', 'banned', 'ok', 'fail']],
  ['window prune boundary',
   {'ban_s': 5,
    'events': [[0, False], [10, False], [12, False], [30, False]],
    'threshold': 2,
    'window_s': 10},
   ['fail', 'fail', 'ban-until-17', 'fail']],
  ['failures cleared by ban',
   {'ban_s': 5,
    'events': [[0, False], [1, False], [2, False], [7, False], [9, False], [10, True]],
    'threshold': 3,
    'window_s': 100},
   ['fail', 'fail', 'ban-until-7', 'fail', 'fail', 'ok']],
  ['banned failures ignored',
   {'ban_s': 10,
    'events': [[0, False], [1, False], [5, False], [6, False], [11, False], [13, True]],
    'threshold': 2,
    'window_s': 100},
   ['fail', 'ban-until-11', 'banned', 'banned', 'fail', 'ok']],
  ['random attempts',
   {'ban_s': 15,
    'events': [[10, False],
               [13, False],
               [16, False],
               [20, False],
               [52, False],
               [53, False],
               [57, False],
               [74, False],
               [80, False],
               [87, False],
               [106, False],
               [115, True],
               [116, False],
               [119, True]],
    'threshold': 3,
    'window_s': 20},
   ['fail',
    'fail',
    'ban-until-31',
    'banned',
    'fail',
    'fail',
    'ban-until-87',
    'banned',
    'banned',
    'fail',
    'fail',
    'ok',
    'fail',
    'ok']]],
 [['ban and escalate',
   {'ban_s': 10,
    'events': [[0, False],
               [1, False],
               [2, False],
               [5, False],
               [12, False],
               [13, False],
               [14, False],
               [32, False],
               [40, True]],
    'threshold': 3,
    'window_s': 60},
   ['fail', 'fail', 'ban-until-12', 'banned', 'fail', 'fail', 'ban-until-34', 'banned', 'ok']],
  ['third ban escalates',
   {'ban_s': 10,
    'events': [[0, False], [10, False], [30, False], [65, True], [72, True]],
    'threshold': 1,
    'window_s': 5},
   ['ban-until-10', 'ban-until-30', 'ban-until-70', 'banned', 'ok']],
  ['ban end instant',
   {'ban_s': 20,
    'events': [[0, False], [1, False], [20, True], [21, True], [24, False]],
    'threshold': 2,
    'window_s': 30},
   ['fail', 'ban-until-21', 'banned', 'ok', 'fail']],
  ['window prune boundary',
   {'ban_s': 5,
    'events': [[0, False], [10, False], [13, False], [30, False]],
    'threshold': 2,
    'window_s': 10},
   ['fail', 'fail', 'ban-until-18', 'fail']],
  ['failures cleared by ban',
   {'ban_s': 5,
    'events': [[0, False], [1, False], [2, False], [7, False], [10, False], [11, True]],
    'threshold': 3,
    'window_s': 100},
   ['fail', 'fail', 'ban-until-7', 'fail', 'fail', 'ok']],
  ['banned failures ignored',
   {'ban_s': 10,
    'events': [[0, False], [1, False], [5, False], [6, False], [11, False], [14, True]],
    'threshold': 2,
    'window_s': 100},
   ['fail', 'ban-until-11', 'banned', 'banned', 'fail', 'ok']],
  ['random attempts',
   {'ban_s': 15,
    'events': [[0, False],
               [23, False],
               [25, True],
               [34, False],
               [35, False],
               [49, False],
               [49, True],
               [60, False],
               [71, False],
               [83, False],
               [87, False],
               [87, False],
               [89, False],
               [117, False]],
    'threshold': 3,
    'window_s': 20},
   ['fail',
    'fail',
    'ok',
    'fail',
    'ban-until-50',
    'banned',
    'banned',
    'fail',
    'fail',
    'fail',
    'ban-until-117',
    'banned',
    'banned',
    'fail']]],
 [['ban and escalate',
   {'ban_s': 10,
    'events': [[0, False],
               [1, False],
               [2, False],
               [5, False],
               [12, False],
               [13, False],
               [14, False],
               [33, False],
               [40, True]],
    'threshold': 3,
    'window_s': 60},
   ['fail', 'fail', 'ban-until-12', 'banned', 'fail', 'fail', 'ban-until-34', 'banned', 'ok']],
  ['third ban escalates',
   {'ban_s': 10,
    'events': [[0, False], [10, False], [30, False], [65, True], [73, True]],
    'threshold': 1,
    'window_s': 5},
   ['ban-until-10', 'ban-until-30', 'ban-until-70', 'banned', 'ok']],
  ['ban end instant',
   {'ban_s': 20,
    'events': [[0, False], [1, False], [20, True], [21, True], [25, False]],
    'threshold': 2,
    'window_s': 30},
   ['fail', 'ban-until-21', 'banned', 'ok', 'fail']],
  ['window prune boundary',
   {'ban_s': 5,
    'events': [[0, False], [10, False], [14, False], [30, False]],
    'threshold': 2,
    'window_s': 10},
   ['fail', 'fail', 'ban-until-19', 'fail']],
  ['failures cleared by ban',
   {'ban_s': 5,
    'events': [[0, False], [1, False], [2, False], [7, False], [11, False], [12, True]],
    'threshold': 3,
    'window_s': 100},
   ['fail', 'fail', 'ban-until-7', 'fail', 'fail', 'ok']],
  ['banned failures ignored',
   {'ban_s': 10,
    'events': [[0, False], [1, False], [5, False], [6, False], [11, False], [15, True]],
    'threshold': 2,
    'window_s': 100},
   ['fail', 'ban-until-11', 'banned', 'banned', 'fail', 'ok']],
  ['random attempts',
   {'ban_s': 15,
    'events': [[8, False],
               [30, False],
               [30, False],
               [39, True],
               [44, False],
               [45, True],
               [47, False],
               [58, True],
               [78, False],
               [78, False],
               [82, False],
               [90, False],
               [107, False],
               [119, False]],
    'threshold': 3,
    'window_s': 20},
   ['fail',
    'fail',
    'fail',
    'ok',
    'ban-until-59',
    'banned',
    'banned',
    'banned',
    'fail',
    'fail',
    'ban-until-112',
    'banned',
    'banned',
    'fail']]],
 [['ban and escalate',
   {'ban_s': 10,
    'events': [[0, False],
               [1, False],
               [2, False],
               [5, False],
               [12, False],
               [13, False],
               [14, False],
               [34, False],
               [40, True]],
    'threshold': 3,
    'window_s': 60},
   ['fail', 'fail', 'ban-until-12', 'banned', 'fail', 'fail', 'ban-until-34', 'fail', 'ok']],
  ['third ban escalates',
   {'ban_s': 10,
    'events': [[0, False], [10, False], [30, False], [65, True], [74, True]],
    'threshold': 1,
    'window_s': 5},
   ['ban-until-10', 'ban-until-30', 'ban-until-70', 'banned', 'ok']],
  ['ban end instant',
   {'ban_s': 20,
    'events': [[0, False], [1, False], [20, True], [21, True], [26, False]],
    'threshold': 2,
    'window_s': 30},
   ['fail', 'ban-until-21', 'banned', 'ok', 'fail']],
  ['window prune boundary',
   {'ban_s': 5,
    'events': [[0, False], [10, False], [15, False], [30, False]],
    'threshold': 2,
    'window_s': 10},
   ['fail', 'fail', 'ban-until-20', 'fail']],
  ['failures cleared by ban',
   {'ban_s': 5,
    'events': [[0, False], [1, False], [2, False], [7, False], [12, False], [13, True]],
    'threshold': 3,
    'window_s': 100},
   ['fail', 'fail', 'ban-until-7', 'fail', 'fail', 'ok']],
  ['banned failures ignored',
   {'ban_s': 10,
    'events': [[0, False], [1, False], [5, False], [6, False], [11, False], [16, True]],
    'threshold': 2,
    'window_s': 100},
   ['fail', 'ban-until-11', 'banned', 'banned', 'fail', 'ok']],
  ['random attempts',
   {'ban_s': 15,
    'events': [[6, False],
               [17, False],
               [25, False],
               [51, False],
               [52, True],
               [68, True],
               [78, True],
               [79, False],
               [86, True],
               [90, False],
               [92, True],
               [96, False],
               [100, False],
               [110, False]],
    'threshold': 3,
    'window_s': 20},
   ['fail',
    'fail',
    'ban-until-40',
    'fail',
    'ok',
    'ok',
    'ok',
    'fail',
    'ok',
    'fail',
    'ok',
    'ban-until-126',
    'banned',
    'banned']]],
 [['ban and escalate',
   {'ban_s': 10,
    'events': [[0, False],
               [1, False],
               [2, False],
               [5, False],
               [12, False],
               [13, False],
               [14, False],
               [35, False],
               [40, True]],
    'threshold': 3,
    'window_s': 60},
   ['fail', 'fail', 'ban-until-12', 'banned', 'fail', 'fail', 'ban-until-34', 'fail', 'ok']],
  ['third ban escalates',
   {'ban_s': 10,
    'events': [[0, False], [10, False], [30, False], [65, True], [75, True]],
    'threshold': 1,
    'window_s': 5},
   ['ban-until-10', 'ban-until-30', 'ban-until-70', 'banned', 'ok']],
  ['ban end instant',
   {'ban_s': 20,
    'events': [[0, False], [1, False], [20, True], [21, True], [27, False]],
    'threshold': 2,
    'window_s': 30},
   ['fail', 'ban-until-21', 'banned', 'ok', 'fail']],
  ['window prune boundary',
   {'ban_s': 5,
    'events': [[0, False], [10, False], [16, False], [30, False]],
    'threshold': 2,
    'window_s': 10},
   ['fail', 'fail', 'ban-until-21', 'fail']],
  ['failures cleared by ban',
   {'ban_s': 5,
    'events': [[0, False], [1, False], [2, False], [7, False], [13, False], [14, True]],
    'threshold': 3,
    'window_s': 100},
   ['fail', 'fail', 'ban-until-7', 'fail', 'fail', 'ok']],
  ['banned failures ignored',
   {'ban_s': 10,
    'events': [[0, False], [1, False], [5, False], [6, False], [11, False], [17, True]],
    'threshold': 2,
    'window_s': 100},
   ['fail', 'ban-until-11', 'banned', 'banned', 'fail', 'ok']],
  ['random attempts',
   {'ban_s': 15,
    'events': [[11, True],
               [15, True],
               [29, False],
               [39, False],
               [45, False],
               [45, False],
               [46, False],
               [50, True],
               [54, False],
               [56, False],
               [58, True],
               [60, False],
               [83, False],
               [92, False]],
    'threshold': 3,
    'window_s': 20},
   ['ok',
    'ok',
    'fail',
    'fail',
    'ban-until-60',
    'banned',
    'banned',
    'banned',
    'banned',
    'banned',
    'banned',
    'fail',
    'fail',
    'fail']]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
A client retrying exactly when told the ban ends is still refused.

Input {threshold, window_s, ban_s, events [[t, ok]]} with nondecreasing t. While t < ban end every event is "banned" and ignored. Failures are kept for window_s seconds (f > t - window_s). When the kept failures reach threshold the key is banned until t + ban_s * 2^strikes, strikes increments and the failure log is cleared; the event reports "ban-until-<end>". Otherwise failures report "fail" and successes "ok". Return the per-event results.

split: open-access