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

N = 1
observations = []
def solve(objs, card, heap_end, queries):
    size_of = {s: z for s, z in objs}
    ncards = (heap_end + card - 1) // card
    table = [None] * ncards
    for start, size in sorted(objs):
        c = start // card
        if table[c] is None or table[c] < 0:
            table[c] = start - c * card
        last = (start + size - 1) // card
        for k in range(c + 1, min(last, ncards - 1) + 1):
            if table[k] is None:
                table[k] = -1
    def owner(q):
        c = q // card
        while c >= 0:
            e = table[c]
            if e is None:
                return None
            if e < 0:
                c += e
                continue
            a = c * card + e
            if a not in size_of:
                return 'corrupt-table'
            if a > q:
                c -= 1
                continue
            while a + size_of[a] <= q:
                a += size_of[a]
                if a not in size_of:
                    return None
            return a
        return None
    return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [47, 147, 167, 367, 391, 407]),
   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('first address of every card',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('object ends and starts',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [147, 148, 168, 391, 408]),
   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('smaller cards',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 264]], 64, 264, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [55, 155, 175, 375, 399, 415]),
   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('first address of every card',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('object ends and starts',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [155, 156, 176, 399, 416]),
   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('smaller cards',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
  ('control: single object heap',
   ([[0, 272]], 64, 272, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [63, 163, 183, 383, 407, 423]),
   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('first address of every card',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('object ends and starts',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [163, 164, 184, 407, 424]),
   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('smaller cards',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 280]], 64, 280, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [71, 171, 191, 391, 415, 431]),
   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('first address of every card',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('object ends and starts',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [171, 172, 192, 415, 432]),
   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('smaller cards',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
  ('control: single object heap',
   ([[0, 288]], 64, 288, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [79, 179, 199, 399, 423, 439]),
   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('first address of every card',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('object ends and starts',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [179, 180, 200, 423, 440]),
   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('smaller cards',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 296]], 64, 296, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(objs, card, heap_end, queries):
    size_of = {s: z for s, z in objs}
    ncards = (heap_end + card - 1) // card
    table = [None] * ncards
    for start, size in sorted(objs):
        c = start // card
        if table[c] is None or table[c] < 0:
            table[c] = start - c * card
        last = (start + size - 1) // card
        for k in range(c + 1, min(last, ncards - 1) + 1):
            if table[k] is None:
                table[k] = -(k - c - 1)
    def owner(q):
        c = q // card
        while c >= 0:
            e = table[c]
            if e is None:
                return None
            if e < 0:
                c += e
                continue
            a = c * card + e
            if a not in size_of:
                return 'corrupt-table'
            if a > q:
                c -= 1
                continue
            while a + size_of[a] <= q:
                a += size_of[a]
                if a not in size_of:
                    return None
            return a
        return None
    return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [47, 147, 167, 367, 391, 407]),
   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('first address of every card',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('object ends and starts',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [147, 148, 168, 391, 408]),
   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('smaller cards',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 264]], 64, 264, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [55, 155, 175, 375, 399, 415]),
   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('first address of every card',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('object ends and starts',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [155, 156, 176, 399, 416]),
   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('smaller cards',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
  ('control: single object heap',
   ([[0, 272]], 64, 272, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [63, 163, 183, 383, 407, 423]),
   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('first address of every card',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('object ends and starts',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [163, 164, 184, 407, 424]),
   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('smaller cards',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 280]], 64, 280, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [71, 171, 191, 391, 415, 431]),
   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('first address of every card',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('object ends and starts',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [171, 172, 192, 415, 432]),
   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('smaller cards',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
  ('control: single object heap',
   ([[0, 288]], 64, 288, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [79, 179, 199, 399, 423, 439]),
   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('first address of every card',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('object ends and starts',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [179, 180, 200, 423, 440]),
   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('smaller cards',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 296]], 64, 296, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
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:
Lookups deep inside large objects take one hop per card and the table encoding differs from the contract.

A contiguous heap of [start, size] objects is covered by cards of the given size. For each card the table stores the offset of the first object that starts inside the card; a card with no object start that is covered by an object from card c stores -(k - c), a direct back-skip to that card. To find the object containing address q: from q's card follow back-skips; if the card's first start lies after q, move to the previous card; then walk objects forward until one contains q (an entry that does not land on an object start yields corrupt-table). Return the table and the owner start for each query.

split: open-access


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

N = 1
observations = []
def solve(objs, card, heap_end, queries):
    size_of = {s: z for s, z in objs}
    ncards = (heap_end + card - 1) // card
    table = [None] * ncards
    for start, size in sorted(objs):
        c = start // card
        if table[c] is None or table[c] < 0:
            table[c] = start - c * card
        last = (start + size - 1) // card
        for k in range(c + 1, min(last, ncards - 1) + 1):
            if table[k] is None:
                table[k] = -(k - c)
    def owner(q):
        c = q // card
        while c >= 0:
            e = table[c]
            if e is None:
                return None
            if e < 0:
                c += e
                continue
            a = c * card + e
            if a not in size_of:
                return 'corrupt-table'
            if a > q:
                return a
            while a + size_of[a] <= q:
                a += size_of[a]
                if a not in size_of:
                    return None
            return a
        return None
    return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [47, 147, 167, 367, 391, 407]),
   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('first address of every card',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('object ends and starts',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [147, 148, 168, 391, 408]),
   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('smaller cards',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 264]], 64, 264, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [55, 155, 175, 375, 399, 415]),
   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('first address of every card',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('object ends and starts',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [155, 156, 176, 399, 416]),
   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('smaller cards',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
  ('control: single object heap',
   ([[0, 272]], 64, 272, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [63, 163, 183, 383, 407, 423]),
   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('first address of every card',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('object ends and starts',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [163, 164, 184, 407, 424]),
   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('smaller cards',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 280]], 64, 280, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [71, 171, 191, 391, 415, 431]),
   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('first address of every card',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('object ends and starts',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [171, 172, 192, 415, 432]),
   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('smaller cards',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
  ('control: single object heap',
   ([[0, 288]], 64, 288, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [79, 179, 199, 399, 423, 439]),
   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('first address of every card',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('object ends and starts',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [179, 180, 200, 423, 440]),
   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('smaller cards',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 296]], 64, 296, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

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

N = 1
observations = []
def solve(objs, card, heap_end, queries):
    size_of = {s: z for s, z in objs}
    ncards = (heap_end + card - 1) // card
    table = [None] * ncards
    for start, size in sorted(objs):
        c = start // card
        if table[c] is None or table[c] < 0:
            table[c] = start - c * card
        last = (start + size - 1) // card
        for k in range(c + 1, min(last, ncards - 1) + 1):
            if table[k] is None:
                table[k] = -(k - c)
    def owner(q):
        c = q // card
        while c >= 0:
            e = table[c]
            if e is None:
                return None
            if e < 0:
                c += e
                continue
            a = c * card + e
            if a not in size_of:
                return 'corrupt-table'
            if a > q:
                return None
            while a + size_of[a] <= q:
                a += size_of[a]
                if a not in size_of:
                    return None
            return a
        return None
    return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [47, 147, 167, 367, 391, 407]),
   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('first address of every card',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('object ends and starts',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [147, 148, 168, 391, 408]),
   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('smaller cards',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 264]], 64, 264, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [55, 155, 175, 375, 399, 415]),
   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('first address of every card',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('object ends and starts',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [155, 156, 176, 399, 416]),
   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('smaller cards',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
  ('control: single object heap',
   ([[0, 272]], 64, 272, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [63, 163, 183, 383, 407, 423]),
   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('first address of every card',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('object ends and starts',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [163, 164, 184, 407, 424]),
   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('smaller cards',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 280]], 64, 280, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [71, 171, 191, 391, 415, 431]),
   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('first address of every card',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('object ends and starts',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [171, 172, 192, 415, 432]),
   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('smaller cards',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
  ('control: single object heap',
   ([[0, 288]], 64, 288, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [79, 179, 199, 399, 423, 439]),
   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('first address of every card',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('object ends and starts',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [179, 180, 200, 423, 440]),
   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('smaller cards',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 296]], 64, 296, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
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:
Addresses at the beginning of a card are attributed to the next object.

A contiguous heap of [start, size] objects is covered by cards of the given size. For each card the table stores the offset of the first object that starts inside the card; a card with no object start that is covered by an object from card c stores -(k - c), a direct back-skip to that card. To find the object containing address q: from q's card follow back-skips; if the card's first start lies after q, move to the previous card; then walk objects forward until one contains q (an entry that does not land on an object start yields corrupt-table). Return the table and the owner start for each query.

split: open-access


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

N = 1
observations = []
def solve(objs, card, heap_end, queries):
    size_of = {s: z for s, z in objs}
    ncards = (heap_end + card - 1) // card
    table = [None] * ncards
    for start, size in sorted(objs):
        c = start // card
        if table[c] is None or table[c] < 0:
            table[c] = start - c * card
        last = (start + size - 1) // card
        for k in range(c + 1, min(last, ncards - 1) + 1):
            if table[k] is None:
                table[k] = -(k - c)
    def owner(q):
        c = q // card
        while c >= 0:
            e = table[c]
            if e is None:
                return None
            if e < 0:
                c += e
                continue
            a = c * card + e
            if a not in size_of:
                return 'corrupt-table'
            if a > q:
                c -= 1
                continue
            while a + size_of[a] < q:
                a += size_of[a]
                if a not in size_of:
                    return None
            return a
        return None
    return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [47, 147, 167, 367, 391, 407]),
   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('first address of every card',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('object ends and starts',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [147, 148, 168, 391, 408]),
   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('smaller cards',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 264]], 64, 264, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [55, 155, 175, 375, 399, 415]),
   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('first address of every card',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('object ends and starts',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [155, 156, 176, 399, 416]),
   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('smaller cards',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
  ('control: single object heap',
   ([[0, 272]], 64, 272, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [63, 163, 183, 383, 407, 423]),
   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('first address of every card',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('object ends and starts',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [163, 164, 184, 407, 424]),
   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('smaller cards',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 280]], 64, 280, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [71, 171, 191, 391, 415, 431]),
   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('first address of every card',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('object ends and starts',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [171, 172, 192, 415, 432]),
   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('smaller cards',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
  ('control: single object heap',
   ([[0, 288]], 64, 288, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [79, 179, 199, 399, 423, 439]),
   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('first address of every card',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('object ends and starts',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [179, 180, 200, 423, 440]),
   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('smaller cards',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 296]], 64, 296, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
for label, args, expected in cases[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

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

N = 1
observations = []
def solve(objs, card, heap_end, queries):
    size_of = {s: z for s, z in objs}
    ncards = (heap_end + card - 1) // card
    table = [None] * ncards
    for start, size in sorted(objs):
        c = start // card
        if table[c] is None or table[c] < 0:
            table[c] = start - c * card
        last = (start + size - 1) // card
        for k in range(c + 1, min(last, ncards - 1) + 1):
            if table[k] is None:
                table[k] = -(k - c)
    def owner(q):
        c = q // card
        while c >= 0:
            e = table[c]
            if e is None:
                return None
            if e < 0:
                c += e
                continue
            a = c * card + e
            if a not in size_of:
                return 'corrupt-table'
            if a > q:
                c -= 1
                continue
            while a < q:
                a += size_of[a]
                if a not in size_of:
                    return None
            return a
        return None
    return {'table': table, 'owners': [owner(q) for q in queries]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: owners across spanning objects',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 64, 472, [53, 318, 368]),
   {'owners': [48, 168, 368], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [47, 147, 167, 367, 391, 407]),
   {'owners': [0, 48, 148, 168, 368, 392], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('first address of every card',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 48, 48, 168, 168, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('object ends and starts',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]],
    64,
    472,
    [147, 148, 168, 391, 408]),
   {'owners': [48, 148, 168, 368, 408], 'table': [0, -1, 20, -1, -2, 48, 8, -1]}),
  ('smaller cards',
   ([[0, 48], [48, 100], [148, 20], [168, 200], [368, 24], [392, 16], [408, 64]], 32, 472, [238, 411, 5]),
   {'owners': [168, 408, 0], 'table': [0, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 264]], 64, 264, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 64, 480, [61, 326, 376]),
   {'owners': [56, 176, 376], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [55, 155, 175, 375, 399, 415]),
   {'owners': [0, 56, 156, 176, 376, 400], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('first address of every card',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 56, 56, 176, 176, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('object ends and starts',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]],
    64,
    480,
    [155, 156, 176, 399, 416]),
   {'owners': [56, 156, 176, 376, 416], 'table': [0, -1, 28, -1, -2, 56, 16, -1]}),
  ('smaller cards',
   ([[0, 56], [56, 100], [156, 20], [176, 200], [376, 24], [400, 16], [416, 64]], 32, 480, [246, 419, 5]),
   {'owners': [176, 416, 0], 'table': [0, 24, -1, -2, 28, 16, -1, -2, -3, -4, -5, 24, 16, 0, -1]}),
  ('control: single object heap',
   ([[0, 272]], 64, 272, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 64, 488, [69, 334, 384]),
   {'owners': [64, 184, 384], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [63, 163, 183, 383, 407, 423]),
   {'owners': [0, 64, 164, 184, 384, 408], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('first address of every card',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 64, 64, 184, 184, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('object ends and starts',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]],
    64,
    488,
    [163, 164, 184, 407, 424]),
   {'owners': [64, 164, 184, 384, 424], 'table': [0, 0, 36, -1, -2, -3, 0, -1]}),
  ('smaller cards',
   ([[0, 64], [64, 100], [164, 20], [184, 200], [384, 24], [408, 16], [424, 64]], 32, 488, [254, 427, 5]),
   {'owners': [184, 424, 0], 'table': [0, -1, 0, -1, -2, 4, -1, -2, -3, -4, -5, -6, 0, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 280]], 64, 280, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 64, 496, [77, 342, 392]),
   {'owners': [72, 192, 392], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [71, 171, 191, 391, 415, 431]),
   {'owners': [0, 72, 172, 192, 392, 416], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('first address of every card',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 72, 192, 192, 192, 192, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('object ends and starts',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]],
    64,
    496,
    [171, 172, 192, 415, 432]),
   {'owners': [72, 172, 192, 392, 432], 'table': [0, 8, 44, 0, -1, -2, 8, -1]}),
  ('smaller cards',
   ([[0, 72], [72, 100], [172, 20], [192, 200], [392, 24], [416, 16], [432, 64]], 32, 496, [262, 435, 5]),
   {'owners': [192, 432, 0], 'table': [0, -1, 8, -1, -2, 12, 0, -1, -2, -3, -4, -5, 8, 0, -1, -2]}),
  ('control: single object heap',
   ([[0, 288]], 64, 288, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})],
 [('regression: owners across spanning objects',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 64, 504, [85, 350, 400]),
   {'owners': [80, 200, 400], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('addresses just before a card-internal start',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [79, 179, 199, 399, 423, 439]),
   {'owners': [0, 80, 180, 200, 400, 424], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('first address of every card',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [0, 64, 128, 192, 256, 320, 384, 448]),
   {'owners': [0, 0, 80, 180, 200, 200, 200, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('object ends and starts',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]],
    64,
    504,
    [179, 180, 200, 423, 440]),
   {'owners': [80, 180, 200, 400, 440], 'table': [0, 16, 52, 8, -1, -2, 16, -1]}),
  ('smaller cards',
   ([[0, 80], [80, 100], [180, 20], [200, 200], [400, 24], [424, 16], [440, 64]], 32, 504, [270, 443, 5]),
   {'owners': [200, 440, 0], 'table': [0, -1, 16, -1, -2, 20, 8, -1, -2, -3, -4, -5, 16, 8, -1, -2]}),
  ('control: single object heap',
   ([[0, 296]], 64, 296, [0, 100, 255]),
   {'owners': [0, 0, 0], 'table': [0, -1, -2, -3, -4]})]]
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:
The first byte of an object is reported as belonging to its predecessor.

A contiguous heap of [start, size] objects is covered by cards of the given size. For each card the table stores the offset of the first object that starts inside the card; a card with no object start that is covered by an object from card c stores -(k - c), a direct back-skip to that card. To find the object containing address q: from q's card follow back-skips; if the card's first start lies after q, move to the previous card; then walk objects forward until one contains q (an entry that does not land on an object start yields corrupt-table). Return the table and the owner start for each query.

split: open-access


prompt:
After a second move the hash changes and the object grows another 8 bytes.

objs maps id -> [address, size]. The identity hash of an object is (address >> 3) & 0xFFFF of the address at which it was first hashed. Objects start unhashed; hash marks them hashed and returns the hash computed from the current address while they have not moved. The first move of a hashed object stores that hash in a new 8-byte trailing slot (size grows by 8) and later moves keep it; moving an unhashed object stores nothing. Return all hashes and the final [address, size] layout.

split: open-access


prompt:
The hash observed before a move differs from the one observed after it.

objs maps id -> [address, size]. The identity hash of an object is (address >> 3) & 0xFFFF of the address at which it was first hashed. Objects start unhashed; hash marks them hashed and returns the hash computed from the current address while they have not moved. The first move of a hashed object stores that hash in a new 8-byte trailing slot (size grows by 8) and later moves keep it; moving an unhashed object stores nothing. Return all hashes and the final [address, size] layout.

split: open-access


prompt:
hashCode changes after every collection that moves the object.

objs maps id -> [address, size]. The identity hash of an object is (address >> 3) & 0xFFFF of the address at which it was first hashed. Objects start unhashed; hash marks them hashed and returns the hash computed from the current address while they have not moved. The first move of a hashed object stores that hash in a new 8-byte trailing slot (size grows by 8) and later moves keep it; moving an unhashed object stores nothing. Return all hashes and the final [address, size] layout.

split: open-access


prompt:
Hashes of unmoved objects disagree with the value later stored on move.

objs maps id -> [address, size]. The identity hash of an object is (address >> 3) & 0xFFFF of the address at which it was first hashed. Objects start unhashed; hash marks them hashed and returns the hash computed from the current address while they have not moved. The first move of a hashed object stores that hash in a new 8-byte trailing slot (size grows by 8) and later moves keep it; moving an unhashed object stores nothing. Return all hashes and the final [address, size] layout.

split: open-access


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

N = 1
observations = []
def solve(kinds, region_size, card, writes):
    remsets = {}
    for slot, val in writes:
        if val is None:
            continue
        src, dst = slot // region_size, val // region_size
        while kinds[dst] == 'hcont':
            dst -= 1
        if slot // card == val // card:
            continue
        if kinds[src] == 'young':
            continue
        remsets.setdefault(dst, set()).add(slot // card)
    return {str(k): sorted(v) for k, v in sorted(remsets.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 1040], [2056, 6152], [6452, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2056, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1040], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1032, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 1040], [2064, 6152], [6460, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2064, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1048], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1040, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 1040], [2072, 6152], [6468, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2072, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1056], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1048, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 1040], [2080, 6152], [6476, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2080, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1064], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1056, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 1040], [2088, 6152], [6484, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2088, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1072], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1064, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, None], [6144, None], [2112, 3072]]),
   {'3': [16]})]]
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(kinds, region_size, card, writes):
    remsets = {}
    for slot, val in writes:
        if val is None:
            continue
        src, dst = slot // region_size, val // region_size
        while kinds[dst] == 'hcont':
            dst -= 1
        if abs(slot - val) < region_size:
            continue
        if kinds[src] == 'young':
            continue
        remsets.setdefault(dst, set()).add(slot // card)
    return {str(k): sorted(v) for k, v in sorted(remsets.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 1040], [2056, 6152], [6452, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2056, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1040], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1032, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 1040], [2064, 6152], [6460, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2064, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1048], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1040, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 1040], [2072, 6152], [6468, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2072, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1056], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1048, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 1040], [2080, 6152], [6476, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2080, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1064], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1056, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 1040], [2088, 6152], [6484, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2088, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1072], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1064, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, None], [6144, None], [2112, 3072]]),
   {'3': [16]})]]
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:
Remembered sets fill with pointers that never cross a region boundary.

Region-based remembered sets. kinds[r] is young, old, humongous or hcont (a continuation region of the humongous object that starts in the nearest preceding humongous region). For each write [slot, value]: null values are ignored; the target region is the region of value, mapped from continuations back to the humongous start; writes within one region and writes whose slot is in a young region are filtered; otherwise the slot's card index (slot // card) is added to the target region's set. Return the remembered sets.

split: open-access


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

N = 1
observations = []
def solve(kinds, region_size, card, writes):
    remsets = {}
    for slot, val in writes:
        if val is None:
            continue
        src, dst = slot // region_size, val // region_size
        while kinds[dst] == 'hcont':
            dst -= 1
        if src == dst:
            continue
        if kinds[dst] == 'young':
            continue
        remsets.setdefault(dst, set()).add(slot // card)
    return {str(k): sorted(v) for k, v in sorted(remsets.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 1040], [2056, 6152], [6452, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2056, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1040], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1032, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 1040], [2064, 6152], [6460, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2064, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1048], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1040, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 1040], [2072, 6152], [6468, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2072, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1056], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1048, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 1040], [2080, 6152], [6476, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2080, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1064], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1056, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 1040], [2088, 6152], [6484, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2088, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1072], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1064, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, None], [6144, None], [2112, 3072]]),
   {'3': [16]})]]
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(kinds, region_size, card, writes):
    remsets = {}
    for slot, val in writes:
        if val is None:
            continue
        src, dst = slot // region_size, val // region_size
        while kinds[dst] == 'hcont':
            dst -= 1
        if src == dst:
            continue
        if 'young' in (kinds[src], kinds[dst]):
            continue
        remsets.setdefault(dst, set()).add(slot // card)
    return {str(k): sorted(v) for k, v in sorted(remsets.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 1040], [2056, 6152], [6452, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2056, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1040], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1032, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 1040], [2064, 6152], [6460, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2064, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1048], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1040, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 1040], [2072, 6152], [6468, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2072, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1056], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1048, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 1040], [2080, 6152], [6476, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2080, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1064], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1056, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 1040], [2088, 6152], [6484, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2088, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1072], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1064, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, None], [6144, None], [2112, 3072]]),
   {'3': [16]})]]
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:
Old-to-young references are missing and young evacuation loses live objects.

Region-based remembered sets. kinds[r] is young, old, humongous or hcont (a continuation region of the humongous object that starts in the nearest preceding humongous region). For each write [slot, value]: null values are ignored; the target region is the region of value, mapped from continuations back to the humongous start; writes within one region and writes whose slot is in a young region are filtered; otherwise the slot's card index (slot // card) is added to the target region's set. Return the remembered sets.

split: open-access


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

N = 1
observations = []
def solve(kinds, region_size, card, writes):
    remsets = {}
    for slot, val in writes:
        if val is None:
            continue
        src, dst = slot // region_size, val // region_size
        while kinds[dst] == 'hcont':
            dst -= 1
        if src == dst:
            continue
        if kinds[src] == 'young':
            continue
        remsets.setdefault(dst, set()).add(val // card)
    return {str(k): sorted(v) for k, v in sorted(remsets.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 1040], [2056, 6152], [6452, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2056, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1040], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1032, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 1040], [2064, 6152], [6460, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2064, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1048], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1040, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 1040], [2072, 6152], [6468, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2072, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1056], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1048, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 1040], [2080, 6152], [6476, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2080, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1064], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1056, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 1040], [2088, 6152], [6484, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2088, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1072], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1064, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, None], [6144, None], [2112, 3072]]),
   {'3': [16]})]]
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(kinds, region_size, card, writes):
    remsets = {}
    for slot, val in writes:
        if val is None:
            continue
        src, dst = slot // region_size, val // region_size
        while kinds[dst] == 'hcont':
            dst -= 1
        if src == dst:
            continue
        if kinds[src] == 'young':
            continue
        remsets.setdefault(dst, set()).add(slot // region_size)
    return {str(k): sorted(v) for k, v in sorted(remsets.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 1040], [2056, 6152], [6452, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2056, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1040], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1032, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 1040], [2064, 6152], [6460, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2064, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1048], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1040, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 1040], [2072, 6152], [6468, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2072, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1056], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1048, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 1040], [2080, 6152], [6476, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2080, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1064], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1056, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 1040], [2088, 6152], [6484, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2088, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1072], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1064, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, None], [6144, None], [2112, 3072]]),
   {'3': [16]})]]
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:
Evacuation rescans cards in the target region, which do not contain the referencing slot.

Region-based remembered sets. kinds[r] is young, old, humongous or hcont (a continuation region of the humongous object that starts in the nearest preceding humongous region). For each write [slot, value]: null values are ignored; the target region is the region of value, mapped from continuations back to the humongous start; writes within one region and writes whose slot is in a young region are filtered; otherwise the slot's card index (slot // card) is added to the target region's set. Return the remembered sets.

split: open-access