{"id":"constant-weight-codes","name":"Largest constant-weight codes A(n,d,w), open entries of Brouwer's table","family":"coding-theory","description":"Return an explicit binary constant-weight code (list of integers below 2^n, each of weight w) of length n with minimum Hamming distance d, as large as you can, for 21 triples (n, d, w) with n <= 28 whose best-known lower and upper bounds on A(n,d,w) still differ. The eval recomputes weights and the minimum distance from the words; the score is code size over the best-known lower bound.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["cwc.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":"# Largest constant-weight codes A(n,d,w), open entries of Brouwer's table\n\n## Goal\n\n`cwc.py` exposes `code(n: int, d: int, w: int, time_budget: float, seed: int) -> list[int]`: a\nbinary code of length `n`, minimum Hamming distance `d`, in which every codeword has Hamming weight\nexactly `w`, given as a list of distinct integers in `[0, 2^n)` (bit `i` is coordinate `i`). Return\nas many codewords as you can.\n\n`A(n,d,w)` is the largest size of such a code (equivalently, the largest family of `w`-subsets of an\n`n`-set with pairwise intersections at most `w - d/2`; packings and Steiner systems are the extreme\ncases). Brouwer's tables of bounds on `A(n,d,w)`, updating Brouwer, Shearer, Sloane and Smith (1990),\ngive an explicit code for nearly every lower bound. The 22 instances here are open cells of those\ntables with `n <= 28`, `d = 6..14`, and records that verify in well under a second. Beat the record\nin any row and you have a new lower bound; the table moved in 2026 alone through Rosin (automated\nsearch, arXiv:2603.00174), Lysenstoen (arXiv:2607.19550), Echols (arXiv:2608.13906) and two batches\nof new codes from Boisclair, so these entries are live.\n\n## Records\n\nBest-known lower bounds (the records) and upper bounds, read 2026-09-07 from\naeb.win.tue.nl/codes/Andw.html. Every row is open. Unmarked upper bounds in the table are Agrell,\nVardy and Zeger (2000); \"S\" Schrijver (2005), \"KKT\" Kang-Kim-Toan (2011), \"Po\" Polak (2017), \"MEL\"\nMounits-Etzion-Litsyn (2005), \"O\" Ostergard (2010). \"BSSS\" is the 1990 table.\n\n| n | d | w | record | upper bound | source of the record |\n|---|---|---|---|---|---|\n| 18 | 6 | 5 | 69 | 72 | Aw, Chee and Ling, Ars Comb. 67 (2003) |\n| 20 | 6 | 5 | 90 | 100 | cyclic code, first given on Brouwer's page |\n| 22 | 6 | 5 | 132 | 136 | code with a prescribed automorphism group, Brouwer's page |\n| 18 | 6 | 6 | 133 | 186 | Rosin, arXiv:2603.00174 |\n| 20 | 6 | 6 | 232 | 276 | from the Nordstrom-Robinson / Golay code with tails (Brouwer, label t) |\n| 21 | 6 | 6 | 273 | 350 | code with a prescribed automorphism group, first given on Brouwer's page |\n| 20 | 6 | 7 | 462 | 651 | from the Nordstrom-Robinson / Golay code with tails (Brouwer, label t) |\n| 20 | 6 | 8 | 590 | 1084 (Po) | Echols, arXiv:2608.13906 |\n| 23 | 6 | 10 | 2992 | 7521 | Lysenstoen, arXiv:2607.19550, polished on Brouwer's page |\n| 24 | 6 | 10 | 4237 | 12186 | Lysenstoen, arXiv:2607.19550, polished on Brouwer's page |\n| 18 | 8 | 9 | 48 | 58 (O) | BSSS, shortened code |\n| 20 | 8 | 9 | 160 | 173 | code with a prescribed automorphism group, Brouwer's page |\n| 22 | 8 | 9 | 292 | 440 (Po) | Rosin, arXiv:2603.00174 |\n| 23 | 8 | 9 | 412 | 662 (Po) | Rosin, arXiv:2603.00174 |\n| 24 | 8 | 6 | 78 | 92 | BSSS |\n| 22 | 10 | 8 | 25 | 33 | Rosin, arXiv:2603.00174 |\n| 23 | 10 | 9 | 45 | 78 (MEL) | cyclic code, Brouwer's page |\n| 24 | 10 | 10 | 72 | 170 (KKT) | cyclic code, Brouwer's page |\n| 26 | 12 | 10 | 33 | 37 | Nurmela, Kaikkonen and Ostergard, IEEE Trans. Inf. Theory 43 (1997) |\n| 27 | 12 | 11 | 54 | 90 | cyclic code, Brouwer's page |\n| 28 | 12 | 12 | 119 | 198 (KKT) | code with a prescribed automorphism group, first given on Brouwer's page |\n| 27 | 14 | 12 | 19 | 20 | cyclic code, Brouwer's page |\n\nAll 22 record codes were downloaded from the table's explicit-code links (`cwc/d6/i20.5` and so on;\norbit files were expanded under the listed permutation group) and pass this eval at exactly the\nrecord size. The upper bounds are hard caps: the eval refuses any list longer than the upper bound,\nbecause such a list necessarily contains a pair at distance below `d`.\n\n## Metric\n\n    metric = mean over the 22 instances of  size(n,d,w) / record(n,d,w)\n\nThe eval re-derives everything from the list you return: every entry must be an `int` in\n`[0, 2^n)` (no `bool`) of weight exactly `w`, entries must be distinct, and every pair must be at\nHamming distance at least `d` (for constant weight this is even, so `d = 6` means any two words\nshare at most `w - 3` ones). The check is exact integer XOR and popcount, bucketed by a pigeonhole\non `d` coordinate blocks. Any violation fails the whole run (`wrong_answer`); so does a solver that\nraises or runs past `1.25 * time_budget + 3` seconds. Only size counts; `size / record` above 1 in\nany row is listed in `records_beaten`.\n\n`ZT_EVAL_SEED` only changes the `seed` handed to `code`; the instance set is fixed.\n\n## Constraints\n\n- Standard library only. No numpy, no scipy. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The default is 4 s per instance, so a full eval takes\n  about 90 s plus about a second of verification.\n- Deterministic given `seed`: use `random.Random(seed)`.\n\n## Iterating\n\n- `ZT_EVAL_INSTANCES=20-6-5,24-6-10` runs a subset (labels are `n-d-w`);\n  `ZT_EVAL_PER_INSTANCE_SECONDS=1` shortens the per-instance budget. Run `python eval.py` in your\n  workspace and read `per_instance` for `size`, `ratio`, `seconds` and `verify_seconds`.\n- The baseline (greedy union of random cyclic orbits, then random single words) scores about 0.56.\n  It is weakest on the big `d = 6` rows and the `d >= 12` rows, where the records are structured.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Codes with a prescribed automorphism group. Almost every record in the table is a union of\n  orbits of a group acting on the coordinates: the full cyclic shift (`Z_n`), a product of shorter\n  cycles (Brouwer's `cycle 1 1 9 9`, `cycle 3 3 3 ... 1 1 1`), affine groups `x -> ax + b` on `Z_p`\n  or on `GF(q)`, `ASL(1,q)`, or two generating permutations. Enumerate orbits under the group\n  (their internal minimum distance is fixed once), then solve a maximum clique / independent-set\n  problem on the compatibility graph of orbits. This is the Nurmela-Kaikkonen-Ostergard method and\n  the `g`/`c` entries of the table; it beats orbit-greedy by a wide margin.\n- Local search on the word level: pick a word, drop it, greedily refill from the candidates it was\n  blocking; simulated annealing on the number of violated pairs with a tabu list. Rosin's 2026\n  records came from an automated search of this kind, and Lysenstoen's from fixing half the\n  coordinates to a known code and solving the other half as a maximum-weight independent set.\n- Constructions from smaller codes: shortening (`A(n,d,w) >= A(n+1,d,w) * ... `, take the words\n  with a 0 or a 1 in one coordinate), lengthening, juxtaposition, partitioning the weight-`w` words\n  by a linear code of distance `d` (the Graham-Sloane construction), and taking the weight-`w`\n  words of the Golay or Nordstrom-Robinson code (labels `G` and `t`) and appending \"tails\".\n- Steiner systems and packings are the `w - d/2 = t - 1` boundary: the `d = 2w - 2` rows are\n  packings of `(w-1)`-subsets, so design-theoretic constructions (difference families, cyclic\n  packings) apply directly.\n- Pairwise checks cost about 50 ns per pair in pure Python; a candidate screened against 4000\n  words costs about 0.2 ms, so budget candidates accordingly, or index the code by a coordinate\n  block the way the eval does.\n\nWrite one honest line in `NOTES.md`: the idea, and which rows it helped.\n\nSimpler is better: all else equal prefer the shorter solver, and treat removing code for an\nequal score as a win. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for constant-weight-codes. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nThe solver returns a list of codewords (integers below 2^n, each of Hamming weight w). The eval\nrecomputes everything from that list: distinctness, range, weight, and the minimum Hamming\ndistance (exact integer XOR + popcount), and scores size / best-known lower bound. Nothing the\nsolver reports is trusted.\n\nEnv:\n  ZT_EVAL_SEED                   seed handed to code()\n  ZT_EVAL_PER_INSTANCE_SECONDS   time budget per (n, d, w) (default 4)\n  ZT_EVAL_INSTANCES              comma-separated labels \"n-d-w\" (default: all 22 below)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport math\nimport os\nimport random\nimport sys\nimport time\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"4\"))\nDEFAULT_INSTANCES = (\"18-6-5,20-6-5,22-6-5,18-6-6,20-6-6,21-6-6,20-6-7,20-6-8,23-6-10,24-6-10,\"\n                     \"18-8-9,20-8-9,22-8-9,23-8-9,24-8-6,22-10-8,23-10-9,24-10-10,\"\n                     \"26-12-10,27-12-11,28-12-12,27-14-12\")\nINSTANCES = [x.strip() for x in os.environ.get(\"ZT_EVAL_INSTANCES\", DEFAULT_INSTANCES).split(\",\") if x.strip()]\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nEPS = 1e-9\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\n# (n, d, w) -> (best-known lower bound = record, best-known upper bound, source of the lower bound).\n# Read 2026-09-07 from Andries Brouwer's tables of bounds on A(n,d,w) (aeb.win.tue.nl/codes/Andw.html),\n# which update Brouwer, Shearer, Sloane and Smith, \"A new table of constant weight codes\", IEEE Trans.\n# Inf. Theory 36 (1990) (\"BSSS\"). Unmarked upper bounds there are Agrell, Vardy and Zeger, IEEE Trans.\n# Inf. Theory 46 (2000); others are Schrijver 2005 (S), Kang-Kim-Toan 2011 (KKT), Polak 2017 (Po),\n# Mounits-Etzion-Litsyn 2005 (MEL), Ostergard 2010 (O). Every entry here is open: lower < upper, and\n# every record was downloaded from the table's explicit-code link and passes this eval exactly.\n# Update when a hub-verified submission exceeds the record.\nRECORDS = {\n    (18, 6, 5): (69, 72, \"Aw, Chee and Ling, Ars Comb. 67 (2003)\"),\n    (20, 6, 5): (90, 100, \"cyclic code first given on Brouwer's page\"),\n    (22, 6, 5): (132, 136, \"code with prescribed automorphism group, Brouwer's page\"),\n    (18, 6, 6): (133, 186, \"Rosin, arXiv:2603.00174 (2026)\"),\n    (20, 6, 6): (232, 276, \"from the Nordstrom-Robinson / Golay code with tails, Brouwer's page (label t)\"),\n    (21, 6, 6): (273, 350, \"code with prescribed automorphism group, first given on Brouwer's page\"),\n    (20, 6, 7): (462, 651, \"from the Nordstrom-Robinson / Golay code with tails, Brouwer's page (label t)\"),\n    (20, 6, 8): (590, 1084, \"Echols, arXiv:2608.13906 (2026)\"),\n    (23, 6, 10): (2992, 7521, \"Lysenstoen, arXiv:2607.19550 (2026), polished on Brouwer's page\"),\n    (24, 6, 10): (4237, 12186, \"Lysenstoen, arXiv:2607.19550 (2026), polished on Brouwer's page\"),\n    (18, 8, 9): (48, 58, \"BSSS, shortened code; upper bound Ostergard 2010\"),\n    (20, 8, 9): (160, 173, \"code with prescribed automorphism group, Brouwer's page\"),\n    (22, 8, 9): (292, 440, \"Rosin, arXiv:2603.00174 (2026)\"),\n    (23, 8, 9): (412, 662, \"Rosin, arXiv:2603.00174 (2026)\"),\n    (24, 8, 6): (78, 92, \"BSSS (1990)\"),\n    (22, 10, 8): (25, 33, \"Rosin, arXiv:2603.00174 (2026)\"),\n    (23, 10, 9): (45, 78, \"cyclic code, Brouwer's page; upper bound MEL 2005\"),\n    (24, 10, 10): (72, 170, \"cyclic code, Brouwer's page; upper bound KKT 2011\"),\n    (26, 12, 10): (33, 37, \"Nurmela, Kaikkonen and Ostergard, IEEE Trans. Inf. Theory 43 (1997)\"),\n    (27, 12, 11): (54, 90, \"cyclic code, Brouwer's page\"),\n    (28, 12, 12): (119, 198, \"code with prescribed automorphism group, first given on Brouwer's page\"),\n    (27, 14, 12): (19, 20, \"cyclic code, Brouwer's page\"),\n}\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 cwc.py: {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 parse_label(label: str) -> tuple[int, int, int]:\n    try:\n        n, d, w = (int(x) for x in label.split(\"-\"))\n    except Exception:\n        fail(f\"bad instance label {label!r}, expected 'n-d-w'\", \"error\")\n    if (n, d, w) not in RECORDS:\n        fail(f\"no record for (n, d, w) = ({n}, {d}, {w})\", \"error\")\n    return n, d, w\n\n\ndef parse_words(words, n: int, d: int, w: int) -> list[int]:\n    \"\"\"Return the codewords as distinct weight-w ints in [0, 2^n). Anything else is a wrong answer.\"\"\"\n    tag = f\"code({n}, {d}, {w})\"\n    if not isinstance(words, (list, tuple, set, frozenset)):\n        fail(f\"{tag} must return a list of integers\", \"wrong_answer\")\n    upper = RECORDS[(n, d, w)][1]\n    if len(words) > upper:\n        fail(f\"{tag} returned {len(words)} words, more than the proven upper bound A({n},{d},{w}) <= {upper}: \"\n             \"such a list necessarily contains two words at distance < d; refusing to verify\", \"wrong_answer\")\n    out = []\n    for x in words:\n        if isinstance(x, bool) or not isinstance(x, int):\n            fail(f\"{tag} returned a non-integer codeword {x!r}\"[:300], \"wrong_answer\")\n        if x < 0 or x >> n:\n            fail(f\"{tag} returned {x}, which is not in [0, 2^{n})\", \"wrong_answer\")\n        if x.bit_count() != w:\n            fail(f\"{tag} returned {x}, which has weight {x.bit_count()}, not {w}\", \"wrong_answer\")\n        out.append(x)\n    if len(set(out)) != len(out):\n        fail(f\"{tag} returned duplicate codewords (distance 0)\", \"wrong_answer\")\n    return out\n\n\ndef hamming_cap(m: int, d: int) -> int:\n    \"\"\"Sphere-packing bound on a binary code of length m and minimum distance d.\"\"\"\n    t = (d - 1) // 2\n    return (1 << m) // sum(math.comb(m, i) for i in range(t + 1))\n\n\ndef check_min_distance(code: list[int], n: int, d: int, tag: str) -> None:\n    \"\"\"Fail unless every pair of codewords is at Hamming distance >= d.\n\n    Pigeonhole: split the n coordinates into d blocks; two words at distance <= d-1 agree on at\n    least one whole block, so only pairs that share a block value need comparing. Words sharing a\n    block of b coordinates form a code of length n-b and distance d, so a bucket larger than the\n    sphere-packing bound for (n-b, d) is impossible and is rejected outright (this also bounds the\n    work on adversarial input).\n    \"\"\"\n    sizes = [n // d + (1 if i < n % d else 0) for i in range(d)]\n    shift = 0\n    for b in sizes:\n        mask = (1 << b) - 1\n        buckets: dict[int, list[int]] = {}\n        for c in code:\n            buckets.setdefault((c >> shift) & mask, []).append(c)\n        cap = hamming_cap(n - b, d)\n        for lst in buckets.values():\n            if len(lst) > cap:\n                fail(f\"{tag}: {len(lst)} codewords agree on {b} coordinates, but a distance-{d} code of length \"\n                     f\"{n - b} has at most {cap} words; the list contains a pair at distance < {d}\", \"wrong_answer\")\n            for i in range(len(lst) - 1):\n                ci = lst[i]\n                for cj in lst[i + 1:]:\n                    if (ci ^ cj).bit_count() < d:\n                        fail(f\"{tag}: codewords {ci} and {cj} are at distance {(ci ^ cj).bit_count()} < {d}\",\n                             \"wrong_answer\")\n        shift += b\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"cwc.py\")\n    sys.dont_write_bytecode = True  # a stale cwc.pyc must never be what gets scored\n    sys.path.insert(0, str(here))\n    try:\n        import cwc as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import cwc.py failed: {e!r}\", \"compile_error\")\n    if not callable(getattr(cand, \"code\", None)):\n        fail(\"cwc.py must define code(n, d, w, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"andw|{SEED}\").getrandbits(32)\n    per, beaten = {}, []\n    for label in INSTANCES:\n        n, d, w = parse_label(label)\n        record, upper, _src = RECORDS[(n, d, w)]\n        tag = f\"code({n}, {d}, {w})\"\n        t0 = time.perf_counter()\n        try:\n            words = cand.code(n, d, w, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"{tag} raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"{tag} took {elapsed:.1f}s against a {BUDGET:.1f}s budget\", \"timeout\")\n        t1 = time.perf_counter()\n        code = parse_words(words, n, d, w)\n        check_min_distance(code, n, d, tag)\n        size = len(code)\n        per[f\"{n}-{d}-{w}\"] = {\"size\": size, \"record\": record, \"upper_bound\": upper,\n                               \"ratio\": round(size / record, 6), \"seconds\": round(elapsed, 2),\n                               \"verify_seconds\": round(time.perf_counter() - t1, 2)}\n        if size > record:\n            beaten.append(f\"{n}-{d}-{w}\")\n    metric = sum(v[\"ratio\"] for v in per.values()) / len(per)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_instance\": per, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"cwc.py":"\"\"\"Baseline: greedy union of cyclic orbits, then a random greedy fill.\n\nPhase 1 draws random words of weight w and tries to add the whole orbit under the cyclic shift\n(n words or a divisor of n): the orbit must have internal minimum distance >= d and distance >= d\nto everything placed so far. Many table entries are cyclic codes found this way with a smarter\nchoice of orbits. Phase 2 spends the rest of the budget adding single random words of weight w\nthat fit. Deterministic given seed. Scores roughly half the records. Beat it.\n\"\"\"\n\nimport random\nimport time\n\n\ndef _fits(c: int, words: list[int], d: int) -> bool:\n    return all((c ^ x).bit_count() >= d for x in words)\n\n\ndef _orbit(c: int, n: int) -> list[int]:\n    mask = (1 << n) - 1\n    out, x = [], c\n    while True:\n        out.append(x)\n        x = ((x << 1) | (x >> (n - 1))) & mask\n        if x == c:\n            return out\n\n\ndef _random_word(rng: random.Random, n: int, w: int) -> int:\n    c = 0\n    for i in rng.sample(range(n), w):\n        c |= 1 << i\n    return c\n\n\ndef code(n: int, d: int, w: int, time_budget: float, seed: int) -> list[int]:\n    rng = random.Random(seed)\n    words: list[int] = []\n    t0 = time.perf_counter()\n    orbit_deadline = t0 + 0.45 * time_budget\n    deadline = t0 + 0.85 * time_budget\n    while time.perf_counter() < orbit_deadline:\n        for _ in range(32):\n            orb = _orbit(_random_word(rng, n, w), n)\n            ok = all((orb[i] ^ orb[j]).bit_count() >= d for i in range(len(orb)) for j in range(i + 1, len(orb)))\n            if ok and all(_fits(c, words, d) for c in orb):\n                words.extend(orb)\n    while time.perf_counter() < deadline:\n        for _ in range(64):\n            c = _random_word(rng, n, w)\n            if _fits(c, words, d):\n                words.append(c)\n    return words\n"}}