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

N = 1
observations = []
def solve(heap, roots, base, limit):
    forward = {}
    tospace = []
    free = base
    def copy(a):
        nonlocal free
        if a is None:
            return None
        if a in forward:
            return forward[a]
        need = (heap[a]['size'] + 7) // 8 * 8
        if free + need > limit:
            raise MemoryError()
        forward[a] = free
        tospace.append([free, a, list(heap[a]['fields'])])
        free += need
        return forward[a]
    try:
        new_roots = [copy(r) for r in roots]
        scan = 0
        while scan < len(tospace) - 1:
            entry = tospace[scan]
            entry[2] = [copy(f) for f in entry[2]]
            scan += 1
    except MemoryError:
        return ['out-of-memory', len(tospace)]
    return {'roots': new_roots, 'layout': tospace, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 8}},
    [1],
    0,
    500),
   {'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 16}},
    [1],
    0,
    500),
   {'free': 40, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 9}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 24}},
    [1],
    0,
    500),
   {'free': 48, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 32}},
    [1],
    0,
    500),
   {'free': 56, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 100, [1016, 1040]], [1016, 200, [1040]], [1040, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 200, [1024]], [1024, 300, [1032, None]], [1032, 100, [1000, 1024]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1072),
   {'free': 1072,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1048]],
               [1048, 300, [1056, None]],
               [1056, 100, [1024, 1048]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1071),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 40}},
    [1],
    0,
    500),
   {'free': 64, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [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(heap, roots, base, limit):
    forward = {}
    tospace = []
    free = base
    def copy(a):
        nonlocal free
        if a is None:
            return None
        if a in forward:
            return forward[a]
        need = (heap[a]['size'] + 7) // 8 * 8
        if free + need > limit:
            raise MemoryError()
        forward[a] = free
        tospace.append([free, a, list(heap[a]['fields'])])
        free += need
        return forward[a]
    try:
        new_roots = [copy(r) for r in roots]
        scan = 0
        for _ in range(len(tospace)):
            entry = tospace[scan]
            entry[2] = [copy(f) for f in entry[2]]
            scan += 1
    except MemoryError:
        return ['out-of-memory', len(tospace)]
    return {'roots': new_roots, 'layout': tospace, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 13},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 8}},
    [1],
    0,
    500),
   {'free': 32, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 14},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 16}},
    [1],
    0,
    500),
   {'free': 40, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 15},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 9}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 24}},
    [1],
    0,
    500),
   {'free': 48, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 100, [1016, 1032]], [1016, 200, [1032]], [1032, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 200, [1016]], [1016, 300, [1024, None]], [1024, 100, [1000, 1016]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1040,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1064),
   {'free': 1064,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1040]],
               [1040, 300, [1048, None]],
               [1048, 100, [1024, 1040]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 16},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1063),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 10}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 32}},
    [1],
    0,
    500),
   {'free': 56, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [0]})],
 [('regression: shared object and cycle copied once',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [100],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 100, [1016, 1040]], [1016, 200, [1040]], [1040, 300, [1000, None]]],
    'roots': [1000]}),
  ('odd sizes are rounded up to 8 bytes',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [200],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 200, [1024]], [1024, 300, [1032, None]], [1032, 100, [1000, 1024]]],
    'roots': [1000]}),
  ('two roots to the same object',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [300, 300, None],
    1000,
    2000),
   {'free': 1048,
    'layout': [[1000, 300, [1008, None]], [1008, 100, [1024, 1000]], [1024, 200, [1000]]],
    'roots': [1000, 1000, None]}),
  ('to-space exactly full',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1072),
   {'free': 1072,
    'layout': [[1000, 400, [1024]],
               [1024, 200, [1048]],
               [1048, 300, [1056, None]],
               [1056, 100, [1024, 1048]]],
    'roots': [1000]}),
  ('to-space one byte short',
   ({100: {'fields': [200, 300], 'size': 16},
     200: {'fields': [300], 'size': 17},
     300: {'fields': [100, None], 'size': 8},
     400: {'fields': [200], 'size': 24}},
    [400],
    1000,
    1071),
   ['out-of-memory', 3]),
  ('aligned size fits but raw size would too',
   ({1: {'fields': [], 'size': 11}}, [1], 0, 12),
   ['out-of-memory', 0]),
  ('last copied object is scanned',
   ({1: {'fields': [2], 'size': 8},
     2: {'fields': [3], 'size': 8},
     3: {'fields': [4], 'size': 8},
     4: {'fields': [], 'size': 40}},
    [1],
    0,
    500),
   {'free': 64, 'layout': [[0, 1, [8]], [8, 2, [16]], [16, 3, [24]], [24, 4, []]], 'roots': [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:
Fields of the most recently copied object keep pointing into from-space.

Breadth-first semispace copying. heap maps from-space address -> {size, fields}. Roots are copied in order, then a scan pointer walks to-space copying each referenced object exactly once (forwarding addresses are reused) and rewriting fields to to-space addresses. Copies are bump-allocated from base with sizes rounded up to 8 bytes; if a copy would end beyond limit, return ["out-of-memory", copies so far]. Return new roots, the to-space layout [new, old, fields] and the final free pointer.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, roots, base):
    starts = sorted(o[0] for o in objs)
    info = {o[0]: o for o in objs}
    def owner(p):
        i = bisect.bisect_right(starts, p) - 1
        if i < 0:
            raise KeyError(p)
        s = starts[i]
        if p >= s + info[s][1]:
            raise KeyError(p)
        return s
    try:
        live = set()
        stack = [r for r in roots if r is not None]
        while stack:
            s = owner(stack.pop())
            if s in live:
                continue
            live.add(s)
            stack.extend(f for f in info[s][2] if f is not None)
        fwd = {}
        top = base
        for s in starts:
            if s in live:
                fwd[s] = top
            top += info[s][1]
        def reloc(p):
            if p is None:
                return None
            s = owner(p)
            return fwd[s] + (p - s)
        layout = [[fwd[s], s, [reloc(f) for f in info[s][2]]] for s in starts if s in live]
        new_roots = [reloc(r) for r in roots]
    except KeyError as e:
        return ['dangling-pointer', e.args[0]]
    except IndexError:
        return ['heap-walk-error']
    return {'layout': layout, 'roots': new_roots, 'top': top}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    41),
   {'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]],
    'roots': [41, 81],
    'top': 109}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [152], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [104], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    42),
   {'layout': [[42, 100, [68, None]], [58, 124, [46]], [82, 148, [94]], [94, 160, []]],
    'roots': [42, 82],
    'top': 110}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [153], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [105], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    43),
   {'layout': [[43, 100, [70, None]], [59, 124, [47]], [83, 148, [95]], [95, 160, []]],
    'roots': [43, 83],
    'top': 111}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [150], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [102], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    44),
   {'layout': [[44, 100, [72, None]], [60, 124, [48]], [84, 148, [96]], [96, 160, []]],
    'roots': [44, 84],
    'top': 112}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    45),
   {'layout': [[45, 100, [74, None]], [61, 124, [49]], [85, 148, [97]], [97, 160, []]],
    'roots': [45, 85],
    'top': 113}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})]]
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
import bisect
N = 1
observations = []
def solve(objs, roots, base):
    starts = sorted(o[0] for o in objs)
    info = {o[0]: o for o in objs}
    def owner(p):
        i = bisect.bisect_right(starts, p) - 1
        if i < 0:
            raise KeyError(p)
        s = starts[i]
        if p >= s + info[s][1]:
            raise KeyError(p)
        return s
    try:
        live = set()
        stack = [r for r in roots if r is not None]
        while stack:
            s = owner(stack.pop())
            if s in live:
                continue
            live.add(s)
            stack.extend(f for f in info[s][2] if f is not None)
        fwd = {}
        top = base
        for s in starts:
            if s in live:
                fwd[s] = top
                top = s + info[s][1]
        def reloc(p):
            if p is None:
                return None
            s = owner(p)
            return fwd[s] + (p - s)
        layout = [[fwd[s], s, [reloc(f) for f in info[s][2]]] for s in starts if s in live]
        new_roots = [reloc(r) for r in roots]
    except KeyError as e:
        return ['dangling-pointer', e.args[0]]
    except IndexError:
        return ['heap-walk-error']
    return {'layout': layout, 'roots': new_roots, 'top': top}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    41),
   {'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]],
    'roots': [41, 81],
    'top': 109}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [152], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [104], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    42),
   {'layout': [[42, 100, [68, None]], [58, 124, [46]], [82, 148, [94]], [94, 160, []]],
    'roots': [42, 82],
    'top': 110}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [153], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [105], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    43),
   {'layout': [[43, 100, [70, None]], [59, 124, [47]], [83, 148, [95]], [95, 160, []]],
    'roots': [43, 83],
    'top': 111}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [150], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [102], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    44),
   {'layout': [[44, 100, [72, None]], [60, 124, [48]], [84, 148, [96]], [96, 160, []]],
    'roots': [44, 84],
    'top': 112}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    45),
   {'layout': [[45, 100, [74, None]], [61, 124, [49]], [85, 148, [97]], [97, 160, []]],
    'roots': [45, 85],
    'top': 113}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})]]
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 keep the gaps left by dead objects and the heap never shrinks.

Mark-compact with sliding. objs are [start, size, fields] in arbitrary order; pointers (fields and roots) may point anywhere inside an object and belong to the object whose [start, start+size) contains them; a pointer outside every object is ["dangling-pointer", p]. Mark from the roots, assign new addresses to live objects in address order starting at base with no gaps, and relocate every pointer to new start + original offset. Return the new layout [new, old, fields], new roots and the new top.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, roots, base):
    starts = sorted(o[0] for o in objs)
    info = {o[0]: o for o in objs}
    def owner(p):
        i = bisect.bisect_right(starts, p) - 1
        if i < 0:
            raise KeyError(p)
        s = starts[i]
        if p >= s + info[s][1]:
            raise KeyError(p)
        return s
    try:
        live = set()
        stack = [r for r in roots if r is not None]
        while stack:
            s = owner(stack.pop())
            if s in live:
                continue
            live.add(s)
            stack.extend(f for f in info[s][2] if f is not None)
        fwd = {}
        top = base
        for s in [o[0] for o in objs]:
            if s in live:
                fwd[s] = top
                top += info[s][1]
        def reloc(p):
            if p is None:
                return None
            s = owner(p)
            return fwd[s] + (p - s)
        layout = [[fwd[s], s, [reloc(f) for f in info[s][2]]] for s in starts if s in live]
        new_roots = [reloc(r) for r in roots]
    except KeyError as e:
        return ['dangling-pointer', e.args[0]]
    except IndexError:
        return ['heap-walk-error']
    return {'layout': layout, 'roots': new_roots, 'top': top}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    41),
   {'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]],
    'roots': [41, 81],
    'top': 109}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [152], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [104], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    42),
   {'layout': [[42, 100, [68, None]], [58, 124, [46]], [82, 148, [94]], [94, 160, []]],
    'roots': [42, 82],
    'top': 110}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [153], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [105], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    43),
   {'layout': [[43, 100, [70, None]], [59, 124, [47]], [83, 148, [95]], [95, 160, []]],
    'roots': [43, 83],
    'top': 111}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [150], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [102], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    44),
   {'layout': [[44, 100, [72, None]], [60, 124, [48]], [84, 148, [96]], [96, 160, []]],
    'roots': [44, 84],
    'top': 112}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    45),
   {'layout': [[45, 100, [74, None]], [61, 124, [49]], [85, 148, [97]], [97, 160, []]],
    'roots': [45, 85],
    'top': 113}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})]]
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
import bisect
N = 1
observations = []
def solve(objs, roots, base):
    starts = sorted(o[0] for o in objs)
    info = {o[0]: o for o in objs}
    def owner(p):
        i = bisect.bisect_right(starts, p) - 1
        if i < 0:
            raise KeyError(p)
        s = starts[i]
        if p >= s + info[s][1]:
            raise KeyError(p)
        return s
    try:
        live = set()
        stack = [r for r in roots if r is not None]
        while stack:
            s = owner(stack.pop())
            if s in live:
                continue
            live.add(s)
            stack.extend(f for f in info[s][2] if f is not None)
        fwd = {}
        top = base
        for s in sorted(starts, key=lambda s: -info[s][1]):
            if s in live:
                fwd[s] = top
                top += info[s][1]
        def reloc(p):
            if p is None:
                return None
            s = owner(p)
            return fwd[s] + (p - s)
        layout = [[fwd[s], s, [reloc(f) for f in info[s][2]]] for s in starts if s in live]
        new_roots = [reloc(r) for r in roots]
    except KeyError as e:
        return ['dangling-pointer', e.args[0]]
    except IndexError:
        return ['heap-walk-error']
    return {'layout': layout, 'roots': new_roots, 'top': top}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    41),
   {'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]],
    'roots': [41, 81],
    'top': 109}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [152], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [104], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    42),
   {'layout': [[42, 100, [68, None]], [58, 124, [46]], [82, 148, [94]], [94, 160, []]],
    'roots': [42, 82],
    'top': 110}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [153], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [105], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    43),
   {'layout': [[43, 100, [70, None]], [59, 124, [47]], [83, 148, [95]], [95, 160, []]],
    'roots': [43, 83],
    'top': 111}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [150], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [102], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    44),
   {'layout': [[44, 100, [72, None]], [60, 124, [48]], [84, 148, [96]], [96, 160, []]],
    'roots': [44, 84],
    'top': 112}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    45),
   {'layout': [[45, 100, [74, None]], [61, 124, [49]], [85, 148, [97]], [97, 160, []]],
    'roots': [45, 85],
    'top': 113}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})]]
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 are permuted instead of slid, so live objects can overtake each other.

Mark-compact with sliding. objs are [start, size, fields] in arbitrary order; pointers (fields and roots) may point anywhere inside an object and belong to the object whose [start, start+size) contains them; a pointer outside every object is ["dangling-pointer", p]. Mark from the roots, assign new addresses to live objects in address order starting at base with no gaps, and relocate every pointer to new start + original offset. Return the new layout [new, old, fields], new roots and the new top.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import bisect
N = 1
observations = []
def solve(objs, roots, base):
    starts = sorted(o[0] for o in objs)
    info = {o[0]: o for o in objs}
    def owner(p):
        i = bisect.bisect_right(starts, p) - 1
        if i < 0:
            raise KeyError(p)
        s = starts[i]
        if p >= s + info[s][1]:
            raise KeyError(p)
        return s
    try:
        live = set()
        stack = [r for r in roots if r is not None]
        while stack:
            s = owner(stack.pop())
            if s in live:
                continue
            live.add(s)
            stack.extend(f for f in info[s][2] if f is not None)
        fwd = {}
        top = base
        for s in starts:
            if s in live:
                fwd[s] = top
                top += info[s][1]
        def reloc(p):
            if p is None:
                return None
            s = owner(p)
            return fwd[s]
        layout = [[fwd[s], s, [reloc(f) for f in info[s][2]]] for s in starts if s in live]
        new_roots = [reloc(r) for r in roots]
    except KeyError as e:
        return ['dangling-pointer', e.args[0]]
    except IndexError:
        return ['heap-walk-error']
    return {'layout': layout, 'roots': new_roots, 'top': top}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    41),
   {'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]],
    'roots': [41, 81],
    'top': 109}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [152], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [104], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    42),
   {'layout': [[42, 100, [68, None]], [58, 124, [46]], [82, 148, [94]], [94, 160, []]],
    'roots': [42, 82],
    'top': 110}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [153], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [105], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    43),
   {'layout': [[43, 100, [70, None]], [59, 124, [47]], [83, 148, [95]], [95, 160, []]],
    'roots': [43, 83],
    'top': 111}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [150], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [102], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    44),
   {'layout': [[44, 100, [72, None]], [60, 124, [48]], [84, 148, [96]], [96, 160, []]],
    'roots': [44, 84],
    'top': 112}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    45),
   {'layout': [[45, 100, [74, None]], [61, 124, [49]], [85, 148, [97]], [97, 160, []]],
    'roots': [45, 85],
    'top': 113}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})]]
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
import bisect
N = 1
observations = []
def solve(objs, roots, base):
    starts = sorted(o[0] for o in objs)
    info = {o[0]: o for o in objs}
    def owner(p):
        i = bisect.bisect_right(starts, p) - 1
        if i < 0:
            raise KeyError(p)
        s = starts[i]
        if p >= s + info[s][1]:
            raise KeyError(p)
        return s
    try:
        live = set()
        stack = [r for r in roots if r is not None]
        while stack:
            s = owner(stack.pop())
            if s in live:
                continue
            live.add(s)
            stack.extend(f for f in info[s][2] if f is not None)
        fwd = {}
        top = base
        for s in starts:
            if s in live:
                fwd[s] = top
                top += info[s][1]
        def reloc(p):
            if p is None:
                return None
            s = owner(p)
            return fwd.get(p, p)
        layout = [[fwd[s], s, [reloc(f) for f in info[s][2]]] for s in starts if s in live]
        new_roots = [reloc(r) for r in roots]
    except KeyError as e:
        return ['dangling-pointer', e.args[0]]
    except IndexError:
        return ['heap-walk-error']
    return {'layout': layout, 'roots': new_roots, 'top': top}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [125, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    41),
   {'layout': [[41, 100, [66, None]], [57, 124, [45]], [81, 148, [93]], [93, 160, []]],
    'roots': [41, 81],
    'top': 109}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [133, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [126, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [152], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [104], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    42),
   {'layout': [[42, 100, [68, None]], [58, 124, [46]], [82, 148, [94]], [94, 160, []]],
    'roots': [42, 82],
    'top': 110}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [134, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [127, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [153], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [105], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    43),
   {'layout': [[43, 100, [70, None]], [59, 124, [47]], [83, 148, [95]], [95, 160, []]],
    'roots': [43, 83],
    'top': 111}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [135, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [128, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [150], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [102], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    44),
   {'layout': [[44, 100, [72, None]], [60, 124, [48]], [84, 148, [96]], [96, 160, []]],
    'roots': [44, 84],
    'top': 112}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [136, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})],
 [('regression: interior pointers relocate with their object',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [100], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [100], 'top': 140}),
  ('dead objects do not advance the compaction pointer',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [124], 100),
   {'layout': [[100, 100, [129, None]], [116, 124, [104]]], 'roots': [116], 'top': 140}),
  ('pointer to an object start',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [148, 160],
    100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [100, 112], 'top': 128}),
  ('interior root',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [151], 100),
   {'layout': [[100, 148, [112]], [112, 160, []]], 'roots': [103], 'top': 128}),
  ('compaction into a lower base',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]],
    [100, 148],
    45),
   {'layout': [[45, 100, [74, None]], [61, 124, [49]], [85, 148, [97]], [97, 160, []]],
    'roots': [45, 85],
    'top': 113}),
  ('control: no roots',
   ([[160, 16, []], [100, 16, [137, None]], [116, 8, []], [124, 24, [104]], [148, 12, [160]]], [None], 100),
   {'layout': [], 'roots': [None], 'top': 100})]]
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:
Pointers into the middle of objects are redirected to the object headers.

Mark-compact with sliding. objs are [start, size, fields] in arbitrary order; pointers (fields and roots) may point anywhere inside an object and belong to the object whose [start, start+size) contains them; a pointer outside every object is ["dangling-pointer", p]. Mark from the roots, assign new addresses to live objects in address order starting at base with no gaps, and relocate every pointer to new start + original offset. Return the new layout [new, old, fields], new roots and the new top.

split: open-access