FA-73831 / Rate limiter algorithms / Open access
Max-min fair split of a global rate limit: indivisible remainder discarded · case 01
A few units of capacity are left unused even though clients still want them.
ROOT CAUSE
The final units smaller than one per client are not handed out.
VERIFIED REPAIR
Give the remainder one unit each to active clients in ascending id order.
Unsuccessful approach: Handing the remainder to the highest ids contradicts the tie-break.
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[:0]:
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', 3], ['z', 3]], 0] | [[['x', 0], ['y', 4], ['z', 3]], 0] | Failed |
| surplus left over | [[['a', 3], ['b', 5]], 12] | [[['a', 3], ['b', 5]], 12] | Passed |
| multi-round water filling | [[['a', 1], ['b', 3], ['c', 6], ['d', 6]], 0] | [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0] | Failed |
| 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', 0], ['c', 0]], 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 / 1568993391f6941533b9b9556ab03b24a68c08c08d11a3b5c3b8f8fb14cc2864
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)
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', 3], ['z', 4]], 0] | [[['x', 0], ['y', 4], ['z', 3]], 0] | Failed |
| surplus left over | [[['a', 3], ['b', 5]], 12] | [[['a', 3], ['b', 5]], 12] | Passed |
| multi-round water filling | [[['a', 1], ['b', 3], ['c', 6], ['d', 7]], 0] | [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0] | Failed |
| 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 / 068b5a30bc511ad000a992877bab496bd48d8bd4b8e80e0d5ae5e8ed486c79e1
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.216217+00:00.
Case digest / d123a5b7037e9ed8c972a1d9cc4b74fc62b01d3cc89a4c85cea95ceb30379de1