FA-73836 / Rate limiter algorithms / Open access
Max-min fair split of a global rate limit: zero-demand clients dilute the first share · case 01
Clients that asked for nothing shrink everyone else's first-round share and can receive remainder units.
ROOT CAUSE
Clients with zero demand are admitted to the active set.
VERIFIED REPAIR
Only clients with positive demand take part.
Unsuccessful approach: Ordering active clients by demand instead of id changes who receives the indivisible remainder.
Case contract
Input {capacity, demands [[client, demand]]} in integer requests per second. Clients with positive demand are active. Repeatedly give each active client min(floor(left / active count), unmet demand) and drop satisfied clients; when the per-client share rounds to zero, hand single units to active clients in ascending id order until capacity is exhausted. Return [sorted [client, allocation]], unallocated capacity].
Why this case matters
Distributed limiters split a global rate among clients or nodes by max-min fairness so light users are fully served and heavy users share the rest.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
C = x['capacity']
need = dict(x['demands'])
alloc = {c: 0 for c in need}
active = sorted(c for c, d in need.items() if d >= 0)
left = C
while active and left > 0:
share = left // len(active)
if share == 0:
for c in active[:left]:
alloc[c] += 1
left = 0
break
nxt = []
for c in active:
give = min(share, need[c] - alloc[c])
alloc[c] += give
left -= give
if alloc[c] < need[c]:
nxt.append(c)
active = nxt
return [sorted([c, a] for c, a in alloc.items()), left]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 12, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 4], ['b', 4], ['c', 4]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 6]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 5]]},
[[['a', 3], ['b', 5]], 12]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 7], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]]},
[[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 101]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 6]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 4]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 6]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]],
[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 13, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 5], ['b', 4], ['c', 4]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 7]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 6]]},
[[['a', 3], ['b', 6]], 11]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 8], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 2], ['q', 4], ['r', 8], ['s', 8], ['t', 4]]},
[[['p', 2], ['q', 4], ['r', 6], ['s', 5], ['t', 4]], 0]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 102]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 7]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 5]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 7]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]],
[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 14, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 5], ['b', 5], ['c', 4]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 8]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 7]]},
[[['a', 3], ['b', 7]], 10]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 9], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 7], ['q', 8], ['r', 2], ['s', 9], ['t', 1]]},
[[['p', 6], ['q', 6], ['r', 2], ['s', 6], ['t', 1]], 0]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 103]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 8]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 6]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 8]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]],
[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 15, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 5], ['b', 5], ['c', 5]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 9]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 8]]},
[[['a', 3], ['b', 8]], 9]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 10], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]]},
[[['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]], 3]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 104]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 9]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 7]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 9]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]],
[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 16, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 6], ['b', 5], ['c', 5]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 10]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 9]]},
[[['a', 3], ['b', 9]], 8]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 11], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]]},
[[['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]], 4]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 105]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 10]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 8]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 10]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| small demand satisfied first | [[['a', 2], ['b', 4], ['c', 4]], 0] | [[['a', 2], ['b', 4], ['c', 4]], 0] | Passed |
| remainder to lowest ids | [[['a', 4], ['b', 4], ['c', 4]], 0] | [[['a', 4], ['b', 4], ['c', 4]], 0] | Passed |
| zero demand ignored | [[['x', 0], ['y', 4], ['z', 3]], 0] | [[['x', 0], ['y', 4], ['z', 3]], 0] | Passed |
| surplus left over | [[['a', 3], ['b', 5]], 12] | [[['a', 3], ['b', 5]], 12] | Passed |
| multi-round water filling | [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0] | [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0] | Passed |
| random demands | [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7] | [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7] | Passed |
| second round respects unmet demand | [[['a', 2], ['b', 7], ['c', 9]], 0] | [[['a', 2], ['b', 7], ['c', 9]], 0] | Passed |
| tiny capacity with idle client | [[['a', 1], ['b', 1], ['c', 0]], 0] | [[['a', 0], ['b', 1], ['c', 1]], 0] | Failed |
| remainder ignores demand size | [[['a', 1], ['b', 1], ['c', 0]], 0] | [[['a', 1], ['b', 1], ['c', 0]], 0] | Passed |
| exact share satisfies | [[['a', 3], ['b', 3], ['c', 3]], 0] | [[['a', 3], ['b', 3], ['c', 3]], 0] | Passed |
SHA-256 / 2c229a5e3901ef8914ed84d6a5d5f1bb210e9bb725788bd1e6c430bfe92afc6b
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
C = x['capacity']
need = dict(x['demands'])
alloc = {c: 0 for c in need}
active = sorted((c for c, d in need.items() if d > 0), key=lambda c: need[c])
left = C
while active and left > 0:
share = left // len(active)
if share == 0:
for c in active[:left]:
alloc[c] += 1
left = 0
break
nxt = []
for c in active:
give = min(share, need[c] - alloc[c])
alloc[c] += give
left -= give
if alloc[c] < need[c]:
nxt.append(c)
active = nxt
return [sorted([c, a] for c, a in alloc.items()), left]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 12, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 4], ['b', 4], ['c', 4]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 6]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 5]]},
[[['a', 3], ['b', 5]], 12]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 7], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]]},
[[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 101]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 6]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 4]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 6]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]],
[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 13, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 5], ['b', 4], ['c', 4]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 7]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 6]]},
[[['a', 3], ['b', 6]], 11]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 8], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 2], ['q', 4], ['r', 8], ['s', 8], ['t', 4]]},
[[['p', 2], ['q', 4], ['r', 6], ['s', 5], ['t', 4]], 0]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 102]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 7]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 5]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 7]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]],
[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 14, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 5], ['b', 5], ['c', 4]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 8]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 7]]},
[[['a', 3], ['b', 7]], 10]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 9], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 7], ['q', 8], ['r', 2], ['s', 9], ['t', 1]]},
[[['p', 6], ['q', 6], ['r', 2], ['s', 6], ['t', 1]], 0]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 103]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 8]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 6]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 8]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]],
[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 15, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 5], ['b', 5], ['c', 5]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 9]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 8]]},
[[['a', 3], ['b', 8]], 9]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 10], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]]},
[[['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]], 3]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 104]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 9]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 7]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 9]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]],
[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 16, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 6], ['b', 5], ['c', 5]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 10]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 9]]},
[[['a', 3], ['b', 9]], 8]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 11], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]]},
[[['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]], 4]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 105]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 10]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 8]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 10]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| small demand satisfied first | [[['a', 2], ['b', 4], ['c', 4]], 0] | [[['a', 2], ['b', 4], ['c', 4]], 0] | Passed |
| remainder to lowest ids | [[['a', 4], ['b', 4], ['c', 4]], 0] | [[['a', 4], ['b', 4], ['c', 4]], 0] | Passed |
| zero demand ignored | [[['x', 0], ['y', 4], ['z', 3]], 0] | [[['x', 0], ['y', 4], ['z', 3]], 0] | Passed |
| surplus left over | [[['a', 3], ['b', 5]], 12] | [[['a', 3], ['b', 5]], 12] | Passed |
| multi-round water filling | [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0] | [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0] | Passed |
| random demands | [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7] | [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7] | Passed |
| second round respects unmet demand | [[['a', 2], ['b', 7], ['c', 9]], 0] | [[['a', 2], ['b', 7], ['c', 9]], 0] | Passed |
| tiny capacity with idle client | [[['a', 0], ['b', 1], ['c', 1]], 0] | [[['a', 0], ['b', 1], ['c', 1]], 0] | Passed |
| remainder ignores demand size | [[['a', 0], ['b', 1], ['c', 1]], 0] | [[['a', 1], ['b', 1], ['c', 0]], 0] | Failed |
| exact share satisfies | [[['a', 3], ['b', 3], ['c', 3]], 0] | [[['a', 3], ['b', 3], ['c', 3]], 0] | Passed |
SHA-256 / f3b1fb73dbe7f85ec73a7de01c3bbf7754981aeb90e9e74ee56c5b0fbfc594c4
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
C = x['capacity']
need = dict(x['demands'])
alloc = {c: 0 for c in need}
active = sorted(c for c, d in need.items() if d > 0)
left = C
while active and left > 0:
share = left // len(active)
if share == 0:
for c in active[:left]:
alloc[c] += 1
left = 0
break
nxt = []
for c in active:
give = min(share, need[c] - alloc[c])
alloc[c] += give
left -= give
if alloc[c] < need[c]:
nxt.append(c)
active = nxt
return [sorted([c, a] for c, a in alloc.items()), left]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 12, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 4], ['b', 4], ['c', 4]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 6]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 5]]},
[[['a', 3], ['b', 5]], 12]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 7], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]]},
[[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 101]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 6]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 4]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 6]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]],
[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 13, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 5], ['b', 4], ['c', 4]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 7]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 6]]},
[[['a', 3], ['b', 6]], 11]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 8], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 2], ['q', 4], ['r', 8], ['s', 8], ['t', 4]]},
[[['p', 2], ['q', 4], ['r', 6], ['s', 5], ['t', 4]], 0]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 102]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 7]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 5]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 7]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]],
[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 14, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 5], ['b', 5], ['c', 4]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 8]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 7]]},
[[['a', 3], ['b', 7]], 10]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 9], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 7], ['q', 8], ['r', 2], ['s', 9], ['t', 1]]},
[[['p', 6], ['q', 6], ['r', 2], ['s', 6], ['t', 1]], 0]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 103]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 8]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 6]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 8]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]],
[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 15, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 5], ['b', 5], ['c', 5]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 9]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 8]]},
[[['a', 3], ['b', 8]], 9]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 10], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]]},
[[['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]], 3]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 104]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 9]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 7]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 9]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]],
[['small demand satisfied first',
{'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
[[['a', 2], ['b', 4], ['c', 4]], 0]],
['remainder to lowest ids',
{'capacity': 16, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
[[['a', 6], ['b', 5], ['c', 5]], 0]],
['zero demand ignored',
{'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 10]]},
[[['x', 0], ['y', 4], ['z', 3]], 0]],
['surplus left over',
{'capacity': 20, 'demands': [['a', 3], ['b', 9]]},
[[['a', 3], ['b', 9]], 8]],
['multi-round water filling',
{'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 11], ['d', 20]]},
[[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
['random demands',
{'capacity': 21, 'demands': [['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]]},
[[['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]], 4]],
['second round respects unmet demand',
{'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 105]]},
[[['a', 2], ['b', 7], ['c', 9]], 0]],
['tiny capacity with idle client',
{'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 10]]},
[[['a', 0], ['b', 1], ['c', 1]], 0]],
['remainder ignores demand size',
{'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 8]]},
[[['a', 1], ['b', 1], ['c', 0]], 0]],
['exact share satisfies',
{'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 10]]},
[[['a', 3], ['b', 3], ['c', 3]], 0]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| small demand satisfied first | [[['a', 2], ['b', 4], ['c', 4]], 0] | [[['a', 2], ['b', 4], ['c', 4]], 0] | Passed |
| remainder to lowest ids | [[['a', 4], ['b', 4], ['c', 4]], 0] | [[['a', 4], ['b', 4], ['c', 4]], 0] | Passed |
| zero demand ignored | [[['x', 0], ['y', 4], ['z', 3]], 0] | [[['x', 0], ['y', 4], ['z', 3]], 0] | Passed |
| surplus left over | [[['a', 3], ['b', 5]], 12] | [[['a', 3], ['b', 5]], 12] | Passed |
| multi-round water filling | [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0] | [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0] | Passed |
| random demands | [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7] | [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7] | Passed |
| second round respects unmet demand | [[['a', 2], ['b', 7], ['c', 9]], 0] | [[['a', 2], ['b', 7], ['c', 9]], 0] | Passed |
| tiny capacity with idle client | [[['a', 0], ['b', 1], ['c', 1]], 0] | [[['a', 0], ['b', 1], ['c', 1]], 0] | Passed |
| remainder ignores demand size | [[['a', 1], ['b', 1], ['c', 0]], 0] | [[['a', 1], ['b', 1], ['c', 0]], 0] | Passed |
| exact share satisfies | [[['a', 3], ['b', 3], ['c', 3]], 0] | [[['a', 3], ['b', 3], ['c', 3]], 0] | Passed |
SHA-256 / 6d1415162cbbad040d68637a47fc608c97f41cb462def47fcb0c5dd7f7b7bd5b
Verification & scope
A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:48:51.257879+00:00.
Case digest / c21a8de06bdcff62c8690a1ea764a3b7890e2a2e3b30fe48cd405e164698f3c7