FA-90641 / Garbage collector invariants / Open access
Collection set: liveness ratio truncated to zero · case 01
Nearly full old regions are treated as empty and chosen for evacuation.
ROOT CAUSE
The liveness ratio is computed with integer division before scaling to percent.
VERIFIED REPAIR
Compare live * 100 with pct * used.
Unsuccessful approach: Allowing equality admits regions exactly at the threshold.
Case contract
Regions are [id, kind, used, live]. All young regions are always collected (their live bytes cost live * cost). Old regions whose liveness is strictly below live_pct percent (live * 100 < pct * used) are candidates; humongous regions never are. Candidates are ordered by reclaimable bytes (used - live) descending, ties by id, and added while the accumulated cost stays within budget; selection stops at the first candidate that does not fit. Return the collection set, its cost and reclaimed bytes.
Why this case matters
Region-based collectors meet pause goals by choosing the collection set against a cost budget.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(regions, budget, live_pct, cost):
cset = []
time = 0
for rid, kind, used, live in regions:
if kind == 'young':
cset.append(rid)
time += live * cost
cands = [r for r in regions if r[1] == 'old' and r[3] // r[2] * 100 < live_pct]
cands.sort(key=lambda r: (-(r[2] - r[3]), r[0]))
for rid, kind, used, live in cands:
t = live * cost
if time + t > budget:
break
cset.append(rid)
time += t
reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)
return {'cset': cset, 'time': time, 'reclaimed': reclaimed}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
101,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
101,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
85,
85,
2),
{'cset': [1, 2], 'reclaimed': 160, 'time': 80}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
102,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
102,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
90,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
103,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
103,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
95,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
104,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
104,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
100,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
105,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
105,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
105,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]
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 |
|---|---|---|---|
| regression: candidates fill the budget exactly | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | Passed |
| budget stops at the first region that does not fit | {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65} | {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65} | Passed |
| expensive region first stops selection | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | Passed |
| region at exactly the liveness threshold excluded | {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290} | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | Failed |
| higher threshold admits more regions | {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290} | {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290} | Passed |
| cost multiplier | {'cset': [1, 2], 'reclaimed': 160, 'time': 80} | {'cset': [1, 2], 'reclaimed': 160, 'time': 80} | Passed |
| control: only young regions fit | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | Passed |
SHA-256 / aa89694c75e46710022b497bdb16315e6845c2fd6942385feac5adea9e33409a
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(regions, budget, live_pct, cost):
cset = []
time = 0
for rid, kind, used, live in regions:
if kind == 'young':
cset.append(rid)
time += live * cost
cands = [r for r in regions if r[1] == 'old' and r[3] * 100 // r[2] <= live_pct]
cands.sort(key=lambda r: (-(r[2] - r[3]), r[0]))
for rid, kind, used, live in cands:
t = live * cost
if time + t > budget:
break
cset.append(rid)
time += t
reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)
return {'cset': cset, 'time': time, 'reclaimed': reclaimed}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
101,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
101,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
85,
85,
2),
{'cset': [1, 2], 'reclaimed': 160, 'time': 80}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
102,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
102,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
90,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
103,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
103,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
95,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
104,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
104,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
100,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
105,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
105,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
105,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]
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 |
|---|---|---|---|
| regression: candidates fill the budget exactly | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | Passed |
| budget stops at the first region that does not fit | {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65} | {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65} | Passed |
| expensive region first stops selection | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | Passed |
| region at exactly the liveness threshold excluded | {'cset': [1, 2, 7, 3, 5, 4], 'reclaimed': 400, 'time': 200} | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | Failed |
| higher threshold admits more regions | {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290} | {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290} | Passed |
| cost multiplier | {'cset': [1, 2], 'reclaimed': 160, 'time': 80} | {'cset': [1, 2], 'reclaimed': 160, 'time': 80} | Passed |
| control: only young regions fit | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | Passed |
SHA-256 / c54af1f2737b2f7857d3f2358dfed906d155b76da0e754c31086feb252ab46a4
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(regions, budget, live_pct, cost):
cset = []
time = 0
for rid, kind, used, live in regions:
if kind == 'young':
cset.append(rid)
time += live * cost
cands = [r for r in regions if r[1] == 'old' and r[3] * 100 < live_pct * r[2]]
cands.sort(key=lambda r: (-(r[2] - r[3]), r[0]))
for rid, kind, used, live in cands:
t = live * cost
if time + t > budget:
break
cset.append(rid)
time += t
reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)
return {'cset': cset, 'time': time, 'reclaimed': reclaimed}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
101,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
101,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
85,
85,
2),
{'cset': [1, 2], 'reclaimed': 160, 'time': 80}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
102,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
102,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
90,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
103,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
103,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
95,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
104,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
104,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
100,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
105,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
105,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
105,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]
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 |
|---|---|---|---|
| regression: candidates fill the budget exactly | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | Passed |
| budget stops at the first region that does not fit | {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65} | {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65} | Passed |
| expensive region first stops selection | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | Passed |
| region at exactly the liveness threshold excluded | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | Passed |
| higher threshold admits more regions | {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290} | {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290} | Passed |
| cost multiplier | {'cset': [1, 2], 'reclaimed': 160, 'time': 80} | {'cset': [1, 2], 'reclaimed': 160, 'time': 80} | Passed |
| control: only young regions fit | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | Passed |
SHA-256 / 2324d77e6602475e201cd5306025558e86bafedc7295b36cd173443e854b15ac
Verification & scope
A deterministic, bounded teaching model of one garbage-collector mechanism with stipulated rules; it is not a production collector and claims no conformance to any particular runtime. 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:51:28.533646+00:00.
Case digest / e08b7950539c161e31bf189159abd9c7df9adbf14f245e23c3706705334bb2f7