Covering designs, t = 3

# Covering designs, t = 3 ## Goal A **(v, k, t) covering design** is a list of blocks, each a k-subset of {0, ..., v-1}, such that every t-subset of {0, ..., v-1} is contained in at least one block. Fewer blocks is better; the minimum is the covering number C(v, k, t). This pack fixes **t = 3** and hands you a set of (v, k) instances whose best-known coverings are *not* proven optimal. `cover.py` exposes cover(v: int, k: int, t: int, time_budget: float, seed: int) -> list[list[int]] returning the blocks (each a list of k distinct integers in `range(v)`; order does not matter). The eval checks every block and every t-subset itself, so an invalid or incomplete covering fails the whole submission rather than scoring low. ## Metric The eval runs `cover` on the fixed instance set below, each with the given time budget (3 s by default), verifies the covering, and reports metric = mean over instances of record(v, k) / blocks(v, k) so 1.0 means matching every best-known covering and anything above 1.0 on an instance is a new upper bound. The per-instance ratios are in the eval output (`per_instance`), and any instance you beat is listed under `records_beaten`. ## Records Best-known upper bounds from the La Jolla Covering Repository (Dan Gordon), table dated 2026-01-16 (read through the Internet Archive on 2026-09-07 because the site was unreachable). None of these is proven optimal; the repository's bold entries were excluded on purpose. | v | k | best-known blocks | |---|---|-------------------| | 13 | 6 | 21 | | 14 | 5 | 43 | | 15 | 5 | 55 | | 16 | 7 | 24 | | 17 | 8 | 18 | | 18 | 9 | 16 | | 18 | 10 | 12 | | 18 | 11 | 10 | | 19 | 4 | 258 | | 20 | 12 | 10 | | 22 | 13 | 11 | | 23 | 14 | 10 | | 25 | 15 | 10 | | 27 | 16 | 10 | | 28 | 17 | 10 | | 30 | 18 | 10 | | 31 | 4 | 1165 | | 32 | 19 | 11 | | 33 | 20 | 10 | | 35 | 21 | 10 | | 36 | 22 | 10 | | 37 | 23 | 9 | | 39 | 24 | 9 | | 41 | 25 | 9 | If you beat one, the covering itself is the evidence: it is in your submission files' output and the eval log. Send it to the repository as well (it accepts new coverings), and say so in your notes so the hub can update the table. ## Iterating - Start on one or two instances: `ZT_EVAL_INSTANCES=13-6,14-5 ZT_EVAL_PER_INSTANCE_SECONDS=2 python eval.py` runs in a few seconds. The full set takes about 72 s of solver time plus verification. - Respect `time_budget` (seconds, per call). The eval kills the run if the whole set overruns. - Only the standard library is available. Verification enumerates C(k, t) subsets per block, so returning wildly oversized coverings is slow as well as bad. - Classic approaches: greedy with lookahead, simulated annealing on block sets, taking known algebraic coverings (finite geometries, difference families) and deleting or merging blocks, and the constructions cited in the repository (Gordon, Kuperberg, Patashnik, "New constructions for covering designs", 1995; Nurmela and Östergård's local search).