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

N = 1
observations = []
def solve(ops, replicas):
    M = {r: {} for r in replicas}
    def offer(r, key, entry):
        cur = M[r].get(key)
        if cur is None or (entry[1], entry[2], entry[3]) > (cur[1], cur[2], cur[3]):
            M[r][key] = entry
    for op in ops:
        if op[0] == 'put':
            _, r, key, value, ts = op
            offer(r, key, [value, ts, 0, r])
        elif op[0] == 'del':
            _, r, key, ts = op
            offer(r, key, [None, ts, 1, r])
        else:
            s, d = op[1], op[2]
            for key, entry in list(M[s].items()):
                offer(d, key, list(entry))
    return [sorted([k, e[0]] for k, e in M[r].items() ) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 2], ['put', 'b', 'k', 'old', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 4], ['put', 'a', 'x', 2, 2]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 1], ['del', 'b', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 1], ['del', 'a', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 1], ['put', 'b', 'z', 'zb', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 1, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 1], ['n', None]], [['m', 1], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 2], ['put', 'a', 'w', 'late', 1], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]])],
    2: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 3], ['put', 'b', 'k', 'old', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 5], ['put', 'a', 'x', 2, 3]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 2], ['del', 'b', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 2], ['del', 'a', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 2], ['put', 'b', 'z', 'zb', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 2, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 2], ['n', None]], [['m', 2], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 3], ['put', 'a', 'w', 'late', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2]], [['k0', 0], ['k1', 1], ['k2', 2], ['q', 'bq']]])],
    3: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 4], ['put', 'b', 'k', 'old', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 6], ['put', 'a', 'x', 2, 4]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 3], ['del', 'b', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 3], ['del', 'a', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 3], ['put', 'b', 'z', 'zb', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 3, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 3], ['n', None]], [['m', 3], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 4], ['put', 'a', 'w', 'late', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['q', 'bq']]])],
    4: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 5], ['put', 'b', 'k', 'old', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 7], ['put', 'a', 'x', 2, 5]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 4], ['del', 'b', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 4], ['del', 'a', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 4], ['put', 'b', 'z', 'zb', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 4, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 4], ['n', None]], [['m', 4], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 5], ['put', 'a', 'w', 'late', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['q', 'bq']]])],
    5: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 6], ['put', 'b', 'k', 'old', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 8], ['put', 'a', 'x', 2, 6]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 7], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 5], ['del', 'b', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 5], ['del', 'a', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 5], ['put', 'b', 'z', 'zb', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 5, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 5], ['n', None]], [['m', 5], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 6], ['put', 'a', 'w', 'late', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'a', 'k5', 5, 6], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5], ['q', 'bq']]])],
}[N]
for label, args, expected in cases:
    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(ops, replicas):
    M = {r: {} for r in replicas}
    def offer(r, key, entry):
        cur = M[r].get(key)
        if cur is None or (entry[1], entry[2], entry[3]) > (cur[1], cur[2], cur[3]):
            M[r][key] = entry
    for op in ops:
        if op[0] == 'put':
            _, r, key, value, ts = op
            offer(r, key, [value, ts, 0, r])
        elif op[0] == 'del':
            _, r, key, ts = op
            offer(r, key, [None, ts, 1, r])
        else:
            s, d = op[1], op[2]
            for key, entry in list(M[s].items()):
                offer(d, key, list(entry))
    return [sorted([k, e[0]] for k, e in M[r].items() if e[0] is not None) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 2], ['put', 'b', 'k', 'old', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 4], ['put', 'a', 'x', 2, 2]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 1], ['del', 'b', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 1], ['del', 'a', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 1], ['put', 'b', 'z', 'zb', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 1, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 1], ['n', None]], [['m', 1], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 2], ['put', 'a', 'w', 'late', 1], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]])],
    2: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 3], ['put', 'b', 'k', 'old', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 5], ['put', 'a', 'x', 2, 3]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 2], ['del', 'b', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 2], ['del', 'a', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 2], ['put', 'b', 'z', 'zb', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 2, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 2], ['n', None]], [['m', 2], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 3], ['put', 'a', 'w', 'late', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2]], [['k0', 0], ['k1', 1], ['k2', 2], ['q', 'bq']]])],
    3: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 4], ['put', 'b', 'k', 'old', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 6], ['put', 'a', 'x', 2, 4]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 3], ['del', 'b', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 3], ['del', 'a', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 3], ['put', 'b', 'z', 'zb', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 3, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 3], ['n', None]], [['m', 3], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 4], ['put', 'a', 'w', 'late', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['q', 'bq']]])],
    4: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 5], ['put', 'b', 'k', 'old', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 7], ['put', 'a', 'x', 2, 5]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 4], ['del', 'b', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 4], ['del', 'a', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 4], ['put', 'b', 'z', 'zb', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 4, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 4], ['n', None]], [['m', 4], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 5], ['put', 'a', 'w', 'late', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['q', 'bq']]])],
    5: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 6], ['put', 'b', 'k', 'old', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 8], ['put', 'a', 'x', 2, 6]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 7], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 5], ['del', 'b', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 5], ['del', 'a', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 5], ['put', 'b', 'z', 'zb', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 5, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 5], ['n', None]], [['m', 5], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 6], ['put', 'a', 'w', 'late', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'a', 'k5', 5, 6], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5], ['q', 'bq']]])],
}[N]
for label, args, expected in cases:
    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:
Deleted keys appear in the document with a null value.

Each key holds [value, ts, kind, writer] with kind 1 for a delete tombstone and 0 for a put. An incoming entry (local op or merge) replaces the stored one only if (ts, kind, writer) is lexicographically larger, so deletes win timestamp ties and writers break the rest. Tombstones are kept. ["merge", s, d] offers each of s's entries to d. Return sorted visible [key, value] pairs per replica.

split: open-access


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

N = 1
observations = []
def solve(ops, replicas):
    M = {r: {} for r in replicas}
    def offer(r, key, entry):
        cur = M[r].get(key)
        if cur is None or (entry[1], entry[3]) > (cur[1], cur[3]):
            M[r][key] = entry
    for op in ops:
        if op[0] == 'put':
            _, r, key, value, ts = op
            offer(r, key, [value, ts, 0, r])
        elif op[0] == 'del':
            _, r, key, ts = op
            offer(r, key, [None, ts, 1, r])
        else:
            s, d = op[1], op[2]
            for key, entry in list(M[s].items()):
                offer(d, key, list(entry))
    return [sorted([k, e[0]] for k, e in M[r].items() if e[2] == 0) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 2], ['put', 'b', 'k', 'old', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 4], ['put', 'a', 'x', 2, 2]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 1], ['del', 'b', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 1], ['del', 'a', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 1], ['put', 'b', 'z', 'zb', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 1, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 1], ['n', None]], [['m', 1], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 2], ['put', 'a', 'w', 'late', 1], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]])],
    2: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 3], ['put', 'b', 'k', 'old', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 5], ['put', 'a', 'x', 2, 3]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 2], ['del', 'b', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 2], ['del', 'a', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 2], ['put', 'b', 'z', 'zb', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 2, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 2], ['n', None]], [['m', 2], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 3], ['put', 'a', 'w', 'late', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2]], [['k0', 0], ['k1', 1], ['k2', 2], ['q', 'bq']]])],
    3: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 4], ['put', 'b', 'k', 'old', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 6], ['put', 'a', 'x', 2, 4]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 3], ['del', 'b', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 3], ['del', 'a', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 3], ['put', 'b', 'z', 'zb', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 3, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 3], ['n', None]], [['m', 3], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 4], ['put', 'a', 'w', 'late', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['q', 'bq']]])],
    4: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 5], ['put', 'b', 'k', 'old', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 7], ['put', 'a', 'x', 2, 5]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 4], ['del', 'b', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 4], ['del', 'a', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 4], ['put', 'b', 'z', 'zb', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 4, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 4], ['n', None]], [['m', 4], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 5], ['put', 'a', 'w', 'late', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['q', 'bq']]])],
    5: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 6], ['put', 'b', 'k', 'old', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 8], ['put', 'a', 'x', 2, 6]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 7], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 5], ['del', 'b', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 5], ['del', 'a', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 5], ['put', 'b', 'z', 'zb', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 5, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 5], ['n', None]], [['m', 5], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 6], ['put', 'a', 'w', 'late', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'a', 'k5', 5, 6], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5], ['q', 'bq']]])],
}[N]
for label, args, expected in cases:
    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(ops, replicas):
    M = {r: {} for r in replicas}
    def offer(r, key, entry):
        cur = M[r].get(key)
        if cur is None or (entry[1], entry[2], entry[3]) > (cur[1], cur[2], cur[3]):
            M[r][key] = entry
    for op in ops:
        if op[0] == 'put':
            _, r, key, value, ts = op
            offer(r, key, [value, ts, 0, r])
        elif op[0] == 'del':
            _, r, key, ts = op
            offer(r, key, [None, ts, -1, r])
        else:
            s, d = op[1], op[2]
            for key, entry in list(M[s].items()):
                offer(d, key, list(entry))
    return [sorted([k, e[0]] for k, e in M[r].items() if e[2] == 0) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 2], ['put', 'b', 'k', 'old', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 4], ['put', 'a', 'x', 2, 2]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 1], ['del', 'b', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 1], ['del', 'a', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 1], ['put', 'b', 'z', 'zb', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 1, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 1], ['n', None]], [['m', 1], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 2], ['put', 'a', 'w', 'late', 1], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]])],
    2: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 3], ['put', 'b', 'k', 'old', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 5], ['put', 'a', 'x', 2, 3]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 2], ['del', 'b', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 2], ['del', 'a', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 2], ['put', 'b', 'z', 'zb', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 2, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 2], ['n', None]], [['m', 2], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 3], ['put', 'a', 'w', 'late', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2]], [['k0', 0], ['k1', 1], ['k2', 2], ['q', 'bq']]])],
    3: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 4], ['put', 'b', 'k', 'old', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 6], ['put', 'a', 'x', 2, 4]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 3], ['del', 'b', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 3], ['del', 'a', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 3], ['put', 'b', 'z', 'zb', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 3, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 3], ['n', None]], [['m', 3], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 4], ['put', 'a', 'w', 'late', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['q', 'bq']]])],
    4: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 5], ['put', 'b', 'k', 'old', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 7], ['put', 'a', 'x', 2, 5]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 4], ['del', 'b', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 4], ['del', 'a', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 4], ['put', 'b', 'z', 'zb', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 4, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 4], ['n', None]], [['m', 4], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 5], ['put', 'a', 'w', 'late', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['q', 'bq']]])],
    5: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 6], ['put', 'b', 'k', 'old', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 8], ['put', 'a', 'x', 2, 6]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 7], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 5], ['del', 'b', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 5], ['del', 'a', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 5], ['put', 'b', 'z', 'zb', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 5, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 5], ['n', None]], [['m', 5], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 6], ['put', 'a', 'w', 'late', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'a', 'k5', 5, 6], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5], ['q', 'bq']]])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
A put and a delete with equal timestamps resolve by replica name, sometimes keeping the key.

Each key holds [value, ts, kind, writer] with kind 1 for a delete tombstone and 0 for a put. An incoming entry (local op or merge) replaces the stored one only if (ts, kind, writer) is lexicographically larger, so deletes win timestamp ties and writers break the rest. Tombstones are kept. ["merge", s, d] offers each of s's entries to d. Return sorted visible [key, value] pairs per replica.

split: open-access


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

N = 1
observations = []
def solve(initial, inserts):
    BASE = 10
    lst = [list(p) for p in initial]
    def between(p, q):
        out = []
        upper = True
        d = 0
        while True:
            a = p[d] if d < len(p) else 0
            b = q[d] if upper and d < len(q) else BASE
            if b - a > 0:
                out.append((a + b) // 2)
                return out
            out.append(a)
            if a < b:
                upper = False
            d += 1
    for i in inserts:
        p = lst[i - 1] if i > 0 else []
        q = lst[i] if i < len(lst) else []
        lst.insert(i, between(p, q))
    return ['.'.join(str(x) for x in pos) for pos in lst]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4]], ['5', '7', '8', '9', '9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0]], ['0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2]], ['2', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1]], ['1.2.9', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    2: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5]], ['5', '7', '8', '9', '9.5', '9.7']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0]], ['0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1]], ['2', '3', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1]], ['1.2.9', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    3: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6]], ['5', '7', '8', '9', '9.5', '9.7', '9.8']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0]], ['0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3]], ['2', '3', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1]], ['1.2.9', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    4: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2]], ['2', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1]], ['1.2.9', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    5: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7, 8]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9', '9.9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.1', '0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2, 1]], ['2', '2.5', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1, 1]], ['1.2.9', '1.2.9.2', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
}[N]
for label, args, expected in cases:
    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(initial, inserts):
    BASE = 10
    lst = [list(p) for p in initial]
    def between(p, q):
        out = []
        upper = True
        d = 0
        while True:
            a = p[d] if d < len(p) else 0
            b = q[d] if upper and d < len(q) else BASE
            if b - a > 0:
                out.append(a + 1)
                return out
            out.append(a)
            if a < b:
                upper = False
            d += 1
    for i in inserts:
        p = lst[i - 1] if i > 0 else []
        q = lst[i] if i < len(lst) else []
        lst.insert(i, between(p, q))
    return ['.'.join(str(x) for x in pos) for pos in lst]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4]], ['5', '7', '8', '9', '9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0]], ['0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2]], ['2', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1]], ['1.2.9', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    2: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5]], ['5', '7', '8', '9', '9.5', '9.7']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0]], ['0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1]], ['2', '3', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1]], ['1.2.9', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    3: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6]], ['5', '7', '8', '9', '9.5', '9.7', '9.8']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0]], ['0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3]], ['2', '3', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1]], ['1.2.9', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    4: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2]], ['2', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1]], ['1.2.9', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    5: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7, 8]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9', '9.9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.1', '0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2, 1]], ['2', '2.5', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1, 1]], ['1.2.9', '1.2.9.2', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
}[N]
for label, args, expected in cases:
    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:
Two neighbours one digit apart receive a new position equal to the lower neighbour.

Starting from the given sorted positions, positions are digit lists in base 10 compared lexicographically and never ending in 0. Inserting at list index i allocates between the neighbours p (or [] at the start) and q (or [] at the end): walking depth d, lower digit a is p[d] or 0, upper digit b is q[d] while q still constrains (else 10); if b - a > 1 append (a+b)//2 and stop, else append a, and q stops constraining once a < b. Return positions as dotted strings in list order.

split: open-access


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

N = 1
observations = []
def solve(initial, inserts):
    BASE = 10
    lst = [list(p) for p in initial]
    def between(p, q):
        out = []
        upper = True
        d = 0
        while True:
            a = p[d] if d < len(p) else 0
            b = q[d] if upper and d < len(q) else BASE
            if b - a > 1:
                out.append((a + b) // 2)
                return out
            out.append(a)
            d += 1
    for i in inserts:
        p = lst[i - 1] if i > 0 else []
        q = lst[i] if i < len(lst) else []
        lst.insert(i, between(p, q))
    return ['.'.join(str(x) for x in pos) for pos in lst]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4]], ['5', '7', '8', '9', '9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0]], ['0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2]], ['2', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1]], ['1.2.9', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    2: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5]], ['5', '7', '8', '9', '9.5', '9.7']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0]], ['0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1]], ['2', '3', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1]], ['1.2.9', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    3: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6]], ['5', '7', '8', '9', '9.5', '9.7', '9.8']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0]], ['0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3]], ['2', '3', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1]], ['1.2.9', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    4: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2]], ['2', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1]], ['1.2.9', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    5: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7, 8]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9', '9.9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.1', '0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2, 1]], ['2', '2.5', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1, 1]], ['1.2.9', '1.2.9.2', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
}[N]
for label, args, expected in cases:
    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(initial, inserts):
    BASE = 10
    lst = [list(p) for p in initial]
    def between(p, q):
        out = []
        upper = True
        d = 0
        while True:
            a = p[d] if d < len(p) else 0
            b = q[d] if upper and d < len(q) else BASE
            if b - a > 1:
                out.append((a + b) // 2)
                return out
            out.append(a)
            if a < b and d + 1 >= len(p):
                upper = False
            d += 1
    for i in inserts:
        p = lst[i - 1] if i > 0 else []
        q = lst[i] if i < len(lst) else []
        lst.insert(i, between(p, q))
    return ['.'.join(str(x) for x in pos) for pos in lst]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4]], ['5', '7', '8', '9', '9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0]], ['0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2]], ['2', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1]], ['1.2.9', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    2: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5]], ['5', '7', '8', '9', '9.5', '9.7']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0]], ['0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1]], ['2', '3', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1]], ['1.2.9', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    3: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6]], ['5', '7', '8', '9', '9.5', '9.7', '9.8']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0]], ['0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3]], ['2', '3', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1]], ['1.2.9', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    4: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2]], ['2', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1]], ['1.2.9', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    5: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7, 8]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9', '9.9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.1', '0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2, 1]], ['2', '2.5', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1, 1]], ['1.2.9', '1.2.9.2', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
}[N]
for label, args, expected in cases:
    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:
Positions are allocated deeper than necessary or squeezed against digits that no longer bound them.

Starting from the given sorted positions, positions are digit lists in base 10 compared lexicographically and never ending in 0. Inserting at list index i allocates between the neighbours p (or [] at the start) and q (or [] at the end): walking depth d, lower digit a is p[d] or 0, upper digit b is q[d] while q still constrains (else 10); if b - a > 1 append (a+b)//2 and stop, else append a, and q stops constraining once a < b. Return positions as dotted strings in list order.

split: open-access


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

N = 1
observations = []
def solve(initial, inserts):
    BASE = 10
    lst = [list(p) for p in initial]
    def between(p, q):
        out = []
        upper = True
        d = 0
        while True:
            a = p[d] if d < len(p) else 0
            b = q[d] if upper and d < len(q) else BASE - 1
            if b - a > 1:
                out.append((a + b) // 2)
                return out
            out.append(a)
            if a < b:
                upper = False
            d += 1
    for i in inserts:
        p = lst[i - 1] if i > 0 else []
        q = lst[i] if i < len(lst) else []
        lst.insert(i, between(p, q))
    return ['.'.join(str(x) for x in pos) for pos in lst]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4]], ['5', '7', '8', '9', '9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0]], ['0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2]], ['2', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1]], ['1.2.9', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    2: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5]], ['5', '7', '8', '9', '9.5', '9.7']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0]], ['0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1]], ['2', '3', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1]], ['1.2.9', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    3: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6]], ['5', '7', '8', '9', '9.5', '9.7', '9.8']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0]], ['0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3]], ['2', '3', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1]], ['1.2.9', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    4: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2]], ['2', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1]], ['1.2.9', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    5: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7, 8]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9', '9.9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.1', '0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2, 1]], ['2', '2.5', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1, 1]], ['1.2.9', '1.2.9.2', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
}[N]
for label, args, expected in cases:
    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(initial, inserts):
    BASE = 10
    lst = [list(p) for p in initial]
    def between(p, q):
        out = []
        upper = True
        d = 0
        while True:
            a = p[d] if d < len(p) else 0
            b = q[d] if upper and d < len(q) else BASE + 1
            if b - a > 1:
                out.append((a + b) // 2)
                return out
            out.append(a)
            if a < b:
                upper = False
            d += 1
    for i in inserts:
        p = lst[i - 1] if i > 0 else []
        q = lst[i] if i < len(lst) else []
        lst.insert(i, between(p, q))
    return ['.'.join(str(x) for x in pos) for pos in lst]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4]], ['5', '7', '8', '9', '9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0]], ['0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2]], ['2', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1]], ['1.2.9', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    2: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5]], ['5', '7', '8', '9', '9.5', '9.7']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0]], ['0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1]], ['2', '3', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1]], ['1.2.9', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    3: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6]], ['5', '7', '8', '9', '9.5', '9.7', '9.8']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0]], ['0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3]], ['2', '3', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1]], ['1.2.9', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    4: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2]], ['2', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1]], ['1.2.9', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
    5: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7, 8]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9', '9.9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.1', '0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2, 1]], ['2', '2.5', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1, 1]], ['1.2.9', '1.2.9.2', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
}[N]
for label, args, expected in cases:
    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:
Appending after a position ending in 8 or 9 goes deeper instead of using the free top digit.

Starting from the given sorted positions, positions are digit lists in base 10 compared lexicographically and never ending in 0. Inserting at list index i allocates between the neighbours p (or [] at the start) and q (or [] at the end): walking depth d, lower digit a is p[d] or 0, upper digit b is q[d] while q still constrains (else 10); if b - a > 1 append (a+b)//2 and stop, else append a, and q stops constraining once a < b. Return positions as dotted strings in list order.

split: open-access