{"id":"covering-design-t8","name":"Covering designs, t = 8","family":"covering-designs","description":"Cover every 8-subset of a v-set with as few k-subsets as possible: 24 open (v, k) instances from the La Jolla Covering Repository, exact verification.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":264,"agent_timeout_seconds":900,"mutable":["cover.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":"# Covering designs, t = 8\n\n## Goal\n\nA **(v, k, t) covering design** is a list of blocks, each a k-subset of {0, ..., v-1}, such that\nevery t-subset of {0, ..., v-1} is contained in at least one block. Fewer blocks is better; the\nminimum is the covering number C(v, k, t). This pack fixes **t = 8** and hands you a set of\n(v, k) instances whose best-known coverings are *not* proven optimal.\n\n`cover.py` exposes\n\n    cover(v: int, k: int, t: int, time_budget: float, seed: int) -> list[list[int]]\n\nreturning the blocks (each a list of k distinct integers in `range(v)`; order does not matter).\nThe eval checks every block and every t-subset itself, so an invalid or incomplete covering fails\nthe whole submission rather than scoring low.\n\n## Metric\n\nThe eval runs `cover` on the fixed instance set below, each with the given time budget\n(3 s by default), verifies the covering, and reports\n\n    metric = mean over instances of  record(v, k) / blocks(v, k)\n\nso 1.0 means matching every best-known covering and anything above 1.0 on an instance is a new\nupper bound. The per-instance ratios are in the eval output (`per_instance`), and any instance you\nbeat is listed under `records_beaten`.\n\n## Records\n\nBest-known upper bounds from the La Jolla Covering Repository (Dan Gordon), table dated\n2026-01-16 (read through the Internet Archive on 2026-09-07 because the site was unreachable).\nNone of these is proven optimal; the repository's bold entries were excluded on purpose.\n\n| v | k | best-known blocks |\n|---|---|-------------------|\n| 14 | 9 | 471 |\n| 14 | 10 | 115 |\n| 15 | 9 | 789 |\n| 15 | 10 | 253 |\n| 15 | 11 | 80 |\n| 16 | 9 | 1756 |\n| 16 | 10 | 448 |\n| 16 | 11 | 167 |\n| 16 | 12 | 59 |\n| 17 | 11 | 282 |\n| 17 | 12 | 122 |\n| 17 | 13 | 42 |\n| 18 | 12 | 206 |\n| 18 | 13 | 92 |\n| 19 | 13 | 154 |\n| 19 | 14 | 74 |\n| 20 | 14 | 119 |\n| 20 | 15 | 57 |\n| 21 | 14 | 193 |\n| 21 | 15 | 96 |\n| 21 | 16 | 48 |\n| 22 | 15 | 162 |\n| 22 | 16 | 71 |\n| 22 | 17 | 40 |\n\nIf you beat one, the covering itself is the evidence: it is in your submission files' output and\nthe eval log. Send it to the repository as well (it accepts new coverings), and say so in your\nnotes so the hub can update the table.\n\n## Iterating\n\n- Start on one or two instances: `ZT_EVAL_INSTANCES=14-9,14-10 ZT_EVAL_PER_INSTANCE_SECONDS=2 python eval.py`\n  runs in a few seconds. The full set takes about 72 s of solver time plus verification.\n- Respect `time_budget` (seconds, per call). The eval kills the run if the whole set overruns.\n- Only the standard library is available. Verification enumerates C(k, t) subsets per block, so\n  returning wildly oversized coverings is slow as well as bad.\n- Classic approaches: greedy with lookahead, simulated annealing on block sets, taking known\n  algebraic coverings (finite geometries, difference families) and deleting or merging blocks, and\n  the constructions cited in the repository (Gordon, Kuperberg, Patashnik, \"New constructions for\n  covering designs\", 1995; Nurmela and Östergård's local search).\n","eval_py":"\"\"\"Eval for covering-design-t8. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nVerification is exact: every block is checked, and every t-subset of range(v) must appear in a\nblock. Environment:\n  ZT_EVAL_SEED                    seed handed to cover() (the instance set is fixed)\n  ZT_EVAL_INSTANCES               comma-separated \"v-k\" labels (default \"14-9,14-10,15-9,15-10,15-11,16-9,16-10,16-11,16-12,17-11,17-12,17-13,18-12,18-13,19-13,19-14,20-14,20-15,21-14,21-15,21-16,22-15,22-16,22-17\")\n  ZT_EVAL_PER_INSTANCE_SECONDS    time budget handed to cover() per instance (default 3)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport hashlib\nimport json\nimport os\nimport sys\nimport time\nfrom itertools import combinations\nfrom pathlib import Path\n\nT = 8\nRECORDS = {\"14-9\": 471, \"14-10\": 115, \"15-9\": 789, \"15-10\": 253, \"15-11\": 80, \"16-9\": 1756, \"16-10\": 448, \"16-11\": 167, \"16-12\": 59, \"17-11\": 282, \"17-12\": 122, \"17-13\": 42, \"18-12\": 206, \"18-13\": 92, \"19-13\": 154, \"19-14\": 74, \"20-14\": 119, \"20-15\": 57, \"21-14\": 193, \"21-15\": 96, \"21-16\": 48, \"22-15\": 162, \"22-16\": 71, \"22-17\": 40}   # \"v-k\" -> best-known number of blocks\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nINSTANCES = [x.strip() for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"14-9,14-10,15-9,15-10,15-11,16-9,16-10,16-11,16-12,17-11,17-12,17-13,18-12,18-13,19-13,19-14,20-14,20-15,21-14,21-15,21-16,22-15,22-16,22-17\").split(\",\") if x.strip()]\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"3\"))\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 verify(v: int, k: int, blocks) -> int:\n    \"\"\"Exact check. Returns the number of blocks.\"\"\"\n    if not isinstance(blocks, (list, tuple)) or not blocks:\n        raise ValueError(\"cover() must return a non-empty list of blocks\")\n    if len(blocks) > 4 * RECORDS[f\"{v}-{k}\"] + 64:\n        raise ValueError(f\"{len(blocks)} blocks is over four times the record; refusing to verify\")\n    covered = set()\n    for i, b in enumerate(blocks):\n        if not isinstance(b, (list, tuple)) or len(b) != k:\n            raise ValueError(f\"block {i} is not a list of {k} elements\")\n        try:\n            s = sorted({int(x) for x in b})\n        except (TypeError, ValueError):\n            raise ValueError(f\"block {i} has a non-integer element\")\n        if len(s) != k or s[0] < 0 or s[-1] >= v:\n            raise ValueError(f\"block {i} is not {k} distinct elements of range({v})\")\n        for sub in combinations(s, T):\n            covered.add(sub)\n    need = __import_free_comb__(v, T)\n    if len(covered) != need:\n        missing = next(c for c in combinations(range(v), T) if c not in covered)\n        raise ValueError(f\"not a covering: {len(covered)} of {need} {T}-subsets covered, e.g. {missing} is missing\")\n    return len(blocks)\n\n\ndef __import_free_comb__(n: int, r: int) -> int:\n    out = 1\n    for i in range(r):\n        out = out * (n - i) // (i + 1)\n    return out\n\n\ndef main() -> None:\n    here = Path(__file__).resolve().parent\n    check_imports(here / \"cover.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import cover as mod\n    except Exception as e:\n        fail(f\"cover.py failed to import: {e!r}\", \"compile_error\")\n    if not hasattr(mod, \"cover\"):\n        fail(\"cover.py must define cover(v, k, t, 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        v, k = (int(x) for x in lab.split(\"-\"))\n        t0 = time.time()\n        try:\n            blocks = mod.cover(v, k, T, BUDGET, seed)\n        except Exception as e:\n            fail(f\"cover({v},{k},{T}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.time() - t0\n        if elapsed > BUDGET * 1.25 + 2.0:\n            fail(f\"cover({v},{k},{T}) took {elapsed:.1f}s for a {BUDGET:.1f}s budget\", \"timeout\")\n        try:\n            n_blocks = verify(v, k, blocks)\n        except ValueError as e:\n            fail(f\"cover({v},{k},{T}): {e}\", \"wrong_answer\")\n        ratio = RECORDS[lab] / n_blocks\n        ratios.append(ratio)\n        per[lab] = {\"blocks\": n_blocks, \"record\": RECORDS[lab], \"ratio\": round(ratio, 6), \"seconds\": round(elapsed, 2)}\n        if n_blocks < RECORDS[lab]:\n            beaten.append(lab)\n        print(f\"{lab}: {n_blocks} blocks (record {RECORDS[lab]}), ratio {ratio:.4f}, {elapsed:.1f}s\", flush=True)\n    metric = sum(ratios) / len(ratios)\n    print(json.dumps({\"metric\": round(metric, 6), \"t\": T, \"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":{"cover.py":"\"\"\"Baseline for covering-design-t8: greedy covering with a little randomised lookahead.\n\nRepeatedly take an uncovered t-subset, complete it to a k-block in a few random ways, keep the\ncompletion that covers the most still-uncovered t-subsets, and mark them covered. Always valid;\nusually well above the record. Beat it.\n\"\"\"\n\nimport random\nimport time\nfrom itertools import combinations\n\n\ndef cover(v: int, k: int, t: int, time_budget: float, seed: int) -> list[list[int]]:\n    rng = random.Random(seed * 1000003 + v * 1009 + k * 101 + t)\n    deadline = time.time() + time_budget\n    uncovered = set(combinations(range(v), t))\n    universe = list(range(v))\n    blocks = []\n    while uncovered:\n        base = next(iter(uncovered))\n        rest = [x for x in universe if x not in base]\n        tries = 12 if time.time() < deadline else 1\n        best, best_gain = None, -1\n        for _ in range(tries):\n            extra = rng.sample(rest, k - t)\n            block = sorted(base + tuple(extra))\n            gain = sum(1 for sub in combinations(block, t) if sub in uncovered)\n            if gain > best_gain:\n                best, best_gain = block, gain\n        blocks.append(best)\n        for sub in combinations(best, t):\n            uncovered.discard(sub)\n    return blocks\n"}}