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

N = 1
observations = []
def solve(events):
    objs = {}
    freed = []
    dealloc = []
    out = []
    def release(o):
        if o is None:
            return
        b = objs[o]
        b['rc'] -= 1
        if b['rc'] == 0:
            freed.append(o)
            kids, b['fields'] = b['fields'], []
            if b['weak'] == 0:
                dealloc.append(o)
                del objs[o]
            for c in kids:
                release(c)
    try:
        for ev in events:
            op = ev[0]
            if op == 'new':
                objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
            elif op == 'drop':
                release(ev[1])
            elif op == 'store':
                _, src, field, dst = ev
                if dst is not None:
                    objs[dst]['rc'] += 1
                old = objs[src]['fields'][field]
                objs[src]['fields'][field] = dst
                release(old)
            elif op == 'weak':
                objs[ev[1]]['weak'] += 1
            elif op == 'unweak':
                b = objs[ev[1]]
                b['weak'] -= 1
                if b['weak'] == 0:
                    dealloc.append(ev[1])
                    del objs[ev[1]]
            else:
                b = objs[ev[1]]
                if b['rc'] > 0:
                    b['rc'] += 1
                    out.append(True)
                else:
                    out.append(False)
    except (KeyError, IndexError):
        out.append('use-after-free')
    return {'out': out, 'freed': freed, 'dealloc': dealloc,
            'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 12, 0, 13],
     ['drop', 13],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 13]],),
   {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 12],
     ['upgrade', 12]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 11, 2],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['store', 11, 1, 12],
     ['drop', 12],
     ['drop', 11]],),
   {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['weak', 11],
     ['drop', 11],
     ['upgrade', 11],
     ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 11, 0, 12],
     ['store', 12, 0, 13],
     ['drop', 12],
     ['drop', 13],
     ['drop', 11]],),
   {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 22, 0, 23],
     ['drop', 23],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 23]],),
   {'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 22],
     ['upgrade', 22]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 21, 2],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['store', 21, 1, 22],
     ['drop', 22],
     ['drop', 21]],),
   {'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['weak', 21],
     ['drop', 21],
     ['upgrade', 21],
     ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 21, 0, 22],
     ['store', 22, 0, 23],
     ['drop', 22],
     ['drop', 23],
     ['drop', 21]],),
   {'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 32, 0, 33],
     ['drop', 33],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 33]],),
   {'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 32],
     ['upgrade', 32]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 31, 2],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['store', 31, 1, 32],
     ['drop', 32],
     ['drop', 31]],),
   {'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['weak', 31],
     ['drop', 31],
     ['upgrade', 31],
     ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 31, 0, 32],
     ['store', 32, 0, 33],
     ['drop', 32],
     ['drop', 33],
     ['drop', 31]],),
   {'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 42, 0, 43],
     ['drop', 43],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 43]],),
   {'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 42],
     ['upgrade', 42]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 41, 2],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['store', 41, 1, 42],
     ['drop', 42],
     ['drop', 41]],),
   {'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['weak', 41],
     ['drop', 41],
     ['upgrade', 41],
     ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 41, 0, 42],
     ['store', 42, 0, 43],
     ['drop', 42],
     ['drop', 43],
     ['drop', 41]],),
   {'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 52, 0, 53],
     ['drop', 53],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 53]],),
   {'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 52],
     ['upgrade', 52]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 51, 2],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['store', 51, 1, 52],
     ['drop', 52],
     ['drop', 51]],),
   {'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['weak', 51],
     ['drop', 51],
     ['upgrade', 51],
     ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 51, 0, 52],
     ['store', 52, 0, 53],
     ['drop', 52],
     ['drop', 53],
     ['drop', 51]],),
   {'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
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):
    objs = {}
    freed = []
    dealloc = []
    out = []
    def release(o):
        if o is None:
            return
        b = objs[o]
        b['rc'] -= 1
        if b['rc'] == 0:
            freed.append(o)
            kids, b['fields'] = b['fields'], []
            if b['weak'] == 0:
                dealloc.append(o)
                del objs[o]
            for c in kids:
                release(c)
    try:
        for ev in events:
            op = ev[0]
            if op == 'new':
                objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
            elif op == 'drop':
                release(ev[1])
            elif op == 'store':
                _, src, field, dst = ev
                if dst is not None:
                    objs[dst]['rc'] += 1
                old = objs[src]['fields'][field]
                objs[src]['fields'][field] = dst
                release(old)
            elif op == 'weak':
                objs[ev[1]]['weak'] += 1
            elif op == 'unweak':
                b = objs[ev[1]]
                b['weak'] -= 1
                if b['weak'] == 0 and not b['fields']:
                    dealloc.append(ev[1])
                    del objs[ev[1]]
            else:
                b = objs[ev[1]]
                if b['rc'] > 0:
                    b['rc'] += 1
                    out.append(True)
                else:
                    out.append(False)
    except (KeyError, IndexError):
        out.append('use-after-free')
    return {'out': out, 'freed': freed, 'dealloc': dealloc,
            'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 12, 0, 13],
     ['drop', 13],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 13]],),
   {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['drop', 12],
     ['store', 11, 0, 12],
     ['upgrade', 12]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 11, 2],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['store', 11, 1, 12],
     ['drop', 12],
     ['drop', 11]],),
   {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 11, 1],
     ['new', 12, 0],
     ['store', 11, 0, 12],
     ['weak', 11],
     ['drop', 11],
     ['upgrade', 11],
     ['unweak', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
   {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 11, 1],
     ['new', 12, 1],
     ['new', 13, 0],
     ['store', 11, 0, 12],
     ['store', 12, 0, 13],
     ['drop', 12],
     ['drop', 13],
     ['drop', 11]],),
   {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 22, 0, 23],
     ['drop', 23],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 23]],),
   {'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['drop', 22],
     ['store', 21, 0, 22],
     ['upgrade', 22]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 21, 2],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['store', 21, 1, 22],
     ['drop', 22],
     ['drop', 21]],),
   {'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 21, 1],
     ['new', 22, 0],
     ['store', 21, 0, 22],
     ['weak', 21],
     ['drop', 21],
     ['upgrade', 21],
     ['unweak', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
   {'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 21, 1],
     ['new', 22, 1],
     ['new', 23, 0],
     ['store', 21, 0, 22],
     ['store', 22, 0, 23],
     ['drop', 22],
     ['drop', 23],
     ['drop', 21]],),
   {'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 32, 0, 33],
     ['drop', 33],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 33]],),
   {'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['drop', 32],
     ['store', 31, 0, 32],
     ['upgrade', 32]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 31, 2],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['store', 31, 1, 32],
     ['drop', 32],
     ['drop', 31]],),
   {'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 31, 1],
     ['new', 32, 0],
     ['store', 31, 0, 32],
     ['weak', 31],
     ['drop', 31],
     ['upgrade', 31],
     ['unweak', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
   {'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 31, 1],
     ['new', 32, 1],
     ['new', 33, 0],
     ['store', 31, 0, 32],
     ['store', 32, 0, 33],
     ['drop', 32],
     ['drop', 33],
     ['drop', 31]],),
   {'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 42, 0, 43],
     ['drop', 43],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 43]],),
   {'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['drop', 42],
     ['store', 41, 0, 42],
     ['upgrade', 42]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 41, 2],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['store', 41, 1, 42],
     ['drop', 42],
     ['drop', 41]],),
   {'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 41, 1],
     ['new', 42, 0],
     ['store', 41, 0, 42],
     ['weak', 41],
     ['drop', 41],
     ['upgrade', 41],
     ['unweak', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
   {'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 41, 1],
     ['new', 42, 1],
     ['new', 43, 0],
     ['store', 41, 0, 42],
     ['store', 42, 0, 43],
     ['drop', 42],
     ['drop', 43],
     ['drop', 41]],),
   {'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
 [('regression: overwrite with a child of the old value',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 52, 0, 53],
     ['drop', 53],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 53]],),
   {'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
  ('self-assignment of the only reference',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['drop', 52],
     ['store', 51, 0, 52],
     ['upgrade', 52]],),
   {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
  ('object referenced twice by one parent',
   ([['new', 51, 2],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['store', 51, 1, 52],
     ['drop', 52],
     ['drop', 51]],),
   {'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
  ('upgrade after the last strong reference dies',
   ([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
  ('weak reference keeps the control block only',
   ([['new', 51, 1],
     ['new', 52, 0],
     ['store', 51, 0, 52],
     ['weak', 51],
     ['drop', 51],
     ['upgrade', 51],
     ['unweak', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
  ('dropping a weak reference to a live object',
   ([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
   {'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
  ('control: chain release order',
   ([['new', 51, 1],
     ['new', 52, 1],
     ['new', 53, 0],
     ['store', 51, 0, 52],
     ['store', 52, 0, 53],
     ['drop', 52],
     ['drop', 53],
     ['drop', 51]],),
   {'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
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:
A strongly held object is deallocated when its last weak observer goes away.

Objects carry a strong count and a weak count. new id k: strong 1 (the creating reference), k null fields. drop id: release one strong reference. store src i dst: retain dst, then write, then release the old value. When the strong count reaches 0 the object is destroyed (recorded in freed, its fields released recursively in field order) and, if no weak references remain, its control block is deallocated too; unweak deallocates a destroyed object's block when the last weak reference goes. upgrade id succeeds (and adds a strong reference) only while the strong count is positive. Touching a deallocated block reports "use-after-free".

split: open-access


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

N = 1
observations = []
def solve(heap, external, candidates):
    rc = {o: external.get(o, 0) for o in heap}
    for o, kids in heap.items():
        for c in kids:
            rc[c] += 1
    color = {o: 'black' for o in heap}
    def mark_gray(o):
        if color[o] != 'gray':
            color[o] = 'gray'
            for c in heap[o]:
                if color[c] != 'gray':
                    rc[c] -= 1
                mark_gray(c)
    def scan(o):
        if color[o] == 'gray':
            if rc[o] > 0:
                scan_black(o)
            else:
                color[o] = 'white'
                for c in heap[o]:
                    scan(c)
    def scan_black(o):
        color[o] = 'black'
        for c in heap[o]:
            rc[c] += 1
            if color[c] != 'black':
                scan_black(c)
    for o in candidates:
        mark_gray(o)
    for o in candidates:
        scan(o)
    garbage = sorted(o for o in heap if color[o] == 'white')
    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: three-object garbage cycle',
   ({11: [12], 12: [13], 13: [11]}, {}, [11]),
   {'garbage': [11, 12, 13], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),
   {'garbage': [11, 12], 'rc': {'13': 1}}),
  ('externally held cycle restores its counts',
   ({11: [12], 12: [11]}, {12: 1}, [11]),
   {'garbage': [], 'rc': {'11': 1, '12': 2}}),
  ('candidate sharing a child with a live object',
   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),
   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),
  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),
  ('object with two external references',
   ({18: [19], 19: []}, {18: 2}, [18]),
   {'garbage': [], 'rc': {'18': 2, '19': 1}}),
  ('control: acyclic live candidate',
   ({11: [12], 12: []}, {11: 1}, [11, 12]),
   {'garbage': [], 'rc': {'11': 1, '12': 1}})],
 [('regression: three-object garbage cycle',
   ({21: [22], 22: [23], 23: [21]}, {}, [21]),
   {'garbage': [21, 22, 23], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),
   {'garbage': [21, 22], 'rc': {'23': 1}}),
  ('externally held cycle restores its counts',
   ({21: [22], 22: [21]}, {22: 1}, [21]),
   {'garbage': [], 'rc': {'21': 1, '22': 2}}),
  ('candidate sharing a child with a live object',
   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),
   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),
  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),
  ('object with two external references',
   ({28: [29], 29: []}, {28: 2}, [28]),
   {'garbage': [], 'rc': {'28': 2, '29': 1}}),
  ('control: acyclic live candidate',
   ({21: [22], 22: []}, {21: 1}, [21, 22]),
   {'garbage': [], 'rc': {'21': 1, '22': 1}})],
 [('regression: three-object garbage cycle',
   ({31: [32], 32: [33], 33: [31]}, {}, [31]),
   {'garbage': [31, 32, 33], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),
   {'garbage': [31, 32], 'rc': {'33': 1}}),
  ('externally held cycle restores its counts',
   ({31: [32], 32: [31]}, {32: 1}, [31]),
   {'garbage': [], 'rc': {'31': 1, '32': 2}}),
  ('candidate sharing a child with a live object',
   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),
   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),
  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),
  ('object with two external references',
   ({38: [39], 39: []}, {38: 2}, [38]),
   {'garbage': [], 'rc': {'38': 2, '39': 1}}),
  ('control: acyclic live candidate',
   ({31: [32], 32: []}, {31: 1}, [31, 32]),
   {'garbage': [], 'rc': {'31': 1, '32': 1}})],
 [('regression: three-object garbage cycle',
   ({41: [42], 42: [43], 43: [41]}, {}, [41]),
   {'garbage': [41, 42, 43], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),
   {'garbage': [41, 42], 'rc': {'43': 1}}),
  ('externally held cycle restores its counts',
   ({41: [42], 42: [41]}, {42: 1}, [41]),
   {'garbage': [], 'rc': {'41': 1, '42': 2}}),
  ('candidate sharing a child with a live object',
   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),
   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),
  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),
  ('object with two external references',
   ({48: [49], 49: []}, {48: 2}, [48]),
   {'garbage': [], 'rc': {'48': 2, '49': 1}}),
  ('control: acyclic live candidate',
   ({41: [42], 42: []}, {41: 1}, [41, 42]),
   {'garbage': [], 'rc': {'41': 1, '42': 1}})],
 [('regression: three-object garbage cycle',
   ({51: [52], 52: [53], 53: [51]}, {}, [51]),
   {'garbage': [51, 52, 53], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),
   {'garbage': [51, 52], 'rc': {'53': 1}}),
  ('externally held cycle restores its counts',
   ({51: [52], 52: [51]}, {52: 1}, [51]),
   {'garbage': [], 'rc': {'51': 1, '52': 2}}),
  ('candidate sharing a child with a live object',
   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),
   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),
  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),
  ('object with two external references',
   ({58: [59], 59: []}, {58: 2}, [58]),
   {'garbage': [], 'rc': {'58': 2, '59': 1}}),
  ('control: acyclic live candidate',
   ({51: [52], 52: []}, {51: 1}, [51, 52]),
   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]
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(heap, external, candidates):
    rc = {o: external.get(o, 0) for o in heap}
    for o, kids in heap.items():
        for c in kids:
            rc[c] += 1
    color = {o: 'black' for o in heap}
    def mark_gray(o):
        if color[o] != 'gray':
            color[o] = 'gray'
            for c in heap[o]:
                rc[c] -= 1 if c != o else 0
                mark_gray(c)
    def scan(o):
        if color[o] == 'gray':
            if rc[o] > 0:
                scan_black(o)
            else:
                color[o] = 'white'
                for c in heap[o]:
                    scan(c)
    def scan_black(o):
        color[o] = 'black'
        for c in heap[o]:
            rc[c] += 1
            if color[c] != 'black':
                scan_black(c)
    for o in candidates:
        mark_gray(o)
    for o in candidates:
        scan(o)
    garbage = sorted(o for o in heap if color[o] == 'white')
    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: three-object garbage cycle',
   ({11: [12], 12: [13], 13: [11]}, {}, [11]),
   {'garbage': [11, 12, 13], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),
   {'garbage': [11, 12], 'rc': {'13': 1}}),
  ('externally held cycle restores its counts',
   ({11: [12], 12: [11]}, {12: 1}, [11]),
   {'garbage': [], 'rc': {'11': 1, '12': 2}}),
  ('candidate sharing a child with a live object',
   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),
   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),
  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),
  ('object with two external references',
   ({18: [19], 19: []}, {18: 2}, [18]),
   {'garbage': [], 'rc': {'18': 2, '19': 1}}),
  ('control: acyclic live candidate',
   ({11: [12], 12: []}, {11: 1}, [11, 12]),
   {'garbage': [], 'rc': {'11': 1, '12': 1}})],
 [('regression: three-object garbage cycle',
   ({21: [22], 22: [23], 23: [21]}, {}, [21]),
   {'garbage': [21, 22, 23], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),
   {'garbage': [21, 22], 'rc': {'23': 1}}),
  ('externally held cycle restores its counts',
   ({21: [22], 22: [21]}, {22: 1}, [21]),
   {'garbage': [], 'rc': {'21': 1, '22': 2}}),
  ('candidate sharing a child with a live object',
   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),
   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),
  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),
  ('object with two external references',
   ({28: [29], 29: []}, {28: 2}, [28]),
   {'garbage': [], 'rc': {'28': 2, '29': 1}}),
  ('control: acyclic live candidate',
   ({21: [22], 22: []}, {21: 1}, [21, 22]),
   {'garbage': [], 'rc': {'21': 1, '22': 1}})],
 [('regression: three-object garbage cycle',
   ({31: [32], 32: [33], 33: [31]}, {}, [31]),
   {'garbage': [31, 32, 33], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),
   {'garbage': [31, 32], 'rc': {'33': 1}}),
  ('externally held cycle restores its counts',
   ({31: [32], 32: [31]}, {32: 1}, [31]),
   {'garbage': [], 'rc': {'31': 1, '32': 2}}),
  ('candidate sharing a child with a live object',
   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),
   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),
  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),
  ('object with two external references',
   ({38: [39], 39: []}, {38: 2}, [38]),
   {'garbage': [], 'rc': {'38': 2, '39': 1}}),
  ('control: acyclic live candidate',
   ({31: [32], 32: []}, {31: 1}, [31, 32]),
   {'garbage': [], 'rc': {'31': 1, '32': 1}})],
 [('regression: three-object garbage cycle',
   ({41: [42], 42: [43], 43: [41]}, {}, [41]),
   {'garbage': [41, 42, 43], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),
   {'garbage': [41, 42], 'rc': {'43': 1}}),
  ('externally held cycle restores its counts',
   ({41: [42], 42: [41]}, {42: 1}, [41]),
   {'garbage': [], 'rc': {'41': 1, '42': 2}}),
  ('candidate sharing a child with a live object',
   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),
   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),
  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),
  ('object with two external references',
   ({48: [49], 49: []}, {48: 2}, [48]),
   {'garbage': [], 'rc': {'48': 2, '49': 1}}),
  ('control: acyclic live candidate',
   ({41: [42], 42: []}, {41: 1}, [41, 42]),
   {'garbage': [], 'rc': {'41': 1, '42': 1}})],
 [('regression: three-object garbage cycle',
   ({51: [52], 52: [53], 53: [51]}, {}, [51]),
   {'garbage': [51, 52, 53], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),
   {'garbage': [51, 52], 'rc': {'53': 1}}),
  ('externally held cycle restores its counts',
   ({51: [52], 52: [51]}, {52: 1}, [51]),
   {'garbage': [], 'rc': {'51': 1, '52': 2}}),
  ('candidate sharing a child with a live object',
   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),
   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),
  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),
  ('object with two external references',
   ({58: [59], 59: []}, {58: 2}, [58]),
   {'garbage': [], 'rc': {'58': 2, '59': 1}}),
  ('control: acyclic live candidate',
   ({51: [52], 52: []}, {51: 1}, [51, 52]),
   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]
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:
Garbage cycles keep a phantom count from the edge that closes the cycle and are never collected.

Synchronous trial-deletion cycle collection. Reference counts are external references plus heap in-edges. For each candidate, mark gray: colour gray and, for every out-edge, decrement the child count and recurse. Then scan each candidate: a gray object with positive count is re-blackened together with everything it reaches, restoring one count per traversed edge; a gray object with zero count turns white and its children are scanned. White objects are garbage. Return the garbage and the counts of the surviving objects.

split: open-access


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

N = 1
observations = []
def solve(heap, external, candidates):
    rc = {o: external.get(o, 0) for o in heap}
    for o, kids in heap.items():
        for c in kids:
            rc[c] += 1
    color = {o: 'black' for o in heap}
    def mark_gray(o):
        if color[o] != 'gray':
            color[o] = 'gray'
            for c in heap[o]:
                rc[c] -= 1
                mark_gray(c)
    def scan(o):
        if color[o] == 'gray':
            if rc[o] > 0:
                scan_black(o)
            else:
                color[o] = 'white'
                for c in heap[o]:
                    scan(c)
    def scan_black(o):
        color[o] = 'black'
        for c in heap[o]:
            if color[c] != 'black':
                scan_black(c)
    for o in candidates:
        mark_gray(o)
    for o in candidates:
        scan(o)
    garbage = sorted(o for o in heap if color[o] == 'white')
    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: three-object garbage cycle',
   ({11: [12], 12: [13], 13: [11]}, {}, [11]),
   {'garbage': [11, 12, 13], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),
   {'garbage': [11, 12], 'rc': {'13': 1}}),
  ('externally held cycle restores its counts',
   ({11: [12], 12: [11]}, {12: 1}, [11]),
   {'garbage': [], 'rc': {'11': 1, '12': 2}}),
  ('candidate sharing a child with a live object',
   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),
   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),
  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),
  ('object with two external references',
   ({18: [19], 19: []}, {18: 2}, [18]),
   {'garbage': [], 'rc': {'18': 2, '19': 1}}),
  ('control: acyclic live candidate',
   ({11: [12], 12: []}, {11: 1}, [11, 12]),
   {'garbage': [], 'rc': {'11': 1, '12': 1}})],
 [('regression: three-object garbage cycle',
   ({21: [22], 22: [23], 23: [21]}, {}, [21]),
   {'garbage': [21, 22, 23], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),
   {'garbage': [21, 22], 'rc': {'23': 1}}),
  ('externally held cycle restores its counts',
   ({21: [22], 22: [21]}, {22: 1}, [21]),
   {'garbage': [], 'rc': {'21': 1, '22': 2}}),
  ('candidate sharing a child with a live object',
   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),
   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),
  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),
  ('object with two external references',
   ({28: [29], 29: []}, {28: 2}, [28]),
   {'garbage': [], 'rc': {'28': 2, '29': 1}}),
  ('control: acyclic live candidate',
   ({21: [22], 22: []}, {21: 1}, [21, 22]),
   {'garbage': [], 'rc': {'21': 1, '22': 1}})],
 [('regression: three-object garbage cycle',
   ({31: [32], 32: [33], 33: [31]}, {}, [31]),
   {'garbage': [31, 32, 33], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),
   {'garbage': [31, 32], 'rc': {'33': 1}}),
  ('externally held cycle restores its counts',
   ({31: [32], 32: [31]}, {32: 1}, [31]),
   {'garbage': [], 'rc': {'31': 1, '32': 2}}),
  ('candidate sharing a child with a live object',
   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),
   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),
  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),
  ('object with two external references',
   ({38: [39], 39: []}, {38: 2}, [38]),
   {'garbage': [], 'rc': {'38': 2, '39': 1}}),
  ('control: acyclic live candidate',
   ({31: [32], 32: []}, {31: 1}, [31, 32]),
   {'garbage': [], 'rc': {'31': 1, '32': 1}})],
 [('regression: three-object garbage cycle',
   ({41: [42], 42: [43], 43: [41]}, {}, [41]),
   {'garbage': [41, 42, 43], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),
   {'garbage': [41, 42], 'rc': {'43': 1}}),
  ('externally held cycle restores its counts',
   ({41: [42], 42: [41]}, {42: 1}, [41]),
   {'garbage': [], 'rc': {'41': 1, '42': 2}}),
  ('candidate sharing a child with a live object',
   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),
   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),
  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),
  ('object with two external references',
   ({48: [49], 49: []}, {48: 2}, [48]),
   {'garbage': [], 'rc': {'48': 2, '49': 1}}),
  ('control: acyclic live candidate',
   ({41: [42], 42: []}, {41: 1}, [41, 42]),
   {'garbage': [], 'rc': {'41': 1, '42': 1}})],
 [('regression: three-object garbage cycle',
   ({51: [52], 52: [53], 53: [51]}, {}, [51]),
   {'garbage': [51, 52, 53], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),
   {'garbage': [51, 52], 'rc': {'53': 1}}),
  ('externally held cycle restores its counts',
   ({51: [52], 52: [51]}, {52: 1}, [51]),
   {'garbage': [], 'rc': {'51': 1, '52': 2}}),
  ('candidate sharing a child with a live object',
   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),
   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),
  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),
  ('object with two external references',
   ({58: [59], 59: []}, {58: 2}, [58]),
   {'garbage': [], 'rc': {'58': 2, '59': 1}}),
  ('control: acyclic live candidate',
   ({51: [52], 52: []}, {51: 1}, [51, 52]),
   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]
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(heap, external, candidates):
    rc = {o: external.get(o, 0) for o in heap}
    for o, kids in heap.items():
        for c in kids:
            rc[c] += 1
    color = {o: 'black' for o in heap}
    def mark_gray(o):
        if color[o] != 'gray':
            color[o] = 'gray'
            for c in heap[o]:
                rc[c] -= 1
                mark_gray(c)
    def scan(o):
        if color[o] == 'gray':
            if rc[o] > 0:
                scan_black(o)
            else:
                color[o] = 'white'
                for c in heap[o]:
                    scan(c)
    def scan_black(o):
        color[o] = 'black'
        for c in heap[o]:
            if color[c] != 'black':
                rc[c] += 1
                scan_black(c)
    for o in candidates:
        mark_gray(o)
    for o in candidates:
        scan(o)
    garbage = sorted(o for o in heap if color[o] == 'white')
    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: three-object garbage cycle',
   ({11: [12], 12: [13], 13: [11]}, {}, [11]),
   {'garbage': [11, 12, 13], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),
   {'garbage': [11, 12], 'rc': {'13': 1}}),
  ('externally held cycle restores its counts',
   ({11: [12], 12: [11]}, {12: 1}, [11]),
   {'garbage': [], 'rc': {'11': 1, '12': 2}}),
  ('candidate sharing a child with a live object',
   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),
   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),
  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),
  ('object with two external references',
   ({18: [19], 19: []}, {18: 2}, [18]),
   {'garbage': [], 'rc': {'18': 2, '19': 1}}),
  ('control: acyclic live candidate',
   ({11: [12], 12: []}, {11: 1}, [11, 12]),
   {'garbage': [], 'rc': {'11': 1, '12': 1}})],
 [('regression: three-object garbage cycle',
   ({21: [22], 22: [23], 23: [21]}, {}, [21]),
   {'garbage': [21, 22, 23], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),
   {'garbage': [21, 22], 'rc': {'23': 1}}),
  ('externally held cycle restores its counts',
   ({21: [22], 22: [21]}, {22: 1}, [21]),
   {'garbage': [], 'rc': {'21': 1, '22': 2}}),
  ('candidate sharing a child with a live object',
   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),
   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),
  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),
  ('object with two external references',
   ({28: [29], 29: []}, {28: 2}, [28]),
   {'garbage': [], 'rc': {'28': 2, '29': 1}}),
  ('control: acyclic live candidate',
   ({21: [22], 22: []}, {21: 1}, [21, 22]),
   {'garbage': [], 'rc': {'21': 1, '22': 1}})],
 [('regression: three-object garbage cycle',
   ({31: [32], 32: [33], 33: [31]}, {}, [31]),
   {'garbage': [31, 32, 33], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),
   {'garbage': [31, 32], 'rc': {'33': 1}}),
  ('externally held cycle restores its counts',
   ({31: [32], 32: [31]}, {32: 1}, [31]),
   {'garbage': [], 'rc': {'31': 1, '32': 2}}),
  ('candidate sharing a child with a live object',
   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),
   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),
  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),
  ('object with two external references',
   ({38: [39], 39: []}, {38: 2}, [38]),
   {'garbage': [], 'rc': {'38': 2, '39': 1}}),
  ('control: acyclic live candidate',
   ({31: [32], 32: []}, {31: 1}, [31, 32]),
   {'garbage': [], 'rc': {'31': 1, '32': 1}})],
 [('regression: three-object garbage cycle',
   ({41: [42], 42: [43], 43: [41]}, {}, [41]),
   {'garbage': [41, 42, 43], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),
   {'garbage': [41, 42], 'rc': {'43': 1}}),
  ('externally held cycle restores its counts',
   ({41: [42], 42: [41]}, {42: 1}, [41]),
   {'garbage': [], 'rc': {'41': 1, '42': 2}}),
  ('candidate sharing a child with a live object',
   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),
   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),
  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),
  ('object with two external references',
   ({48: [49], 49: []}, {48: 2}, [48]),
   {'garbage': [], 'rc': {'48': 2, '49': 1}}),
  ('control: acyclic live candidate',
   ({41: [42], 42: []}, {41: 1}, [41, 42]),
   {'garbage': [], 'rc': {'41': 1, '42': 1}})],
 [('regression: three-object garbage cycle',
   ({51: [52], 52: [53], 53: [51]}, {}, [51]),
   {'garbage': [51, 52, 53], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),
   {'garbage': [51, 52], 'rc': {'53': 1}}),
  ('externally held cycle restores its counts',
   ({51: [52], 52: [51]}, {52: 1}, [51]),
   {'garbage': [], 'rc': {'51': 1, '52': 2}}),
  ('candidate sharing a child with a live object',
   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),
   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),
  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),
  ('object with two external references',
   ({58: [59], 59: []}, {58: 2}, [58]),
   {'garbage': [], 'rc': {'58': 2, '59': 1}}),
  ('control: acyclic live candidate',
   ({51: [52], 52: []}, {51: 1}, [51, 52]),
   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]
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 objects inspected by the collector come out with permanently lowered reference counts.

Synchronous trial-deletion cycle collection. Reference counts are external references plus heap in-edges. For each candidate, mark gray: colour gray and, for every out-edge, decrement the child count and recurse. Then scan each candidate: a gray object with positive count is re-blackened together with everything it reaches, restoring one count per traversed edge; a gray object with zero count turns white and its children are scanned. White objects are garbage. Return the garbage and the counts of the surviving objects.

split: open-access


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

N = 1
observations = []
def solve(heap, external, candidates):
    rc = {o: external.get(o, 0) for o in heap}
    for o, kids in heap.items():
        for c in kids:
            rc[c] += 1
    color = {o: 'black' for o in heap}
    def mark_gray(o):
        if color[o] != 'gray':
            color[o] = 'gray'
            for c in heap[o]:
                rc[c] -= 1
                mark_gray(c)
    def scan(o):
        if color[o] == 'gray':
            if external.get(o, 0) > 0:
                scan_black(o)
            else:
                color[o] = 'white'
                for c in heap[o]:
                    scan(c)
    def scan_black(o):
        color[o] = 'black'
        for c in heap[o]:
            rc[c] += 1
            if color[c] != 'black':
                scan_black(c)
    for o in candidates:
        mark_gray(o)
    for o in candidates:
        scan(o)
    garbage = sorted(o for o in heap if color[o] == 'white')
    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: three-object garbage cycle',
   ({11: [12], 12: [13], 13: [11]}, {}, [11]),
   {'garbage': [11, 12, 13], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),
   {'garbage': [11, 12], 'rc': {'13': 1}}),
  ('externally held cycle restores its counts',
   ({11: [12], 12: [11]}, {12: 1}, [11]),
   {'garbage': [], 'rc': {'11': 1, '12': 2}}),
  ('candidate sharing a child with a live object',
   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),
   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),
  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),
  ('object with two external references',
   ({18: [19], 19: []}, {18: 2}, [18]),
   {'garbage': [], 'rc': {'18': 2, '19': 1}}),
  ('control: acyclic live candidate',
   ({11: [12], 12: []}, {11: 1}, [11, 12]),
   {'garbage': [], 'rc': {'11': 1, '12': 1}})],
 [('regression: three-object garbage cycle',
   ({21: [22], 22: [23], 23: [21]}, {}, [21]),
   {'garbage': [21, 22, 23], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),
   {'garbage': [21, 22], 'rc': {'23': 1}}),
  ('externally held cycle restores its counts',
   ({21: [22], 22: [21]}, {22: 1}, [21]),
   {'garbage': [], 'rc': {'21': 1, '22': 2}}),
  ('candidate sharing a child with a live object',
   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),
   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),
  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),
  ('object with two external references',
   ({28: [29], 29: []}, {28: 2}, [28]),
   {'garbage': [], 'rc': {'28': 2, '29': 1}}),
  ('control: acyclic live candidate',
   ({21: [22], 22: []}, {21: 1}, [21, 22]),
   {'garbage': [], 'rc': {'21': 1, '22': 1}})],
 [('regression: three-object garbage cycle',
   ({31: [32], 32: [33], 33: [31]}, {}, [31]),
   {'garbage': [31, 32, 33], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),
   {'garbage': [31, 32], 'rc': {'33': 1}}),
  ('externally held cycle restores its counts',
   ({31: [32], 32: [31]}, {32: 1}, [31]),
   {'garbage': [], 'rc': {'31': 1, '32': 2}}),
  ('candidate sharing a child with a live object',
   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),
   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),
  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),
  ('object with two external references',
   ({38: [39], 39: []}, {38: 2}, [38]),
   {'garbage': [], 'rc': {'38': 2, '39': 1}}),
  ('control: acyclic live candidate',
   ({31: [32], 32: []}, {31: 1}, [31, 32]),
   {'garbage': [], 'rc': {'31': 1, '32': 1}})],
 [('regression: three-object garbage cycle',
   ({41: [42], 42: [43], 43: [41]}, {}, [41]),
   {'garbage': [41, 42, 43], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),
   {'garbage': [41, 42], 'rc': {'43': 1}}),
  ('externally held cycle restores its counts',
   ({41: [42], 42: [41]}, {42: 1}, [41]),
   {'garbage': [], 'rc': {'41': 1, '42': 2}}),
  ('candidate sharing a child with a live object',
   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),
   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),
  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),
  ('object with two external references',
   ({48: [49], 49: []}, {48: 2}, [48]),
   {'garbage': [], 'rc': {'48': 2, '49': 1}}),
  ('control: acyclic live candidate',
   ({41: [42], 42: []}, {41: 1}, [41, 42]),
   {'garbage': [], 'rc': {'41': 1, '42': 1}})],
 [('regression: three-object garbage cycle',
   ({51: [52], 52: [53], 53: [51]}, {}, [51]),
   {'garbage': [51, 52, 53], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),
   {'garbage': [51, 52], 'rc': {'53': 1}}),
  ('externally held cycle restores its counts',
   ({51: [52], 52: [51]}, {52: 1}, [51]),
   {'garbage': [], 'rc': {'51': 1, '52': 2}}),
  ('candidate sharing a child with a live object',
   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),
   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),
  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),
  ('object with two external references',
   ({58: [59], 59: []}, {58: 2}, [58]),
   {'garbage': [], 'rc': {'58': 2, '59': 1}}),
  ('control: acyclic live candidate',
   ({51: [52], 52: []}, {51: 1}, [51, 52]),
   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]
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(heap, external, candidates):
    rc = {o: external.get(o, 0) for o in heap}
    for o, kids in heap.items():
        for c in kids:
            rc[c] += 1
    color = {o: 'black' for o in heap}
    def mark_gray(o):
        if color[o] != 'gray':
            color[o] = 'gray'
            for c in heap[o]:
                rc[c] -= 1
                mark_gray(c)
    def scan(o):
        if color[o] == 'gray':
            if rc[o] > 0 and o in candidates:
                scan_black(o)
            else:
                color[o] = 'white'
                for c in heap[o]:
                    scan(c)
    def scan_black(o):
        color[o] = 'black'
        for c in heap[o]:
            rc[c] += 1
            if color[c] != 'black':
                scan_black(c)
    for o in candidates:
        mark_gray(o)
    for o in candidates:
        scan(o)
    garbage = sorted(o for o in heap if color[o] == 'white')
    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: three-object garbage cycle',
   ({11: [12], 12: [13], 13: [11]}, {}, [11]),
   {'garbage': [11, 12, 13], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),
   {'garbage': [11, 12], 'rc': {'13': 1}}),
  ('externally held cycle restores its counts',
   ({11: [12], 12: [11]}, {12: 1}, [11]),
   {'garbage': [], 'rc': {'11': 1, '12': 2}}),
  ('candidate sharing a child with a live object',
   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),
   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),
  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),
  ('object with two external references',
   ({18: [19], 19: []}, {18: 2}, [18]),
   {'garbage': [], 'rc': {'18': 2, '19': 1}}),
  ('control: acyclic live candidate',
   ({11: [12], 12: []}, {11: 1}, [11, 12]),
   {'garbage': [], 'rc': {'11': 1, '12': 1}})],
 [('regression: three-object garbage cycle',
   ({21: [22], 22: [23], 23: [21]}, {}, [21]),
   {'garbage': [21, 22, 23], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),
   {'garbage': [21, 22], 'rc': {'23': 1}}),
  ('externally held cycle restores its counts',
   ({21: [22], 22: [21]}, {22: 1}, [21]),
   {'garbage': [], 'rc': {'21': 1, '22': 2}}),
  ('candidate sharing a child with a live object',
   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),
   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),
  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),
  ('object with two external references',
   ({28: [29], 29: []}, {28: 2}, [28]),
   {'garbage': [], 'rc': {'28': 2, '29': 1}}),
  ('control: acyclic live candidate',
   ({21: [22], 22: []}, {21: 1}, [21, 22]),
   {'garbage': [], 'rc': {'21': 1, '22': 1}})],
 [('regression: three-object garbage cycle',
   ({31: [32], 32: [33], 33: [31]}, {}, [31]),
   {'garbage': [31, 32, 33], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),
   {'garbage': [31, 32], 'rc': {'33': 1}}),
  ('externally held cycle restores its counts',
   ({31: [32], 32: [31]}, {32: 1}, [31]),
   {'garbage': [], 'rc': {'31': 1, '32': 2}}),
  ('candidate sharing a child with a live object',
   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),
   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),
  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),
  ('object with two external references',
   ({38: [39], 39: []}, {38: 2}, [38]),
   {'garbage': [], 'rc': {'38': 2, '39': 1}}),
  ('control: acyclic live candidate',
   ({31: [32], 32: []}, {31: 1}, [31, 32]),
   {'garbage': [], 'rc': {'31': 1, '32': 1}})],
 [('regression: three-object garbage cycle',
   ({41: [42], 42: [43], 43: [41]}, {}, [41]),
   {'garbage': [41, 42, 43], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),
   {'garbage': [41, 42], 'rc': {'43': 1}}),
  ('externally held cycle restores its counts',
   ({41: [42], 42: [41]}, {42: 1}, [41]),
   {'garbage': [], 'rc': {'41': 1, '42': 2}}),
  ('candidate sharing a child with a live object',
   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),
   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),
  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),
  ('object with two external references',
   ({48: [49], 49: []}, {48: 2}, [48]),
   {'garbage': [], 'rc': {'48': 2, '49': 1}}),
  ('control: acyclic live candidate',
   ({41: [42], 42: []}, {41: 1}, [41, 42]),
   {'garbage': [], 'rc': {'41': 1, '42': 1}})],
 [('regression: three-object garbage cycle',
   ({51: [52], 52: [53], 53: [51]}, {}, [51]),
   {'garbage': [51, 52, 53], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),
   {'garbage': [51, 52], 'rc': {'53': 1}}),
  ('externally held cycle restores its counts',
   ({51: [52], 52: [51]}, {52: 1}, [51]),
   {'garbage': [], 'rc': {'51': 1, '52': 2}}),
  ('candidate sharing a child with a live object',
   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),
   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),
  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),
  ('object with two external references',
   ({58: [59], 59: []}, {58: 2}, [58]),
   {'garbage': [], 'rc': {'58': 2, '59': 1}}),
  ('control: acyclic live candidate',
   ({51: [52], 52: []}, {51: 1}, [51, 52]),
   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]
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:
Objects kept alive by references from outside the candidate subgraph are collected.

Synchronous trial-deletion cycle collection. Reference counts are external references plus heap in-edges. For each candidate, mark gray: colour gray and, for every out-edge, decrement the child count and recurse. Then scan each candidate: a gray object with positive count is re-blackened together with everything it reaches, restoring one count per traversed edge; a gray object with zero count turns white and its children are scanned. White objects are garbage. Return the garbage and the counts of the surviving objects.

split: open-access


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

N = 1
observations = []
def solve(heap, external, candidates):
    rc = {o: external.get(o, 0) for o in heap}
    for o, kids in heap.items():
        for c in kids:
            rc[c] += 1
    color = {o: 'black' for o in heap}
    def mark_gray(o):
        if color[o] != 'gray':
            color[o] = 'gray'
            for c in heap[o]:
                rc[c] -= 1
                mark_gray(c)
    def scan(o):
        if color[o] == 'gray':
            if rc[o] > 0:
                scan_black(o)
            else:
                color[o] = 'white'
                for c in heap[o]:
                    color[c] = 'white' if color[c] == 'gray' else color[c]
    def scan_black(o):
        color[o] = 'black'
        for c in heap[o]:
            rc[c] += 1
            if color[c] != 'black':
                scan_black(c)
    for o in candidates:
        mark_gray(o)
    for o in candidates:
        scan(o)
    garbage = sorted(o for o in heap if color[o] == 'white')
    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: three-object garbage cycle',
   ({11: [12], 12: [13], 13: [11]}, {}, [11]),
   {'garbage': [11, 12, 13], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),
   {'garbage': [11, 12], 'rc': {'13': 1}}),
  ('externally held cycle restores its counts',
   ({11: [12], 12: [11]}, {12: 1}, [11]),
   {'garbage': [], 'rc': {'11': 1, '12': 2}}),
  ('candidate sharing a child with a live object',
   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),
   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),
  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),
  ('object with two external references',
   ({18: [19], 19: []}, {18: 2}, [18]),
   {'garbage': [], 'rc': {'18': 2, '19': 1}}),
  ('control: acyclic live candidate',
   ({11: [12], 12: []}, {11: 1}, [11, 12]),
   {'garbage': [], 'rc': {'11': 1, '12': 1}})],
 [('regression: three-object garbage cycle',
   ({21: [22], 22: [23], 23: [21]}, {}, [21]),
   {'garbage': [21, 22, 23], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),
   {'garbage': [21, 22], 'rc': {'23': 1}}),
  ('externally held cycle restores its counts',
   ({21: [22], 22: [21]}, {22: 1}, [21]),
   {'garbage': [], 'rc': {'21': 1, '22': 2}}),
  ('candidate sharing a child with a live object',
   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),
   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),
  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),
  ('object with two external references',
   ({28: [29], 29: []}, {28: 2}, [28]),
   {'garbage': [], 'rc': {'28': 2, '29': 1}}),
  ('control: acyclic live candidate',
   ({21: [22], 22: []}, {21: 1}, [21, 22]),
   {'garbage': [], 'rc': {'21': 1, '22': 1}})],
 [('regression: three-object garbage cycle',
   ({31: [32], 32: [33], 33: [31]}, {}, [31]),
   {'garbage': [31, 32, 33], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),
   {'garbage': [31, 32], 'rc': {'33': 1}}),
  ('externally held cycle restores its counts',
   ({31: [32], 32: [31]}, {32: 1}, [31]),
   {'garbage': [], 'rc': {'31': 1, '32': 2}}),
  ('candidate sharing a child with a live object',
   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),
   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),
  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),
  ('object with two external references',
   ({38: [39], 39: []}, {38: 2}, [38]),
   {'garbage': [], 'rc': {'38': 2, '39': 1}}),
  ('control: acyclic live candidate',
   ({31: [32], 32: []}, {31: 1}, [31, 32]),
   {'garbage': [], 'rc': {'31': 1, '32': 1}})],
 [('regression: three-object garbage cycle',
   ({41: [42], 42: [43], 43: [41]}, {}, [41]),
   {'garbage': [41, 42, 43], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),
   {'garbage': [41, 42], 'rc': {'43': 1}}),
  ('externally held cycle restores its counts',
   ({41: [42], 42: [41]}, {42: 1}, [41]),
   {'garbage': [], 'rc': {'41': 1, '42': 2}}),
  ('candidate sharing a child with a live object',
   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),
   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),
  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),
  ('object with two external references',
   ({48: [49], 49: []}, {48: 2}, [48]),
   {'garbage': [], 'rc': {'48': 2, '49': 1}}),
  ('control: acyclic live candidate',
   ({41: [42], 42: []}, {41: 1}, [41, 42]),
   {'garbage': [], 'rc': {'41': 1, '42': 1}})],
 [('regression: three-object garbage cycle',
   ({51: [52], 52: [53], 53: [51]}, {}, [51]),
   {'garbage': [51, 52, 53], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),
   {'garbage': [51, 52], 'rc': {'53': 1}}),
  ('externally held cycle restores its counts',
   ({51: [52], 52: [51]}, {52: 1}, [51]),
   {'garbage': [], 'rc': {'51': 1, '52': 2}}),
  ('candidate sharing a child with a live object',
   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),
   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),
  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),
  ('object with two external references',
   ({58: [59], 59: []}, {58: 2}, [58]),
   {'garbage': [], 'rc': {'58': 2, '59': 1}}),
  ('control: acyclic live candidate',
   ({51: [52], 52: []}, {51: 1}, [51, 52]),
   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]
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(heap, external, candidates):
    rc = {o: external.get(o, 0) for o in heap}
    for o, kids in heap.items():
        for c in kids:
            rc[c] += 1
    color = {o: 'black' for o in heap}
    def mark_gray(o):
        if color[o] != 'gray':
            color[o] = 'gray'
            for c in heap[o]:
                rc[c] -= 1
                mark_gray(c)
    def scan(o):
        if color[o] == 'gray':
            if rc[o] > 0:
                scan_black(o)
            else:
                color[o] = 'white'
                for c in heap[o]:
                    if c in candidates:
                        scan(c)
    def scan_black(o):
        color[o] = 'black'
        for c in heap[o]:
            rc[c] += 1
            if color[c] != 'black':
                scan_black(c)
    for o in candidates:
        mark_gray(o)
    for o in candidates:
        scan(o)
    garbage = sorted(o for o in heap if color[o] == 'white')
    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: three-object garbage cycle',
   ({11: [12], 12: [13], 13: [11]}, {}, [11]),
   {'garbage': [11, 12, 13], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),
   {'garbage': [11, 12], 'rc': {'13': 1}}),
  ('externally held cycle restores its counts',
   ({11: [12], 12: [11]}, {12: 1}, [11]),
   {'garbage': [], 'rc': {'11': 1, '12': 2}}),
  ('candidate sharing a child with a live object',
   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),
   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),
  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),
  ('object with two external references',
   ({18: [19], 19: []}, {18: 2}, [18]),
   {'garbage': [], 'rc': {'18': 2, '19': 1}}),
  ('control: acyclic live candidate',
   ({11: [12], 12: []}, {11: 1}, [11, 12]),
   {'garbage': [], 'rc': {'11': 1, '12': 1}})],
 [('regression: three-object garbage cycle',
   ({21: [22], 22: [23], 23: [21]}, {}, [21]),
   {'garbage': [21, 22, 23], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),
   {'garbage': [21, 22], 'rc': {'23': 1}}),
  ('externally held cycle restores its counts',
   ({21: [22], 22: [21]}, {22: 1}, [21]),
   {'garbage': [], 'rc': {'21': 1, '22': 2}}),
  ('candidate sharing a child with a live object',
   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),
   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),
  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),
  ('object with two external references',
   ({28: [29], 29: []}, {28: 2}, [28]),
   {'garbage': [], 'rc': {'28': 2, '29': 1}}),
  ('control: acyclic live candidate',
   ({21: [22], 22: []}, {21: 1}, [21, 22]),
   {'garbage': [], 'rc': {'21': 1, '22': 1}})],
 [('regression: three-object garbage cycle',
   ({31: [32], 32: [33], 33: [31]}, {}, [31]),
   {'garbage': [31, 32, 33], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),
   {'garbage': [31, 32], 'rc': {'33': 1}}),
  ('externally held cycle restores its counts',
   ({31: [32], 32: [31]}, {32: 1}, [31]),
   {'garbage': [], 'rc': {'31': 1, '32': 2}}),
  ('candidate sharing a child with a live object',
   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),
   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),
  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),
  ('object with two external references',
   ({38: [39], 39: []}, {38: 2}, [38]),
   {'garbage': [], 'rc': {'38': 2, '39': 1}}),
  ('control: acyclic live candidate',
   ({31: [32], 32: []}, {31: 1}, [31, 32]),
   {'garbage': [], 'rc': {'31': 1, '32': 1}})],
 [('regression: three-object garbage cycle',
   ({41: [42], 42: [43], 43: [41]}, {}, [41]),
   {'garbage': [41, 42, 43], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),
   {'garbage': [41, 42], 'rc': {'43': 1}}),
  ('externally held cycle restores its counts',
   ({41: [42], 42: [41]}, {42: 1}, [41]),
   {'garbage': [], 'rc': {'41': 1, '42': 2}}),
  ('candidate sharing a child with a live object',
   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),
   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),
  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),
  ('object with two external references',
   ({48: [49], 49: []}, {48: 2}, [48]),
   {'garbage': [], 'rc': {'48': 2, '49': 1}}),
  ('control: acyclic live candidate',
   ({41: [42], 42: []}, {41: 1}, [41, 42]),
   {'garbage': [], 'rc': {'41': 1, '42': 1}})],
 [('regression: three-object garbage cycle',
   ({51: [52], 52: [53], 53: [51]}, {}, [51]),
   {'garbage': [51, 52, 53], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),
   {'garbage': [51, 52], 'rc': {'53': 1}}),
  ('externally held cycle restores its counts',
   ({51: [52], 52: [51]}, {52: 1}, [51]),
   {'garbage': [], 'rc': {'51': 1, '52': 2}}),
  ('candidate sharing a child with a live object',
   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),
   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),
  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),
  ('object with two external references',
   ({58: [59], 59: []}, {58: 2}, [58]),
   {'garbage': [], 'rc': {'58': 2, '59': 1}}),
  ('control: acyclic live candidate',
   ({51: [52], 52: []}, {51: 1}, [51, 52]),
   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]
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:
Cycle members beyond the first child stay gray and survive, while children with outside references are whitened.

Synchronous trial-deletion cycle collection. Reference counts are external references plus heap in-edges. For each candidate, mark gray: colour gray and, for every out-edge, decrement the child count and recurse. Then scan each candidate: a gray object with positive count is re-blackened together with everything it reaches, restoring one count per traversed edge; a gray object with zero count turns white and its children are scanned. White objects are garbage. Return the garbage and the counts of the surviving objects.

split: open-access


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

N = 1
observations = []
def solve(heap, external, candidates):
    rc = {o: 0 for o in heap}
    for o, kids in heap.items():
        for c in kids:
            rc[c] += 1
    color = {o: 'black' for o in heap}
    def mark_gray(o):
        if color[o] != 'gray':
            color[o] = 'gray'
            for c in heap[o]:
                rc[c] -= 1
                mark_gray(c)
    def scan(o):
        if color[o] == 'gray':
            if rc[o] > 0:
                scan_black(o)
            else:
                color[o] = 'white'
                for c in heap[o]:
                    scan(c)
    def scan_black(o):
        color[o] = 'black'
        for c in heap[o]:
            rc[c] += 1
            if color[c] != 'black':
                scan_black(c)
    for o in candidates:
        mark_gray(o)
    for o in candidates:
        scan(o)
    garbage = sorted(o for o in heap if color[o] == 'white')
    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: three-object garbage cycle',
   ({11: [12], 12: [13], 13: [11]}, {}, [11]),
   {'garbage': [11, 12, 13], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),
   {'garbage': [11, 12], 'rc': {'13': 1}}),
  ('externally held cycle restores its counts',
   ({11: [12], 12: [11]}, {12: 1}, [11]),
   {'garbage': [], 'rc': {'11': 1, '12': 2}}),
  ('candidate sharing a child with a live object',
   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),
   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),
  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),
  ('object with two external references',
   ({18: [19], 19: []}, {18: 2}, [18]),
   {'garbage': [], 'rc': {'18': 2, '19': 1}}),
  ('control: acyclic live candidate',
   ({11: [12], 12: []}, {11: 1}, [11, 12]),
   {'garbage': [], 'rc': {'11': 1, '12': 1}})],
 [('regression: three-object garbage cycle',
   ({21: [22], 22: [23], 23: [21]}, {}, [21]),
   {'garbage': [21, 22, 23], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),
   {'garbage': [21, 22], 'rc': {'23': 1}}),
  ('externally held cycle restores its counts',
   ({21: [22], 22: [21]}, {22: 1}, [21]),
   {'garbage': [], 'rc': {'21': 1, '22': 2}}),
  ('candidate sharing a child with a live object',
   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),
   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),
  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),
  ('object with two external references',
   ({28: [29], 29: []}, {28: 2}, [28]),
   {'garbage': [], 'rc': {'28': 2, '29': 1}}),
  ('control: acyclic live candidate',
   ({21: [22], 22: []}, {21: 1}, [21, 22]),
   {'garbage': [], 'rc': {'21': 1, '22': 1}})],
 [('regression: three-object garbage cycle',
   ({31: [32], 32: [33], 33: [31]}, {}, [31]),
   {'garbage': [31, 32, 33], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),
   {'garbage': [31, 32], 'rc': {'33': 1}}),
  ('externally held cycle restores its counts',
   ({31: [32], 32: [31]}, {32: 1}, [31]),
   {'garbage': [], 'rc': {'31': 1, '32': 2}}),
  ('candidate sharing a child with a live object',
   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),
   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),
  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),
  ('object with two external references',
   ({38: [39], 39: []}, {38: 2}, [38]),
   {'garbage': [], 'rc': {'38': 2, '39': 1}}),
  ('control: acyclic live candidate',
   ({31: [32], 32: []}, {31: 1}, [31, 32]),
   {'garbage': [], 'rc': {'31': 1, '32': 1}})],
 [('regression: three-object garbage cycle',
   ({41: [42], 42: [43], 43: [41]}, {}, [41]),
   {'garbage': [41, 42, 43], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),
   {'garbage': [41, 42], 'rc': {'43': 1}}),
  ('externally held cycle restores its counts',
   ({41: [42], 42: [41]}, {42: 1}, [41]),
   {'garbage': [], 'rc': {'41': 1, '42': 2}}),
  ('candidate sharing a child with a live object',
   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),
   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),
  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),
  ('object with two external references',
   ({48: [49], 49: []}, {48: 2}, [48]),
   {'garbage': [], 'rc': {'48': 2, '49': 1}}),
  ('control: acyclic live candidate',
   ({41: [42], 42: []}, {41: 1}, [41, 42]),
   {'garbage': [], 'rc': {'41': 1, '42': 1}})],
 [('regression: three-object garbage cycle',
   ({51: [52], 52: [53], 53: [51]}, {}, [51]),
   {'garbage': [51, 52, 53], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),
   {'garbage': [51, 52], 'rc': {'53': 1}}),
  ('externally held cycle restores its counts',
   ({51: [52], 52: [51]}, {52: 1}, [51]),
   {'garbage': [], 'rc': {'51': 1, '52': 2}}),
  ('candidate sharing a child with a live object',
   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),
   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),
  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),
  ('object with two external references',
   ({58: [59], 59: []}, {58: 2}, [58]),
   {'garbage': [], 'rc': {'58': 2, '59': 1}}),
  ('control: acyclic live candidate',
   ({51: [52], 52: []}, {51: 1}, [51, 52]),
   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]
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(heap, external, candidates):
    rc = {o: min(external.get(o, 0), 1) for o in heap}
    for o, kids in heap.items():
        for c in kids:
            rc[c] += 1
    color = {o: 'black' for o in heap}
    def mark_gray(o):
        if color[o] != 'gray':
            color[o] = 'gray'
            for c in heap[o]:
                rc[c] -= 1
                mark_gray(c)
    def scan(o):
        if color[o] == 'gray':
            if rc[o] > 0:
                scan_black(o)
            else:
                color[o] = 'white'
                for c in heap[o]:
                    scan(c)
    def scan_black(o):
        color[o] = 'black'
        for c in heap[o]:
            rc[c] += 1
            if color[c] != 'black':
                scan_black(c)
    for o in candidates:
        mark_gray(o)
    for o in candidates:
        scan(o)
    garbage = sorted(o for o in heap if color[o] == 'white')
    return {'garbage': garbage, 'rc': {str(o): rc[o] for o in sorted(heap) if color[o] != 'white'}}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: three-object garbage cycle',
   ({11: [12], 12: [13], 13: [11]}, {}, [11]),
   {'garbage': [11, 12, 13], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({11: [12], 12: [11, 13], 13: []}, {13: 1}, [11]),
   {'garbage': [11, 12], 'rc': {'13': 1}}),
  ('externally held cycle restores its counts',
   ({11: [12], 12: [11]}, {12: 1}, [11]),
   {'garbage': [], 'rc': {'11': 1, '12': 2}}),
  ('candidate sharing a child with a live object',
   ({15: [16], 16: [], 17: [16]}, {15: 1}, [17]),
   {'garbage': [17], 'rc': {'15': 1, '16': 1}}),
  ('self-referencing garbage', ({14: [14], 19: []}, {19: 1}, [14]), {'garbage': [14], 'rc': {'19': 1}}),
  ('object with two external references',
   ({18: [19], 19: []}, {18: 2}, [18]),
   {'garbage': [], 'rc': {'18': 2, '19': 1}}),
  ('control: acyclic live candidate',
   ({11: [12], 12: []}, {11: 1}, [11, 12]),
   {'garbage': [], 'rc': {'11': 1, '12': 1}})],
 [('regression: three-object garbage cycle',
   ({21: [22], 22: [23], 23: [21]}, {}, [21]),
   {'garbage': [21, 22, 23], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({21: [22], 22: [21, 23], 23: []}, {23: 1}, [21]),
   {'garbage': [21, 22], 'rc': {'23': 1}}),
  ('externally held cycle restores its counts',
   ({21: [22], 22: [21]}, {22: 1}, [21]),
   {'garbage': [], 'rc': {'21': 1, '22': 2}}),
  ('candidate sharing a child with a live object',
   ({25: [26], 26: [], 27: [26]}, {25: 1}, [27]),
   {'garbage': [27], 'rc': {'25': 1, '26': 1}}),
  ('self-referencing garbage', ({24: [24], 29: []}, {29: 1}, [24]), {'garbage': [24], 'rc': {'29': 1}}),
  ('object with two external references',
   ({28: [29], 29: []}, {28: 2}, [28]),
   {'garbage': [], 'rc': {'28': 2, '29': 1}}),
  ('control: acyclic live candidate',
   ({21: [22], 22: []}, {21: 1}, [21, 22]),
   {'garbage': [], 'rc': {'21': 1, '22': 1}})],
 [('regression: three-object garbage cycle',
   ({31: [32], 32: [33], 33: [31]}, {}, [31]),
   {'garbage': [31, 32, 33], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({31: [32], 32: [31, 33], 33: []}, {33: 1}, [31]),
   {'garbage': [31, 32], 'rc': {'33': 1}}),
  ('externally held cycle restores its counts',
   ({31: [32], 32: [31]}, {32: 1}, [31]),
   {'garbage': [], 'rc': {'31': 1, '32': 2}}),
  ('candidate sharing a child with a live object',
   ({35: [36], 36: [], 37: [36]}, {35: 1}, [37]),
   {'garbage': [37], 'rc': {'35': 1, '36': 1}}),
  ('self-referencing garbage', ({34: [34], 39: []}, {39: 1}, [34]), {'garbage': [34], 'rc': {'39': 1}}),
  ('object with two external references',
   ({38: [39], 39: []}, {38: 2}, [38]),
   {'garbage': [], 'rc': {'38': 2, '39': 1}}),
  ('control: acyclic live candidate',
   ({31: [32], 32: []}, {31: 1}, [31, 32]),
   {'garbage': [], 'rc': {'31': 1, '32': 1}})],
 [('regression: three-object garbage cycle',
   ({41: [42], 42: [43], 43: [41]}, {}, [41]),
   {'garbage': [41, 42, 43], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({41: [42], 42: [41, 43], 43: []}, {43: 1}, [41]),
   {'garbage': [41, 42], 'rc': {'43': 1}}),
  ('externally held cycle restores its counts',
   ({41: [42], 42: [41]}, {42: 1}, [41]),
   {'garbage': [], 'rc': {'41': 1, '42': 2}}),
  ('candidate sharing a child with a live object',
   ({45: [46], 46: [], 47: [46]}, {45: 1}, [47]),
   {'garbage': [47], 'rc': {'45': 1, '46': 1}}),
  ('self-referencing garbage', ({44: [44], 49: []}, {49: 1}, [44]), {'garbage': [44], 'rc': {'49': 1}}),
  ('object with two external references',
   ({48: [49], 49: []}, {48: 2}, [48]),
   {'garbage': [], 'rc': {'48': 2, '49': 1}}),
  ('control: acyclic live candidate',
   ({41: [42], 42: []}, {41: 1}, [41, 42]),
   {'garbage': [], 'rc': {'41': 1, '42': 1}})],
 [('regression: three-object garbage cycle',
   ({51: [52], 52: [53], 53: [51]}, {}, [51]),
   {'garbage': [51, 52, 53], 'rc': {}}),
  ('garbage cycle pointing at a live object',
   ({51: [52], 52: [51, 53], 53: []}, {53: 1}, [51]),
   {'garbage': [51, 52], 'rc': {'53': 1}}),
  ('externally held cycle restores its counts',
   ({51: [52], 52: [51]}, {52: 1}, [51]),
   {'garbage': [], 'rc': {'51': 1, '52': 2}}),
  ('candidate sharing a child with a live object',
   ({55: [56], 56: [], 57: [56]}, {55: 1}, [57]),
   {'garbage': [57], 'rc': {'55': 1, '56': 1}}),
  ('self-referencing garbage', ({54: [54], 59: []}, {59: 1}, [54]), {'garbage': [54], 'rc': {'59': 1}}),
  ('object with two external references',
   ({58: [59], 59: []}, {58: 2}, [58]),
   {'garbage': [], 'rc': {'58': 2, '59': 1}}),
  ('control: acyclic live candidate',
   ({51: [52], 52: []}, {51: 1}, [51, 52]),
   {'garbage': [], 'rc': {'51': 1, '52': 1}})]]
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:
Every candidate subgraph is collected, including ones held by the mutator.

Synchronous trial-deletion cycle collection. Reference counts are external references plus heap in-edges. For each candidate, mark gray: colour gray and, for every out-edge, decrement the child count and recurse. Then scan each candidate: a gray object with positive count is re-blackened together with everything it reaches, restoring one count per traversed edge; a gray object with zero count turns white and its children are scanned. White objects are garbage. Return the garbage and the counts of the surviving objects.

split: open-access