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

N = 1
observations = []
def solve(events, min_heap):
    gogc = 100
    live = 0
    marked = 0
    heap = 0
    goal = min_heap
    gcs = []
    for ev in events:
        if ev[0] == 'alloc':
            heap += ev[1]
            live += ev[1]
            if gogc >= 0 and heap >= goal:
                gcs.append(heap)
                heap = 0
                marked = live
                goal = max(live + live * gogc // 100, min_heap)
        elif ev[0] == 'drop':
            live -= ev[1]
        else:
            gogc = ev[1]
            if gogc >= 0:
                goal = max(marked + marked * gogc // 100, min_heap)
    return {'gcs': gcs, 'goal': goal, 'heap': heap}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: heap reaching the goal exactly',
   ([['alloc', 55], ['alloc', 55], ['drop', 30], ['alloc', 25]], 110),
   {'gcs': [110], 'goal': 220, 'heap': 135}),
  ('goal grows with live heap',
   ([['alloc', 330], ['drop', 110], ['alloc', 220], ['alloc', 10]], 110),
   {'gcs': [330], 'goal': 660, 'heap': 560}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 220], ['alloc', 111]], 110),
   {'gcs': [220, 331], 'goal': 496, 'heap': 331}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 330], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 110),
   {'gcs': [331, 332], 'goal': 332, 'heap': 332}),
  ('goal recomputed from last marked heap',
   ([['alloc', 220], ['drop', 110], ['alloc', 10], ['setgc', 200], ['alloc', 330], ['alloc', 110]], 110),
   {'gcs': [220, 670], 'goal': 1680, 'heap': 560}),
  ('small live heap uses the minimum goal',
   ([['alloc', 110],
     ['drop', 110],
     ['alloc', 109],
     ['drop', 109],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 104]],
    110),
   {'gcs': [110, 220, 110], 'goal': 220, 'heap': 110}),
  ('control: no allocation', ([['setgc', 50]], 110), {'gcs': [], 'goal': 110, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 60], ['alloc', 60], ['drop', 30], ['alloc', 25]], 120),
   {'gcs': [120], 'goal': 240, 'heap': 145}),
  ('goal grows with live heap',
   ([['alloc', 360], ['drop', 120], ['alloc', 240], ['alloc', 10]], 120),
   {'gcs': [360], 'goal': 720, 'heap': 610}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 240], ['alloc', 121]], 120),
   {'gcs': [240, 361], 'goal': 541, 'heap': 361}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 360], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 120),
   {'gcs': [361, 362], 'goal': 362, 'heap': 362}),
  ('goal recomputed from last marked heap',
   ([['alloc', 240], ['drop', 120], ['alloc', 10], ['setgc', 200], ['alloc', 360], ['alloc', 120]], 120),
   {'gcs': [240, 730], 'goal': 1830, 'heap': 610}),
  ('small live heap uses the minimum goal',
   ([['alloc', 120],
     ['drop', 120],
     ['alloc', 119],
     ['drop', 119],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 114]],
    120),
   {'gcs': [120, 240, 120], 'goal': 240, 'heap': 120}),
  ('control: no allocation', ([['setgc', 50]], 120), {'gcs': [], 'goal': 120, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 65], ['alloc', 65], ['drop', 30], ['alloc', 25]], 130),
   {'gcs': [130], 'goal': 260, 'heap': 155}),
  ('goal grows with live heap',
   ([['alloc', 390], ['drop', 130], ['alloc', 260], ['alloc', 10]], 130),
   {'gcs': [390], 'goal': 780, 'heap': 660}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 260], ['alloc', 131]], 130),
   {'gcs': [260, 391], 'goal': 586, 'heap': 391}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 390], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 130),
   {'gcs': [391, 392], 'goal': 392, 'heap': 392}),
  ('goal recomputed from last marked heap',
   ([['alloc', 260], ['drop', 130], ['alloc', 10], ['setgc', 200], ['alloc', 390], ['alloc', 130]], 130),
   {'gcs': [260, 790], 'goal': 1980, 'heap': 660}),
  ('small live heap uses the minimum goal',
   ([['alloc', 130],
     ['drop', 130],
     ['alloc', 129],
     ['drop', 129],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 124]],
    130),
   {'gcs': [130, 260, 130], 'goal': 260, 'heap': 130}),
  ('control: no allocation', ([['setgc', 50]], 130), {'gcs': [], 'goal': 130, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 70], ['alloc', 70], ['drop', 30], ['alloc', 25]], 140),
   {'gcs': [140], 'goal': 280, 'heap': 165}),
  ('goal grows with live heap',
   ([['alloc', 420], ['drop', 140], ['alloc', 280], ['alloc', 10]], 140),
   {'gcs': [420], 'goal': 840, 'heap': 710}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 280], ['alloc', 141]], 140),
   {'gcs': [280, 421], 'goal': 631, 'heap': 421}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 420], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 140),
   {'gcs': [421, 422], 'goal': 422, 'heap': 422}),
  ('goal recomputed from last marked heap',
   ([['alloc', 280], ['drop', 140], ['alloc', 10], ['setgc', 200], ['alloc', 420], ['alloc', 140]], 140),
   {'gcs': [280, 850], 'goal': 2130, 'heap': 710}),
  ('small live heap uses the minimum goal',
   ([['alloc', 140],
     ['drop', 140],
     ['alloc', 139],
     ['drop', 139],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 134]],
    140),
   {'gcs': [140, 280, 140], 'goal': 280, 'heap': 140}),
  ('control: no allocation', ([['setgc', 50]], 140), {'gcs': [], 'goal': 140, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 75], ['alloc', 75], ['drop', 30], ['alloc', 25]], 150),
   {'gcs': [150], 'goal': 300, 'heap': 175}),
  ('goal grows with live heap',
   ([['alloc', 450], ['drop', 150], ['alloc', 300], ['alloc', 10]], 150),
   {'gcs': [450], 'goal': 900, 'heap': 760}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 300], ['alloc', 151]], 150),
   {'gcs': [300, 451], 'goal': 676, 'heap': 451}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 450], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 150),
   {'gcs': [451, 452], 'goal': 452, 'heap': 452}),
  ('goal recomputed from last marked heap',
   ([['alloc', 300], ['drop', 150], ['alloc', 10], ['setgc', 200], ['alloc', 450], ['alloc', 150]], 150),
   {'gcs': [300, 910], 'goal': 2280, 'heap': 760}),
  ('small live heap uses the minimum goal',
   ([['alloc', 150],
     ['drop', 150],
     ['alloc', 149],
     ['drop', 149],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 144]],
    150),
   {'gcs': [150, 300, 150], 'goal': 300, 'heap': 150}),
  ('control: no allocation', ([['setgc', 50]], 150), {'gcs': [], 'goal': 150, 'heap': 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)

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

N = 1
observations = []
def solve(events, min_heap):
    gogc = 100
    live = 0
    marked = 0
    heap = 0
    goal = min_heap
    gcs = []
    for ev in events:
        if ev[0] == 'alloc':
            heap += ev[1]
            live += ev[1]
            if gogc >= 0 and heap >= goal:
                gcs.append(heap)
                heap = marked
                marked = live
                goal = max(live + live * gogc // 100, min_heap)
        elif ev[0] == 'drop':
            live -= ev[1]
        else:
            gogc = ev[1]
            if gogc >= 0:
                goal = max(marked + marked * gogc // 100, min_heap)
    return {'gcs': gcs, 'goal': goal, 'heap': heap}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: heap reaching the goal exactly',
   ([['alloc', 55], ['alloc', 55], ['drop', 30], ['alloc', 25]], 110),
   {'gcs': [110], 'goal': 220, 'heap': 135}),
  ('goal grows with live heap',
   ([['alloc', 330], ['drop', 110], ['alloc', 220], ['alloc', 10]], 110),
   {'gcs': [330], 'goal': 660, 'heap': 560}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 220], ['alloc', 111]], 110),
   {'gcs': [220, 331], 'goal': 496, 'heap': 331}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 330], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 110),
   {'gcs': [331, 332], 'goal': 332, 'heap': 332}),
  ('goal recomputed from last marked heap',
   ([['alloc', 220], ['drop', 110], ['alloc', 10], ['setgc', 200], ['alloc', 330], ['alloc', 110]], 110),
   {'gcs': [220, 670], 'goal': 1680, 'heap': 560}),
  ('small live heap uses the minimum goal',
   ([['alloc', 110],
     ['drop', 110],
     ['alloc', 109],
     ['drop', 109],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 104]],
    110),
   {'gcs': [110, 220, 110], 'goal': 220, 'heap': 110}),
  ('control: no allocation', ([['setgc', 50]], 110), {'gcs': [], 'goal': 110, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 60], ['alloc', 60], ['drop', 30], ['alloc', 25]], 120),
   {'gcs': [120], 'goal': 240, 'heap': 145}),
  ('goal grows with live heap',
   ([['alloc', 360], ['drop', 120], ['alloc', 240], ['alloc', 10]], 120),
   {'gcs': [360], 'goal': 720, 'heap': 610}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 240], ['alloc', 121]], 120),
   {'gcs': [240, 361], 'goal': 541, 'heap': 361}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 360], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 120),
   {'gcs': [361, 362], 'goal': 362, 'heap': 362}),
  ('goal recomputed from last marked heap',
   ([['alloc', 240], ['drop', 120], ['alloc', 10], ['setgc', 200], ['alloc', 360], ['alloc', 120]], 120),
   {'gcs': [240, 730], 'goal': 1830, 'heap': 610}),
  ('small live heap uses the minimum goal',
   ([['alloc', 120],
     ['drop', 120],
     ['alloc', 119],
     ['drop', 119],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 114]],
    120),
   {'gcs': [120, 240, 120], 'goal': 240, 'heap': 120}),
  ('control: no allocation', ([['setgc', 50]], 120), {'gcs': [], 'goal': 120, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 65], ['alloc', 65], ['drop', 30], ['alloc', 25]], 130),
   {'gcs': [130], 'goal': 260, 'heap': 155}),
  ('goal grows with live heap',
   ([['alloc', 390], ['drop', 130], ['alloc', 260], ['alloc', 10]], 130),
   {'gcs': [390], 'goal': 780, 'heap': 660}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 260], ['alloc', 131]], 130),
   {'gcs': [260, 391], 'goal': 586, 'heap': 391}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 390], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 130),
   {'gcs': [391, 392], 'goal': 392, 'heap': 392}),
  ('goal recomputed from last marked heap',
   ([['alloc', 260], ['drop', 130], ['alloc', 10], ['setgc', 200], ['alloc', 390], ['alloc', 130]], 130),
   {'gcs': [260, 790], 'goal': 1980, 'heap': 660}),
  ('small live heap uses the minimum goal',
   ([['alloc', 130],
     ['drop', 130],
     ['alloc', 129],
     ['drop', 129],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 124]],
    130),
   {'gcs': [130, 260, 130], 'goal': 260, 'heap': 130}),
  ('control: no allocation', ([['setgc', 50]], 130), {'gcs': [], 'goal': 130, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 70], ['alloc', 70], ['drop', 30], ['alloc', 25]], 140),
   {'gcs': [140], 'goal': 280, 'heap': 165}),
  ('goal grows with live heap',
   ([['alloc', 420], ['drop', 140], ['alloc', 280], ['alloc', 10]], 140),
   {'gcs': [420], 'goal': 840, 'heap': 710}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 280], ['alloc', 141]], 140),
   {'gcs': [280, 421], 'goal': 631, 'heap': 421}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 420], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 140),
   {'gcs': [421, 422], 'goal': 422, 'heap': 422}),
  ('goal recomputed from last marked heap',
   ([['alloc', 280], ['drop', 140], ['alloc', 10], ['setgc', 200], ['alloc', 420], ['alloc', 140]], 140),
   {'gcs': [280, 850], 'goal': 2130, 'heap': 710}),
  ('small live heap uses the minimum goal',
   ([['alloc', 140],
     ['drop', 140],
     ['alloc', 139],
     ['drop', 139],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 134]],
    140),
   {'gcs': [140, 280, 140], 'goal': 280, 'heap': 140}),
  ('control: no allocation', ([['setgc', 50]], 140), {'gcs': [], 'goal': 140, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 75], ['alloc', 75], ['drop', 30], ['alloc', 25]], 150),
   {'gcs': [150], 'goal': 300, 'heap': 175}),
  ('goal grows with live heap',
   ([['alloc', 450], ['drop', 150], ['alloc', 300], ['alloc', 10]], 150),
   {'gcs': [450], 'goal': 900, 'heap': 760}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 300], ['alloc', 151]], 150),
   {'gcs': [300, 451], 'goal': 676, 'heap': 451}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 450], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 150),
   {'gcs': [451, 452], 'goal': 452, 'heap': 452}),
  ('goal recomputed from last marked heap',
   ([['alloc', 300], ['drop', 150], ['alloc', 10], ['setgc', 200], ['alloc', 450], ['alloc', 150]], 150),
   {'gcs': [300, 910], 'goal': 2280, 'heap': 760}),
  ('small live heap uses the minimum goal',
   ([['alloc', 150],
     ['drop', 150],
     ['alloc', 149],
     ['drop', 149],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 144]],
    150),
   {'gcs': [150, 300, 150], 'goal': 300, 'heap': 150}),
  ('control: no allocation', ([['setgc', 50]], 150), {'gcs': [], 'goal': 150, 'heap': 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)

prompt:
Live data is forgotten, so the next trigger happens far too late.

GOGC-style pacing starting at 100 percent with goal = min_heap. alloc b adds b to the heap and to live bytes and triggers a collection when collection is enabled (percentage >= 0) and heap >= goal: the heap shrinks to the live bytes, which become the marked size, and goal = max(marked + marked * pct // 100, min_heap). drop b turns b live bytes into garbage. setgc p changes the percentage (-1 disables) and, unless disabled, recomputes the goal from the last marked size. Return the heap sizes at which collections triggered, the final goal and heap.

split: open-access


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

N = 1
observations = []
def solve(objs, roots, events, tenure):
    objs = {k: {'gen': v[0], 'addr': v[1], 'fields': list(v[2]), 'age': 0} for k, v in objs.items()}
    roots = list(roots)
    cards = set()
    log = []
    next_addr = 4096
    def slot_card(o, i):
        return objs[o]['addr'] // 64
    try:
        for ev in events:
            if ev[0] == 'store':
                _, src, i, dst = ev
                objs[src]['fields'][i] = dst
                if objs[src]['gen'] == 'old' and dst is not None and objs[dst]['gen'] == 'young':
                    cards.add(slot_card(src, i))
            elif ev[0] == 'alloc':
                objs[ev[1]] = {'gen': 'young', 'addr': 0, 'fields': [None], 'age': 0}
            elif ev[0] == 'root':
                roots.append(ev[1])
            elif ev[0] == 'unroot':
                roots.remove(ev[1])
            else:
                grey = [r for r in roots if objs[r]['gen'] == 'young']
                for o, ob in objs.items():
                    if ob['gen'] == 'old':
                        for i, f in enumerate(ob['fields']):
                            if slot_card(o, i) in cards and f is not None and objs[f]['gen'] == 'young':
                                grey.append(f)
                live = set()
                while grey:
                    y = grey.pop()
                    if y in live:
                        continue
                    live.add(y)
                    for f in objs[y]['fields']:
                        if f is not None and objs[f]['gen'] == 'young':
                            grey.append(f)
                dead = sorted(k for k, ob in objs.items() if ob['gen'] == 'young' and k not in live)
                for k in dead:
                    del objs[k]
                promoted = []
                for k in sorted(live):
                    objs[k]['age'] += 1
                    if objs[k]['age'] >= tenure:
                        objs[k]['gen'] = 'old'
                        objs[k]['addr'] = next_addr
                        next_addr += 64
                        promoted.append(k)
                cards = set()
                for o in [k for k, ob in objs.items() if ob['gen'] == 'old']:
                    for i, f in enumerate(objs[o]['fields']):
                        if f is not None and objs[f]['gen'] == 'young':
                            cards.add(slot_card(o, i))
                log.append({'freed': dead, 'promoted': promoted, 'cards': sorted(cards)})
    except KeyError as e:
        log.append({'dangling': e.args[0]})
    return log
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [1], 'freed': [13, 14], 'promoted': []}, {'cards': [1], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [0, 1], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [2], 'freed': [13, 14], 'promoted': []}, {'cards': [2], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [1, 2], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [3], 'freed': [13, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [2, 3], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [4], 'freed': [13, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [6], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [3, 4], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [5], 'freed': [13, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [7], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [4, 5], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

N = 1
observations = []
def solve(objs, roots, events, tenure):
    objs = {k: {'gen': v[0], 'addr': v[1], 'fields': list(v[2]), 'age': 0} for k, v in objs.items()}
    roots = list(roots)
    cards = set()
    log = []
    next_addr = 4096
    def slot_card(o, i):
        return (objs[o]['addr'] + i) // 64
    try:
        for ev in events:
            if ev[0] == 'store':
                _, src, i, dst = ev
                objs[src]['fields'][i] = dst
                if objs[src]['gen'] == 'old' and dst is not None and objs[dst]['gen'] == 'young':
                    cards.add(slot_card(src, i))
            elif ev[0] == 'alloc':
                objs[ev[1]] = {'gen': 'young', 'addr': 0, 'fields': [None], 'age': 0}
            elif ev[0] == 'root':
                roots.append(ev[1])
            elif ev[0] == 'unroot':
                roots.remove(ev[1])
            else:
                grey = [r for r in roots if objs[r]['gen'] == 'young']
                for o, ob in objs.items():
                    if ob['gen'] == 'old':
                        for i, f in enumerate(ob['fields']):
                            if slot_card(o, i) in cards and f is not None and objs[f]['gen'] == 'young':
                                grey.append(f)
                live = set()
                while grey:
                    y = grey.pop()
                    if y in live:
                        continue
                    live.add(y)
                    for f in objs[y]['fields']:
                        if f is not None and objs[f]['gen'] == 'young':
                            grey.append(f)
                dead = sorted(k for k, ob in objs.items() if ob['gen'] == 'young' and k not in live)
                for k in dead:
                    del objs[k]
                promoted = []
                for k in sorted(live):
                    objs[k]['age'] += 1
                    if objs[k]['age'] >= tenure:
                        objs[k]['gen'] = 'old'
                        objs[k]['addr'] = next_addr
                        next_addr += 64
                        promoted.append(k)
                cards = set()
                for o in [k for k, ob in objs.items() if ob['gen'] == 'old']:
                    for i, f in enumerate(objs[o]['fields']):
                        if f is not None and objs[f]['gen'] == 'young':
                            cards.add(slot_card(o, i))
                log.append({'freed': dead, 'promoted': promoted, 'cards': sorted(cards)})
    except KeyError as e:
        log.append({'dangling': e.args[0]})
    return log
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [1], 'freed': [13, 14], 'promoted': []}, {'cards': [1], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [0, 1], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [2], 'freed': [13, 14], 'promoted': []}, {'cards': [2], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [1, 2], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [3], 'freed': [13, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [2, 3], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [4], 'freed': [13, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [6], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [3, 4], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [5], 'freed': [13, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [7], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [4, 5], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Slots that lie in the card after their object's header are recorded against the wrong card.

Two generations. objs maps id -> [generation, address, fields]; a field slot i of an old object lives at address + 8*i and belongs to card (slot address // 64). store writes a field and, when an old object receives a young reference, dirties that slot's card. minor: roots plus young referents of old slots in dirty cards seed a trace through young objects; unreached young objects are freed; survivors age by one and are promoted (addresses from 4096 in 64-byte steps) when age >= tenure; the card set is then rebuilt from every old slot that still references a young object. alloc id creates a young object with one null field; root/unroot edit the root list. Return per-minor {freed, promoted, cards}; following a freed object reports {"dangling": id}.

split: open-access


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

N = 1
observations = []
def solve(objs, roots, events, tenure):
    objs = {k: {'gen': v[0], 'addr': v[1], 'fields': list(v[2]), 'age': 0} for k, v in objs.items()}
    roots = list(roots)
    cards = set()
    log = []
    next_addr = 4096
    def slot_card(o, i):
        return (objs[o]['addr'] + 8 * i) // 64
    try:
        for ev in events:
            if ev[0] == 'store':
                _, src, i, dst = ev
                objs[src]['fields'][i] = dst
                if objs[src]['gen'] == 'young' and dst is not None and objs[dst]['gen'] == 'young':
                    cards.add(slot_card(src, i))
            elif ev[0] == 'alloc':
                objs[ev[1]] = {'gen': 'young', 'addr': 0, 'fields': [None], 'age': 0}
            elif ev[0] == 'root':
                roots.append(ev[1])
            elif ev[0] == 'unroot':
                roots.remove(ev[1])
            else:
                grey = [r for r in roots if objs[r]['gen'] == 'young']
                for o, ob in objs.items():
                    if ob['gen'] == 'old':
                        for i, f in enumerate(ob['fields']):
                            if slot_card(o, i) in cards and f is not None and objs[f]['gen'] == 'young':
                                grey.append(f)
                live = set()
                while grey:
                    y = grey.pop()
                    if y in live:
                        continue
                    live.add(y)
                    for f in objs[y]['fields']:
                        if f is not None and objs[f]['gen'] == 'young':
                            grey.append(f)
                dead = sorted(k for k, ob in objs.items() if ob['gen'] == 'young' and k not in live)
                for k in dead:
                    del objs[k]
                promoted = []
                for k in sorted(live):
                    objs[k]['age'] += 1
                    if objs[k]['age'] >= tenure:
                        objs[k]['gen'] = 'old'
                        objs[k]['addr'] = next_addr
                        next_addr += 64
                        promoted.append(k)
                cards = set()
                for o in [k for k, ob in objs.items() if ob['gen'] == 'old']:
                    for i, f in enumerate(objs[o]['fields']):
                        if f is not None and objs[f]['gen'] == 'young':
                            cards.add(slot_card(o, i))
                log.append({'freed': dead, 'promoted': promoted, 'cards': sorted(cards)})
    except KeyError as e:
        log.append({'dangling': e.args[0]})
    return log
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [1], 'freed': [13, 14], 'promoted': []}, {'cards': [1], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [0, 1], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [2], 'freed': [13, 14], 'promoted': []}, {'cards': [2], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [1, 2], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [3], 'freed': [13, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [2, 3], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [4], 'freed': [13, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [6], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [3, 4], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [5], 'freed': [13, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [7], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [4, 5], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(objs, roots, events, tenure):
    objs = {k: {'gen': v[0], 'addr': v[1], 'fields': list(v[2]), 'age': 0} for k, v in objs.items()}
    roots = list(roots)
    cards = set()
    log = []
    next_addr = 4096
    def slot_card(o, i):
        return (objs[o]['addr'] + 8 * i) // 64
    try:
        for ev in events:
            if ev[0] == 'store':
                _, src, i, dst = ev
                objs[src]['fields'][i] = dst
                if objs[src]['gen'] == 'old' and dst is not None and objs[dst]['age'] == 0:
                    cards.add(slot_card(src, i))
            elif ev[0] == 'alloc':
                objs[ev[1]] = {'gen': 'young', 'addr': 0, 'fields': [None], 'age': 0}
            elif ev[0] == 'root':
                roots.append(ev[1])
            elif ev[0] == 'unroot':
                roots.remove(ev[1])
            else:
                grey = [r for r in roots if objs[r]['gen'] == 'young']
                for o, ob in objs.items():
                    if ob['gen'] == 'old':
                        for i, f in enumerate(ob['fields']):
                            if slot_card(o, i) in cards and f is not None and objs[f]['gen'] == 'young':
                                grey.append(f)
                live = set()
                while grey:
                    y = grey.pop()
                    if y in live:
                        continue
                    live.add(y)
                    for f in objs[y]['fields']:
                        if f is not None and objs[f]['gen'] == 'young':
                            grey.append(f)
                dead = sorted(k for k, ob in objs.items() if ob['gen'] == 'young' and k not in live)
                for k in dead:
                    del objs[k]
                promoted = []
                for k in sorted(live):
                    objs[k]['age'] += 1
                    if objs[k]['age'] >= tenure:
                        objs[k]['gen'] = 'old'
                        objs[k]['addr'] = next_addr
                        next_addr += 64
                        promoted.append(k)
                cards = set()
                for o in [k for k, ob in objs.items() if ob['gen'] == 'old']:
                    for i, f in enumerate(objs[o]['fields']):
                        if f is not None and objs[f]['gen'] == 'young':
                            cards.add(slot_card(o, i))
                log.append({'freed': dead, 'promoted': promoted, 'cards': sorted(cards)})
    except KeyError as e:
        log.append({'dangling': e.args[0]})
    return log
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [1], 'freed': [13, 14], 'promoted': []}, {'cards': [1], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [0, 1], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 56, [None, None]],
     2: ['old', 192, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [2], 'freed': [13, 14], 'promoted': []}, {'cards': [2], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [1, 2], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 120, [None, None]],
     2: ['old', 256, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [3], 'freed': [13, 14], 'promoted': []}, {'cards': [3], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [2, 3], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 184, [None, None]],
     2: ['old', 320, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [4], 'freed': [13, 14], 'promoted': []}, {'cards': [4], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [6], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [3, 4], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 248, [None, None]],
     2: ['old', 384, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])],
 [('regression: old-to-young edge survives two minor collections',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 1, 11], ['minor'], ['minor']],
    5),
   [{'cards': [5], 'freed': [13, 14], 'promoted': []}, {'cards': [5], 'freed': [], 'promoted': []}]),
  ('edge stored after the target survived once',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [13],
    [['minor'], ['store', 2, 0, 13], ['unroot', 13], ['minor']],
    5),
   [{'cards': [], 'freed': [11, 12, 14], 'promoted': []}, {'cards': [7], 'freed': [], 'promoted': []}]),
  ('promotion at the tenuring threshold',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [], 'freed': [], 'promoted': [11, 12]},
    {'cards': [], 'freed': [], 'promoted': []}]),
  ('promoted object pointing at a younger object',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [11],
    [['minor'], ['alloc', 15], ['store', 11, 0, 15], ['minor'], ['minor']],
    2),
   [{'cards': [], 'freed': [13, 14], 'promoted': []},
    {'cards': [64], 'freed': [12], 'promoted': [11]},
    {'cards': [], 'freed': [], 'promoted': [15]}]),
  ('card of a slot in the next card',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [],
    [['store', 1, 0, 13], ['store', 1, 1, 14], ['minor']],
    4),
   [{'cards': [4, 5], 'freed': [11, 12], 'promoted': []}]),
  ('control: unreferenced young objects die',
   ({1: ['old', 312, [None, None]],
     2: ['old', 448, [None]],
     11: ['young', 0, [12]],
     12: ['young', 0, []],
     13: ['young', 0, []],
     14: ['young', 0, [None]]},
    [12],
    [['minor']],
    3),
   [{'cards': [], 'freed': [11, 13, 14], 'promoted': []}])]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Young objects reachable only from old objects are freed and later dereferenced.

Two generations. objs maps id -> [generation, address, fields]; a field slot i of an old object lives at address + 8*i and belongs to card (slot address // 64). store writes a field and, when an old object receives a young reference, dirties that slot's card. minor: roots plus young referents of old slots in dirty cards seed a trace through young objects; unreached young objects are freed; survivors age by one and are promoted (addresses from 4096 in 64-byte steps) when age >= tenure; the card set is then rebuilt from every old slot that still references a young object. alloc id creates a young object with one null field; root/unroot edit the root list. Return per-minor {freed, promoted, cards}; following a freed object reports {"dangling": id}.

split: open-access