FAILURE MAP
← Case archive

FA-90661 / Garbage collector invariants / Open access

Collection set: humongous regions chosen for evacuation · case 01

Empty humongous regions are scheduled for copying.

Verified by executionVariant 1 · 7 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Every non-young region is considered a candidate.

VERIFIED REPAIR

Only old regions are candidates.

Unsuccessful approach: Admitting dead humongous regions still puts them in the evacuation set.

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] != 'young' 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 fixtureActualExpectedOutcome
regression: candidates fill the budget exactly{'cset': [1, 2, 6, 7, 3, 5], 'reclaimed': 785, 'time': 115}{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}Failed
budget stops at the first region that does not fit{'cset': [1, 2, 6, 7, 3], 'reclaimed': 735, 'time': 65}{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}Failed
expensive region first stops selection{'cset': [1, 2, 6], 'reclaimed': 560, 'time': 40}{'cset': [1, 2], 'reclaimed': 160, 'time': 40}Failed
region at exactly the liveness threshold excluded{'cset': [1, 2, 6, 7, 3, 5], 'reclaimed': 785, 'time': 115}{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}Failed
higher threshold admits more regions{'cset': [1, 2, 6, 7, 3, 5, 4, 8], 'reclaimed': 810, 'time': 290}{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}Failed
cost multiplier{'cset': [1, 2, 6], 'reclaimed': 560, 'time': 80}{'cset': [1, 2], 'reclaimed': 160, 'time': 80}Failed
control: only young regions fit{'cset': [1, 2], 'reclaimed': 160, 'time': 40}{'cset': [1, 2], 'reclaimed': 160, 'time': 40}Passed

SHA-256 / 1c95693f0367a7bb1be5cf2e8d0de230dd262fefe0bed73697b999938bf39720

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' or (r[1] == 'humongous' and r[3] == 0)) 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 fixtureActualExpectedOutcome
regression: candidates fill the budget exactly{'cset': [1, 2, 6, 7, 3, 5], 'reclaimed': 785, 'time': 115}{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}Failed
budget stops at the first region that does not fit{'cset': [1, 2, 6, 7, 3], 'reclaimed': 735, 'time': 65}{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}Failed
expensive region first stops selection{'cset': [1, 2, 6], 'reclaimed': 560, 'time': 40}{'cset': [1, 2], 'reclaimed': 160, 'time': 40}Failed
region at exactly the liveness threshold excluded{'cset': [1, 2, 6, 7, 3, 5], 'reclaimed': 785, 'time': 115}{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}Failed
higher threshold admits more regions{'cset': [1, 2, 6, 7, 3, 5, 4, 8], 'reclaimed': 810, 'time': 290}{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}Failed
cost multiplier{'cset': [1, 2, 6], 'reclaimed': 560, 'time': 80}{'cset': [1, 2], 'reclaimed': 160, 'time': 80}Failed
control: only young regions fit{'cset': [1, 2], 'reclaimed': 160, 'time': 40}{'cset': [1, 2], 'reclaimed': 160, 'time': 40}Passed

SHA-256 / e26516cdb534c2e0a7c1d9a8759b5f249edf1b9a01b8f057bd447da81efdea49

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 fixtureActualExpectedOutcome
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.793950+00:00.

Case digest / 59b9a8e43f9ba8426470307ae397c9330edb690798637903ac07108e7e9f0d11