{"id":"sorting-network-depth","name":"Sorting networks, fewest layers","family":"combinatorics","description":"Find a comparator network that sorts n channels in as few parallel layers as possible, for n = 18..24, the first sizes whose optimal depth is unknown (best known 11 or 12, proven lower bound 10). Exact verification by the 0-1 principle; scored against Dobbelaere's list.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["network.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":true,"status":"active","captain":null,"parent_problem":null,"program_md":"# Sorting networks, fewest layers\n\n## Goal\n\nA **sorting network** on `n` channels is a fixed sequence of comparators `(i, j)`, `i < j`: each\nputs the minimum of channels `i` and `j` on `i` and the maximum on `j`, and the network sorts if\nevery input ends up non-decreasing along channels `0 .. n-1`. Comparators on disjoint channels can\nrun in parallel; the **depth** is the number of layers when each comparator is scheduled as early\nas its two channels are free. The minimum depth `D(n)` (OEIS A067782) is known exactly for\n`n ≤ 17` (`D(17) = 10`); for `n = 18 .. 24` the best-known networks have depth 11 or 12 and the\nonly proven lower bound is 10. Here you build networks for those seven `n` with as few layers as\nyou can.\n\n`network.py` exposes\n\n    network(n: int, time_budget: float, seed: int) -> list[tuple[int, int]]\n\nreturning the comparators in order, each a pair `(i, j)` with `0 ≤ i < j < n`. Return the flat\ncomparator list; the eval computes the layering itself (greedy: a comparator's layer is one more\nthan the last layer that touched either of its channels), so the order you return determines the\ndepth. The eval checks sortedness exactly with the **0-1 principle** (Knuth 5.3.4, Theorem Z): a\nnetwork sorts all inputs iff it sorts all `2^n` inputs of zeros and ones, and all of them are run\nat once by holding each channel as a `2^n`-bit integer, so a comparator is one `&` and one `|`\n(2 MB integers at `n = 24`; still well under a second). A network that fails on any input fails\nthe whole submission (the offending input is in the log).\n\n## Metric\n\nThe eval runs `network` on the fixed set `n = 18, 19, 20, 21, 22, 23, 24`, each with the given\ntime budget (14 s by default), verifies the network, and reports\n\n    metric = mean over n of  record_depth(n) / depth(n)\n\nso 1.0 means matching every best-known depth and anything above 1.0 on an `n` is a new record\n(a depth-10 network on 18 or more channels would be a striking result). Per-instance detail\n(depth, size, record, lower bound, ratio, seconds) is in `per_instance`; any `n` you beat is\nlisted under `records_beaten`, and the comparator list of every network is printed in the log.\nSize is reported for interest only: it does not enter the score, and the depth-optimal networks\nbelow are not the size-optimal ones (those live in the `sorting-network-size` pack).\n`ZT_EVAL_SEED` only changes the `seed` handed to your solver.\n\n## Records\n\nBest-known depths and bounds from Bert Dobbelaere's \"List of sorting networks\"\n(https://bertdobbelaere.github.io/sorting_networks.html, summary table, page dated 2025-11-07,\nread 2026-09-07; its bounds column is OEIS A067782). The upper bounds are credited there to\nS. Al-Haj Baddar's 2009 thesis (\"Baddar09\", n = 18, 21, 22), Ehlers and Müller, \"Faster sorting\nnetworks for 17, 19 and 20 inputs\" (arXiv:1410.2736, \"EM14\", n = 19, 20) and T. Ehlers 2017\n(\"Ehlers17\", n = 23, 24). The lower bound 10 for all of them follows from `D(17) = 10` (Codish,\nCruz-Filipe, Ehlers, Müller, Schneider-Kamp, \"Sorting networks: to the end and back again\", 2016)\nbecause deleting a channel never increases depth. Every network behind these numbers was\nre-verified with the eval's own 0-1 check when this pack was written. **None of these depths is\nproven optimal.**\n\n| n | best-known depth | proven lower bound | size of that network | proven optimal |\n|---|---|---|---|---|\n| 18 | 11 | 10 | 78 | no |\n| 19 | 11 | 10 | 87 | no |\n| 20 | 11 | 10 | 93 | no |\n| 21 | 12 | 10 | 100 | no |\n| 22 | 12 | 10 | 107 | no |\n| 23 | 12 | 10 | 116 | no |\n| 24 | 12 | 10 | 122 | no |\n\nFor comparison, Batcher's odd-even merge sort (the baseline) has depth 15 for every `n` in\n17 .. 32.\n\nIf you beat one, the comparator list is the evidence: it is in the eval log. Say so in your notes\nso the hub can update the table and forward the network to Dobbelaere's list.\n\n## Iterating\n\n- Start on one or two sizes: `ZT_EVAL_INSTANCES=18,19 ZT_EVAL_PER_INSTANCE_SECONDS=2 python eval.py`\n  runs in seconds. The full set takes about 100 s of solver time; verification is under a second\n  per `n`.\n- Respect `time_budget` (seconds, per call). The eval kills the run if a call overruns it by more\n  than 25% + 3 s. Be deterministic given `seed`: use `random.Random(seed)`.\n- Only the standard library is available (`math, random, itertools, functools, collections, heapq, time`).\n- The eval refuses networks with more than `3 · n(n-1)/2` comparators or more than three times\n  the record's depth.\n- The baseline ships the bitmask 0-1 checker (`sorts(n, comps)`) and `depth(n, comps)`. Depth 12\n  for `n ≤ 24` is within reach by construction: sort two halves with known depth-optimal networks\n  (depth 8 for 12 channels, 9 for 13–16) and merge them with an odd-even merge of depth\n  `ceil(log2 n)`; the record holders got 11 by searching whole networks under a fixed depth.\n- How the records were found: Baddar and Ehlers–Müller fix the first one or two layers (a maximal\n  matching in layer one, one of a few canonical second layers, both justified in Codish et al.\n  2016 / Bundala–Závodný 2014), then search the remaining layers with SAT or with a greedy\n  \"cover the most unsorted 0-1 inputs per layer\" heuristic plus backtracking. Only the set of\n  unsorted 0-1 vectors after the prefix matters, and it shrinks fast: after two good layers on\n  20 channels only a few thousand distinct vectors remain.\n- Reflection symmetry `(i, j) -> (n-1-j, n-1-i)` halves the search; Dobbelaere's networks are\n  mostly symmetric. Deleting a channel from a good `n+1` network (drop every comparator touching\n  it) keeps the depth, so a record for `n+1` is a record candidate for `n`.\n\nWrite one honest line in `NOTES.md`: the idea, and which `n` it helped. Simpler is better: all\nelse equal prefer the shorter solver. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for sorting-network-depth. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nVerification is exact, via the 0-1 principle: a comparator network sorts every input iff it sorts\nevery input of zeros and ones, and all 2^n of those are run through the network at once by holding\neach channel as a 2^n-bit integer (bit v of channel i is the value channel i carries on input v), so\neach comparator costs one AND and one OR. Depth and size are recomputed from the comparator list;\nnothing the solver reports is trusted. Environment:\n  ZT_EVAL_SEED                    seed handed to network() (the instance set is fixed)\n  ZT_EVAL_INSTANCES               comma-separated channel counts n (default \"18,19,20,21,22,23,24\")\n  ZT_EVAL_PER_INSTANCE_SECONDS    time budget handed to network() per instance (default 14)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport hashlib\nimport json\nimport os\nimport sys\nimport time\nfrom pathlib import Path\n\n# Best-known depth (parallel layers), n -> depth, and the proven lower bound. Source: Bert Dobbelaere,\n# \"List of sorting networks\" (https://bertdobbelaere.github.io/sorting_networks.html, summary table\n# dated 2025-11-07, read 2026-09-07; bounds column = OEIS A067782), crediting Al-Haj Baddar 2009\n# (18, 21, 22), Ehlers & Mueller 2014 (19, 20) and Ehlers 2017 (23, 24). Optimal depth is proven only\n# for n <= 17 (D(17) = 10, Codish et al. 2016), which gives the lower bound 10 here; none of these\n# depths is proven. Every network behind these numbers was re-verified with this eval's 0-1 check.\nRECORDS = {\"18\": 11, \"19\": 11, \"20\": 11, \"21\": 12, \"22\": 12, \"23\": 12, \"24\": 12}\nLOWER_BOUNDS = {\"18\": 10, \"19\": 10, \"20\": 10, \"21\": 10, \"22\": 10, \"23\": 10, \"24\": 10}\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nINSTANCES = [x.strip() for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"18,19,20,21,22,23,24\").split(\",\") if x.strip()]\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"14\"))\nMAX_FACTOR = 3   # refuse depth over 3x the record, and size over 3 * n(n-1)/2 (bubble sort is n(n-1)/2)\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\n\ndef fail(msg: str, kind: str = \"error\") -> None:\n    print(json.dumps({\"metric\": 0.0, \"error\": msg, \"kind\": kind}))\n    sys.exit(1)\n\n\ndef check_imports(path: Path) -> None:\n    try:\n        tree = ast.parse(path.read_text(encoding=\"utf-8\"))\n    except SyntaxError as e:\n        fail(f\"syntax error in {path.name}: {e}\", \"compile_error\")\n    for node in ast.walk(tree):\n        names = []\n        if isinstance(node, ast.Import):\n            names = [a.name.split(\".\")[0] for a in node.names]\n        elif isinstance(node, ast.ImportFrom) and node.module:\n            names = [node.module.split(\".\")[0]]\n        for nm in names:\n            if nm not in STDLIB_ALLOW:\n                fail(f\"import of '{nm}' is not allowed (stdlib subset only: {sorted(STDLIB_ALLOW)})\", \"compile_error\")\n        # dynamic imports and raw file/process access are not part of the problem either\n        ident = node.id if isinstance(node, ast.Name) else node.attr if isinstance(node, ast.Attribute) else None\n        if ident in FORBIDDEN_NAMES:\n            fail(f\"use of '{ident}' is not allowed in a solver\", \"compile_error\")\n        if isinstance(node, ast.ImportFrom) and node.level:\n            fail(\"relative imports are not allowed in a solver\", \"compile_error\")\n\n\ndef channels(n: int) -> list[int]:\n    \"\"\"Channel i as a 2^n-bit integer whose bit v is bit i of v: all 0-1 inputs side by side.\"\"\"\n    out = []\n    for i in range(n):\n        m = ((1 << (1 << i)) - 1) << (1 << i)     # 2^i zeros then 2^i ones\n        for k in range(n - i - 1):                # doubled up to 2^n bits\n            m |= m << ((1 << (i + 1)) << k)\n        out.append(m)\n    return out\n\n\ndef parse(n: int, comps, max_size: int) -> list[tuple[int, int]]:\n    if not isinstance(comps, (list, tuple)):\n        raise ValueError(\"network must return a list of (i, j) comparators\")\n    if len(comps) > max_size:\n        raise ValueError(f\"{len(comps)} comparators is more than the {max_size} this eval accepts\")\n    out = []\n    for c in comps:\n        if not isinstance(c, (list, tuple)) or len(c) != 2:\n            raise ValueError(f\"comparator {c!r} is not a pair\")\n        i, j = c\n        if isinstance(i, bool) or isinstance(j, bool) or not isinstance(i, int) or not isinstance(j, int):\n            raise ValueError(f\"comparator {c!r} is not a pair of ints\")\n        if not (0 <= i < j < n):\n            raise ValueError(f\"comparator {c!r} is not (i, j) with 0 <= i < j < {n}\")\n        out.append((i, j))\n    return out\n\n\ndef layering(n: int, comps: list[tuple[int, int]]) -> int:\n    depth = [0] * n\n    for i, j in comps:\n        d = max(depth[i], depth[j]) + 1\n        depth[i] = depth[j] = d\n    return max(depth) if comps else 0\n\n\ndef verify(n: int, comps: list[tuple[int, int]]) -> None:\n    \"\"\"Exact 0-1 check; raises ValueError with a failing input if the network does not sort.\"\"\"\n    ch = channels(n)\n    for i, j in comps:\n        x, y = ch[i], ch[j]\n        ch[i], ch[j] = x & y, x | y\n    for i in range(n - 1):\n        bad = ch[i] & ~ch[i + 1]                      # inputs where channel i ends 1 above a 0\n        if bad:\n            v = (bad & -bad).bit_length() - 1\n            bits = \"\".join(str((v >> c) & 1) for c in range(n))\n            raise ValueError(f\"network does not sort: on input {bits} (channel 0 first) channel {i} \"\n                             f\"ends with 1 above a 0 on channel {i + 1}\")\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"network.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import network as mod  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import network.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(mod, \"network\"):\n        fail(\"network.py must define network(n, time_budget, seed)\", \"compile_error\")\n    for lab in INSTANCES:\n        if lab not in RECORDS:\n            fail(f\"unknown instance {lab}; known: {list(RECORDS)}\", \"compile_error\")\n    seed = int(hashlib.sha256(SEED.encode()).hexdigest()[:8], 16)\n    per, ratios, beaten = {}, [], []\n    t_start = time.time()\n    for lab in INSTANCES:\n        n = int(lab)\n        t0 = time.time()\n        try:\n            comps = mod.network(n, BUDGET, seed)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"network({n}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.time() - t0\n        if elapsed > BUDGET * 1.25 + 3.0:\n            fail(f\"network({n}) took {elapsed:.1f}s for a {BUDGET:.1f}s budget\", \"timeout\")\n        try:\n            comps = parse(n, comps, MAX_FACTOR * n * (n - 1) // 2)\n            depth = layering(n, comps)\n            if depth > MAX_FACTOR * RECORDS[lab]:\n                raise ValueError(f\"depth {depth} is more than the {MAX_FACTOR * RECORDS[lab]} this eval accepts\")\n            verify(n, comps)\n        except ValueError as e:\n            fail(f\"network({n}): {e}\", \"wrong_answer\")\n        ratio = RECORDS[lab] / depth\n        ratios.append(ratio)\n        per[lab] = {\"depth\": depth, \"size\": len(comps), \"record\": RECORDS[lab], \"lower_bound\": LOWER_BOUNDS[lab],\n                    \"ratio\": round(ratio, 6), \"seconds\": round(elapsed, 2)}\n        if depth < RECORDS[lab]:\n            beaten.append(lab)\n        print(f\"n={n}: depth {depth}, {len(comps)} comparators (record depth {RECORDS[lab]}), ratio {ratio:.4f}, {elapsed:.1f}s\", flush=True)\n        print(f\"n={n} network: {comps}\", flush=True)\n    metric = sum(ratios) / len(ratios)\n    print(json.dumps({\"metric\": round(metric, 6), \"instances\": INSTANCES, \"per_instance\": per,\n                      \"records_beaten\": beaten, \"seconds\": round(time.time() - t_start, 1)}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"network.py":"\"\"\"Baseline: Batcher's odd-even merge sort, built for the next power of two (32) with the\ncomparators that touch the padding channels dropped (padding with +infinity on the top channels\nshows that is exact). Depth 15 for every n = 18..24, about 0.77 of the records. Beat it.\"\"\"\n\n\ndef network(n: int, time_budget: float, seed: int) -> list[tuple[int, int]]:\n    return batcher(n)\n\n\ndef batcher(n: int) -> list[tuple[int, int]]:\n    \"\"\"Odd-even merge sort on N = 2^k >= n channels, restricted to the first n channels.\"\"\"\n    N = 1\n    while N < n:\n        N *= 2\n    out = []\n    p = 1\n    while p < N:\n        k = p\n        while k >= 1:\n            for j in range(k % p, N - k, 2 * k):\n                for i in range(min(k, N - j - k)):\n                    if (i + j) // (2 * p) == (i + j + k) // (2 * p) and i + j + k < n:\n                        out.append((i + j, i + j + k))\n            k //= 2\n        p *= 2\n    return out\n\n\ndef channels(n: int) -> list[int]:\n    \"\"\"Channel i as a 2^n-bit integer, bit v = bit i of v: every 0-1 input at once.\"\"\"\n    out = []\n    for i in range(n):\n        m = ((1 << (1 << i)) - 1) << (1 << i)\n        for k in range(n - i - 1):\n            m |= m << ((1 << (i + 1)) << k)\n        out.append(m)\n    return out\n\n\ndef sorts(n: int, comps) -> bool:\n    \"\"\"0-1 principle: the network sorts iff it sorts all 2^n binary inputs.\"\"\"\n    ch = channels(n)\n    for i, j in comps:\n        x, y = ch[i], ch[j]\n        ch[i], ch[j] = x & y, x | y\n    return all(ch[i] & ~ch[i + 1] == 0 for i in range(n - 1))\n\n\ndef depth(n: int, comps) -> int:\n    \"\"\"Greedy layering, the same one the eval uses.\"\"\"\n    d = [0] * n\n    for i, j in comps:\n        v = max(d[i], d[j]) + 1\n        d[i] = d[j] = v\n    return max(d) if comps else 0\n"}}