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

N = 1
observations = []
def solve(x):
    maxk = x['max_keys']
    cap = x['capacity']
    rate = x['rate']
    table = {}
    order = []
    out = []
    for t, key in x['requests']:
        if key not in table:
            if len(table) >= maxk:
                idle = list(order)
                if not idle:
                    out.append('overflow')
                    continue
                del table[idle[0]]
                order.remove(idle[0])
            table[key] = [cap, t]
        else:
            order.remove(key)
        order.append(key)
        st = table[key]
        st[0] = min(cap, st[0] + (t - st[1]) * rate)
        st[1] = t
        if st[0] >= 1:
            st[0] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, order]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[2, 'a'],
                 [3, 'a'],
                 [4, 'a'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'c'],
                 [9, 'a'],
                 [9, 'd'],
                 [10, 'a'],
                 [10, 'c'],
                 [10, 'c'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow'],
    ['a', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'b'],
                 [1, 'd'],
                 [2, 'a'],
                 [3, 'c'],
                 [3, 'd'],
                 [4, 'a'],
                 [5, 'b'],
                 [5, 'b'],
                 [8, 'a'],
                 [9, 'b'],
                 [9, 'd'],
                 [10, 'c']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[1, 'a'],
                 [4, 'c'],
                 [5, 'a'],
                 [5, 'c'],
                 [6, 'c'],
                 [7, 'b'],
                 [7, 'b'],
                 [7, 'c'],
                 [7, 'd'],
                 [7, 'd'],
                 [9, 'b'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow',
     'overflow',
     'allow',
     'allow'],
    ['b', 'd']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'c'],
                 [2, 'a'],
                 [3, 'd'],
                 [5, 'b'],
                 [6, 'b'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'a'],
                 [7, 'd'],
                 [8, 'c'],
                 [9, 'd'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'],
                 [1, 'a'],
                 [1, 'c'],
                 [2, 'd'],
                 [3, 'c'],
                 [4, 'd'],
                 [6, 'a'],
                 [8, 'b'],
                 [8, 'd'],
                 [9, 'b'],
                 [10, 'b'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]]]
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):
    maxk = x['max_keys']
    cap = x['capacity']
    rate = x['rate']
    table = {}
    order = []
    out = []
    for t, key in x['requests']:
        if key not in table:
            if len(table) >= maxk:
                idle = [k for k in order if table[k][0] >= cap]
                if not idle:
                    out.append('overflow')
                    continue
                del table[idle[0]]
                order.remove(idle[0])
            table[key] = [cap, t]
        else:
            order.remove(key)
        order.append(key)
        st = table[key]
        st[0] = min(cap, st[0] + (t - st[1]) * rate)
        st[1] = t
        if st[0] >= 1:
            st[0] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, order]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[2, 'a'],
                 [3, 'a'],
                 [4, 'a'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'c'],
                 [9, 'a'],
                 [9, 'd'],
                 [10, 'a'],
                 [10, 'c'],
                 [10, 'c'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow'],
    ['a', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'b'],
                 [1, 'd'],
                 [2, 'a'],
                 [3, 'c'],
                 [3, 'd'],
                 [4, 'a'],
                 [5, 'b'],
                 [5, 'b'],
                 [8, 'a'],
                 [9, 'b'],
                 [9, 'd'],
                 [10, 'c']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[1, 'a'],
                 [4, 'c'],
                 [5, 'a'],
                 [5, 'c'],
                 [6, 'c'],
                 [7, 'b'],
                 [7, 'b'],
                 [7, 'c'],
                 [7, 'd'],
                 [7, 'd'],
                 [9, 'b'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow',
     'overflow',
     'allow',
     'allow'],
    ['b', 'd']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'c'],
                 [2, 'a'],
                 [3, 'd'],
                 [5, 'b'],
                 [6, 'b'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'a'],
                 [7, 'd'],
                 [8, 'c'],
                 [9, 'd'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'],
                 [1, 'a'],
                 [1, 'c'],
                 [2, 'd'],
                 [3, 'c'],
                 [4, 'd'],
                 [6, 'a'],
                 [8, 'b'],
                 [8, 'd'],
                 [9, 'b'],
                 [10, 'b'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]]]
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:
An attacker cycles through new keys to evict its own throttled entry and receive a full bucket.

Input {max_keys, capacity, rate, requests [[t_s, key]]} with nondecreasing whole seconds. Each key has a token bucket (starts full, cost 1). The table holds at most max_keys keys; a new key may only evict the least recently used key whose bucket would be full after refill at the current time (so eviction cannot reset anyone's limit); if no key is idle the request is "overflow" and nothing changes. Every admitted or denied request refreshes the key's recency. Return [results, keys in LRU order].

split: open-access


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

N = 1
observations = []
def solve(x):
    maxk = x['max_keys']
    cap = x['capacity']
    rate = x['rate']
    table = {}
    order = []
    out = []
    for t, key in x['requests']:
        if key not in table:
            if len(table) >= maxk:
                idle = [k for k in order if min(cap, table[k][0] + (t - table[k][1]) * rate) >= cap]
                if not idle:
                    out.append('overflow')
                    continue
                del table[idle[0]]
                order.remove(idle[0])
            table[key] = [cap, t]
        if key not in order:
            order.append(key)
        st = table[key]
        st[0] = min(cap, st[0] + (t - st[1]) * rate)
        st[1] = t
        if st[0] >= 1:
            st[0] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, order]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[2, 'a'],
                 [3, 'a'],
                 [4, 'a'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'c'],
                 [9, 'a'],
                 [9, 'd'],
                 [10, 'a'],
                 [10, 'c'],
                 [10, 'c'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow'],
    ['a', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'b'],
                 [1, 'd'],
                 [2, 'a'],
                 [3, 'c'],
                 [3, 'd'],
                 [4, 'a'],
                 [5, 'b'],
                 [5, 'b'],
                 [8, 'a'],
                 [9, 'b'],
                 [9, 'd'],
                 [10, 'c']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[1, 'a'],
                 [4, 'c'],
                 [5, 'a'],
                 [5, 'c'],
                 [6, 'c'],
                 [7, 'b'],
                 [7, 'b'],
                 [7, 'c'],
                 [7, 'd'],
                 [7, 'd'],
                 [9, 'b'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow',
     'overflow',
     'allow',
     'allow'],
    ['b', 'd']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'c'],
                 [2, 'a'],
                 [3, 'd'],
                 [5, 'b'],
                 [6, 'b'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'a'],
                 [7, 'd'],
                 [8, 'c'],
                 [9, 'd'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'],
                 [1, 'a'],
                 [1, 'c'],
                 [2, 'd'],
                 [3, 'c'],
                 [4, 'd'],
                 [6, 'a'],
                 [8, 'b'],
                 [8, 'd'],
                 [9, 'b'],
                 [10, 'b'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]]]
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):
    maxk = x['max_keys']
    cap = x['capacity']
    rate = x['rate']
    table = {}
    order = []
    out = []
    for t, key in x['requests']:
        if key not in table:
            if len(table) >= maxk:
                idle = [k for k in order if min(cap, table[k][0] + (t - table[k][1]) * rate) >= cap]
                if not idle:
                    out.append('overflow')
                    continue
                del table[idle[0]]
                order.remove(idle[0])
            table[key] = [cap, t]
        else:
            order.remove(key)
            order.insert(0, key)
        if key not in order:
            order.append(key)
        st = table[key]
        st[0] = min(cap, st[0] + (t - st[1]) * rate)
        st[1] = t
        if st[0] >= 1:
            st[0] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, order]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[2, 'a'],
                 [3, 'a'],
                 [4, 'a'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'c'],
                 [9, 'a'],
                 [9, 'd'],
                 [10, 'a'],
                 [10, 'c'],
                 [10, 'c'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow'],
    ['a', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'b'],
                 [1, 'd'],
                 [2, 'a'],
                 [3, 'c'],
                 [3, 'd'],
                 [4, 'a'],
                 [5, 'b'],
                 [5, 'b'],
                 [8, 'a'],
                 [9, 'b'],
                 [9, 'd'],
                 [10, 'c']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[1, 'a'],
                 [4, 'c'],
                 [5, 'a'],
                 [5, 'c'],
                 [6, 'c'],
                 [7, 'b'],
                 [7, 'b'],
                 [7, 'c'],
                 [7, 'd'],
                 [7, 'd'],
                 [9, 'b'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow',
     'overflow',
     'allow',
     'allow'],
    ['b', 'd']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'c'],
                 [2, 'a'],
                 [3, 'd'],
                 [5, 'b'],
                 [6, 'b'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'a'],
                 [7, 'd'],
                 [8, 'c'],
                 [9, 'd'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'],
                 [1, 'a'],
                 [1, 'c'],
                 [2, 'd'],
                 [3, 'c'],
                 [4, 'd'],
                 [6, 'a'],
                 [8, 'b'],
                 [8, 'd'],
                 [9, 'b'],
                 [10, 'b'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]]]
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 frequently used key is evicted as if it were stale.

Input {max_keys, capacity, rate, requests [[t_s, key]]} with nondecreasing whole seconds. Each key has a token bucket (starts full, cost 1). The table holds at most max_keys keys; a new key may only evict the least recently used key whose bucket would be full after refill at the current time (so eviction cannot reset anyone's limit); if no key is idle the request is "overflow" and nothing changes. Every admitted or denied request refreshes the key's recency. Return [results, keys in LRU order].

split: open-access


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

N = 1
observations = []
def solve(x):
    maxk = x['max_keys']
    cap = x['capacity']
    rate = x['rate']
    table = {}
    order = []
    out = []
    for t, key in x['requests']:
        if key not in table:
            if len(table) >= maxk:
                idle = [k for k in order if min(cap, table[k][0] + (t - table[k][1]) * rate) >= cap]
                if not idle:
                    out.append('overflow')
                    continue
                del table[idle[0]]
                order.remove(idle[0])
            table[key] = [0, t]
        else:
            order.remove(key)
        order.append(key)
        st = table[key]
        st[0] = min(cap, st[0] + (t - st[1]) * rate)
        st[1] = t
        if st[0] >= 1:
            st[0] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, order]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[2, 'a'],
                 [3, 'a'],
                 [4, 'a'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'c'],
                 [9, 'a'],
                 [9, 'd'],
                 [10, 'a'],
                 [10, 'c'],
                 [10, 'c'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow'],
    ['a', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'b'],
                 [1, 'd'],
                 [2, 'a'],
                 [3, 'c'],
                 [3, 'd'],
                 [4, 'a'],
                 [5, 'b'],
                 [5, 'b'],
                 [8, 'a'],
                 [9, 'b'],
                 [9, 'd'],
                 [10, 'c']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[1, 'a'],
                 [4, 'c'],
                 [5, 'a'],
                 [5, 'c'],
                 [6, 'c'],
                 [7, 'b'],
                 [7, 'b'],
                 [7, 'c'],
                 [7, 'd'],
                 [7, 'd'],
                 [9, 'b'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow',
     'overflow',
     'allow',
     'allow'],
    ['b', 'd']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'c'],
                 [2, 'a'],
                 [3, 'd'],
                 [5, 'b'],
                 [6, 'b'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'a'],
                 [7, 'd'],
                 [8, 'c'],
                 [9, 'd'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'],
                 [1, 'a'],
                 [1, 'c'],
                 [2, 'd'],
                 [3, 'c'],
                 [4, 'd'],
                 [6, 'a'],
                 [8, 'b'],
                 [8, 'd'],
                 [9, 'b'],
                 [10, 'b'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]]]
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):
    maxk = x['max_keys']
    cap = x['capacity']
    rate = x['rate']
    table = {}
    order = []
    out = []
    for t, key in x['requests']:
        if key not in table:
            if len(table) >= maxk:
                idle = [k for k in order if min(cap, table[k][0] + (t - table[k][1]) * rate) >= cap]
                if not idle:
                    out.append('overflow')
                    continue
                del table[idle[0]]
                order.remove(idle[0])
            table[key] = [1, t]
        else:
            order.remove(key)
        order.append(key)
        st = table[key]
        st[0] = min(cap, st[0] + (t - st[1]) * rate)
        st[1] = t
        if st[0] >= 1:
            st[0] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, order]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[2, 'a'],
                 [3, 'a'],
                 [4, 'a'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'c'],
                 [9, 'a'],
                 [9, 'd'],
                 [10, 'a'],
                 [10, 'c'],
                 [10, 'c'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow'],
    ['a', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'b'],
                 [1, 'd'],
                 [2, 'a'],
                 [3, 'c'],
                 [3, 'd'],
                 [4, 'a'],
                 [5, 'b'],
                 [5, 'b'],
                 [8, 'a'],
                 [9, 'b'],
                 [9, 'd'],
                 [10, 'c']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[1, 'a'],
                 [4, 'c'],
                 [5, 'a'],
                 [5, 'c'],
                 [6, 'c'],
                 [7, 'b'],
                 [7, 'b'],
                 [7, 'c'],
                 [7, 'd'],
                 [7, 'd'],
                 [9, 'b'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow',
     'overflow',
     'allow',
     'allow'],
    ['b', 'd']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'c'],
                 [2, 'a'],
                 [3, 'd'],
                 [5, 'b'],
                 [6, 'b'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'a'],
                 [7, 'd'],
                 [8, 'c'],
                 [9, 'd'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'],
                 [1, 'a'],
                 [1, 'c'],
                 [2, 'd'],
                 [3, 'c'],
                 [4, 'd'],
                 [6, 'a'],
                 [8, 'b'],
                 [8, 'd'],
                 [9, 'b'],
                 [10, 'b'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]]]
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 new client is denied its first request.

Input {max_keys, capacity, rate, requests [[t_s, key]]} with nondecreasing whole seconds. Each key has a token bucket (starts full, cost 1). The table holds at most max_keys keys; a new key may only evict the least recently used key whose bucket would be full after refill at the current time (so eviction cannot reset anyone's limit); if no key is idle the request is "overflow" and nothing changes. Every admitted or denied request refreshes the key's recency. Return [results, keys in LRU order].

split: open-access


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

N = 1
observations = []
def solve(x):
    maxk = x['max_keys']
    cap = x['capacity']
    rate = x['rate']
    table = {}
    order = []
    out = []
    for t, key in x['requests']:
        if key not in table:
            if len(table) >= maxk:
                idle = [k for k in order if min(cap, table[k][0] + (t - table[k][1]) * rate) > 0]
                if not idle:
                    out.append('overflow')
                    continue
                del table[idle[0]]
                order.remove(idle[0])
            table[key] = [cap, t]
        else:
            order.remove(key)
        order.append(key)
        st = table[key]
        st[0] = min(cap, st[0] + (t - st[1]) * rate)
        st[1] = t
        if st[0] >= 1:
            st[0] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, order]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[2, 'a'],
                 [3, 'a'],
                 [4, 'a'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'c'],
                 [9, 'a'],
                 [9, 'd'],
                 [10, 'a'],
                 [10, 'c'],
                 [10, 'c'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow'],
    ['a', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'b'],
                 [1, 'd'],
                 [2, 'a'],
                 [3, 'c'],
                 [3, 'd'],
                 [4, 'a'],
                 [5, 'b'],
                 [5, 'b'],
                 [8, 'a'],
                 [9, 'b'],
                 [9, 'd'],
                 [10, 'c']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[1, 'a'],
                 [4, 'c'],
                 [5, 'a'],
                 [5, 'c'],
                 [6, 'c'],
                 [7, 'b'],
                 [7, 'b'],
                 [7, 'c'],
                 [7, 'd'],
                 [7, 'd'],
                 [9, 'b'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow',
     'overflow',
     'allow',
     'allow'],
    ['b', 'd']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'c'],
                 [2, 'a'],
                 [3, 'd'],
                 [5, 'b'],
                 [6, 'b'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'a'],
                 [7, 'd'],
                 [8, 'c'],
                 [9, 'd'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'],
                 [1, 'a'],
                 [1, 'c'],
                 [2, 'd'],
                 [3, 'c'],
                 [4, 'd'],
                 [6, 'a'],
                 [8, 'b'],
                 [8, 'd'],
                 [9, 'b'],
                 [10, 'b'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]]]
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):
    maxk = x['max_keys']
    cap = x['capacity']
    rate = x['rate']
    table = {}
    order = []
    out = []
    for t, key in x['requests']:
        if key not in table:
            if len(table) >= maxk:
                idle = [k for k in order if min(cap, table[k][0] + (t - table[k][1]) * rate) >= cap - 1]
                if not idle:
                    out.append('overflow')
                    continue
                del table[idle[0]]
                order.remove(idle[0])
            table[key] = [cap, t]
        else:
            order.remove(key)
        order.append(key)
        st = table[key]
        st[0] = min(cap, st[0] + (t - st[1]) * rate)
        st[1] = t
        if st[0] >= 1:
            st[0] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, order]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [4, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [10, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [3, 'b'], [4, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [4, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[2, 'a'],
                 [3, 'a'],
                 [4, 'a'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'c'],
                 [9, 'a'],
                 [9, 'd'],
                 [10, 'a'],
                 [10, 'c'],
                 [10, 'c'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow'],
    ['a', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [5, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [11, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [4, 'b'], [5, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [5, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'b'],
                 [1, 'd'],
                 [2, 'a'],
                 [3, 'c'],
                 [3, 'd'],
                 [4, 'a'],
                 [5, 'b'],
                 [5, 'b'],
                 [8, 'a'],
                 [9, 'b'],
                 [9, 'd'],
                 [10, 'c']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'c']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [6, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [12, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [5, 'b'], [6, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [9, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [6, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[1, 'a'],
                 [4, 'c'],
                 [5, 'a'],
                 [5, 'c'],
                 [6, 'c'],
                 [7, 'b'],
                 [7, 'b'],
                 [7, 'c'],
                 [7, 'd'],
                 [7, 'd'],
                 [9, 'b'],
                 [10, 'd']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'overflow',
     'overflow',
     'allow',
     'allow'],
    ['b', 'd']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [7, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [13, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [6, 'b'], [7, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [10, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [7, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'c'],
                 [2, 'a'],
                 [3, 'd'],
                 [5, 'b'],
                 [6, 'b'],
                 [6, 'd'],
                 [7, 'a'],
                 [7, 'a'],
                 [7, 'd'],
                 [8, 'c'],
                 [9, 'd'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]],
 [['busy key not evicted',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'b'], [1, 'c'], [8, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['a', 'c']]],
  ['lru order refreshed',
   {'capacity': 1,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [1, 'b'], [5, 'a'], [9, 'c'], [14, 'b']]},
   [['allow', 'allow', 'allow', 'allow', 'allow'], ['c', 'b']]],
  ['refilled key is idle',
   {'capacity': 3,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [1, 'b'], [7, 'b'], [8, 'a']]},
   [['allow', 'allow', 'overflow', 'allow', 'allow'], ['a']]],
  ['new key starts full',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [5, 'b'], [6, 'c'], [6, 'c'], [11, 'c']]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], ['b', 'c']]],
  ['partially refilled not idle',
   {'capacity': 4,
    'max_keys': 1,
    'rate': 1,
    'requests': [[0, 'a'], [0, 'a'], [0, 'a'], [2, 'b'], [8, 'b']]},
   [['allow', 'allow', 'allow', 'overflow', 'allow'], ['b']]],
  ['random keys',
   {'capacity': 2,
    'max_keys': 2,
    'rate': 1,
    'requests': [[0, 'a'],
                 [1, 'a'],
                 [1, 'c'],
                 [2, 'd'],
                 [3, 'c'],
                 [4, 'd'],
                 [6, 'a'],
                 [8, 'b'],
                 [8, 'd'],
                 [9, 'b'],
                 [10, 'b'],
                 [10, 'b']]},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow'],
    ['d', 'b']]]]]
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 partially throttled key is evicted and its restrictions are forgotten.

Input {max_keys, capacity, rate, requests [[t_s, key]]} with nondecreasing whole seconds. Each key has a token bucket (starts full, cost 1). The table holds at most max_keys keys; a new key may only evict the least recently used key whose bucket would be full after refill at the current time (so eviction cannot reset anyone's limit); if no key is idle the request is "overflow" and nothing changes. Every admitted or denied request refreshes the key's recency. Return [results, keys in LRU order].

split: open-access


prompt:
The estimate barely reacts to new arrivals and throttling kicks in minutes late.

Input {tau_ms, limit_rps, requests [t_ms]}. The rate estimate r starts at 0. For each arrival strictly after the latest seen time, dt = t - last, a = exp(-dt/tau) and r = a*r + (1-a)*(1000/dt) requests per second. Simultaneous or late arrivals leave r unchanged and never move the clock backwards. Every arrival reports deny if r > limit else allow, with r rounded to 3 decimals.

split: open-access


prompt:
Estimates are a thousand times too small and nothing is ever throttled.

Input {tau_ms, limit_rps, requests [t_ms]}. The rate estimate r starts at 0. For each arrival strictly after the latest seen time, dt = t - last, a = exp(-dt/tau) and r = a*r + (1-a)*(1000/dt) requests per second. Simultaneous or late arrivals leave r unchanged and never move the clock backwards. Every arrival reports deny if r > limit else allow, with r rounded to 3 decimals.

split: open-access


prompt:
Two requests with the same timestamp spike the estimate to 1000 requests per second.

Input {tau_ms, limit_rps, requests [t_ms]}. The rate estimate r starts at 0. For each arrival strictly after the latest seen time, dt = t - last, a = exp(-dt/tau) and r = a*r + (1-a)*(1000/dt) requests per second. Simultaneous or late arrivals leave r unchanged and never move the clock backwards. Every arrival reports deny if r > limit else allow, with r rounded to 3 decimals.

split: open-access


prompt:
Long gaps keep the old rate while short gaps discard it, inverting the smoothing.

Input {tau_ms, limit_rps, requests [t_ms]}. The rate estimate r starts at 0. For each arrival strictly after the latest seen time, dt = t - last, a = exp(-dt/tau) and r = a*r + (1-a)*(1000/dt) requests per second. Simultaneous or late arrivals leave r unchanged and never move the clock backwards. Every arrival reports deny if r > limit else allow, with r rounded to 3 decimals.

split: open-access


prompt:
After a late arrival the next interval is measured from the past and appears artificially long or short.

Input {tau_ms, limit_rps, requests [t_ms]}. The rate estimate r starts at 0. For each arrival strictly after the latest seen time, dt = t - last, a = exp(-dt/tau) and r = a*r + (1-a)*(1000/dt) requests per second. Simultaneous or late arrivals leave r unchanged and never move the clock backwards. Every arrival reports deny if r > limit else allow, with r rounded to 3 decimals.

split: open-access