{"id":"golomb-rulers","name":"Golomb rulers","family":"additive-combinatorics","description":"Place m marks on a ruler so that every pairwise distance is different, with the ruler as short as possible: m = 29..40, the first twelve orders beyond the proven range (OGR-28, 2022), scored against the best-known lengths from Shearer's and Rokicki-Dogon's projective/affine plane constructions. Exact verification.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["ruler.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":"# Golomb rulers\n\n## Goal\n\nA **Golomb ruler** with `m` marks is a set of `m` integers whose `m(m-1)/2` pairwise differences\nare all distinct. Its length is the largest mark minus the smallest. The shortest possible length\n`G(m)` (OEIS A003022) is known for `m ≤ 28`: the last five were settled by distributed.net's OGR\nproject, OGR-28 (length 585) finishing in November 2022 after eight years. For `m ≥ 29` the best\nrulers known all come from the finite-field constructions of Singer (1938, projective plane),\nBose–Chowla (affine plane) and Ruzsa; nobody knows whether they are optimal. Here you build rulers\nfor `m = 29 .. 40` as short as you can.\n\n`ruler.py` exposes\n\n    ruler(m: int, time_budget: float, seed: int) -> list[int]\n\nreturning the `m` marks (distinct non-negative ints, any order; the eval subtracts the smallest, so\nthe ruler need not start at 0). Verification is exact: every pairwise difference is recomputed and\nmust be distinct. A wrong ruler fails the whole submission rather than scoring low.\n\n## Metric\n\nThe eval runs `ruler` on the fixed set `m = 29, 30, ..., 40`, each with the given time budget\n(8 s by default), verifies the ruler, and reports\n\n    metric = mean over m of  record_length(m) / length(m)\n\nso 1.0 means matching every best-known ruler and anything above 1.0 on an `m` is a new record.\nPer-instance detail (length, record, ratio, seconds) is in `per_instance`; any `m` you beat is\nlisted under `records_beaten`, and every ruler's marks are printed in the log. `ZT_EVAL_SEED` only\nchanges the `seed` handed to your solver.\n\n## Records\n\nBest-known lengths from James B. Shearer's \"Table of lengths of shortest known Golomb rulers\"\n(IBM Research, 1998; archived at\nhttps://web.archive.org/web/20170625090514/http://www.research.ibm.com/people/s/shearer/grtab.html)\nand, agreeing on every row, the data file behind Tomas Rokicki and Gil Dogon's \"Larger Golomb\nrulers\" (G4G12, 2015; http://cube20.org/golomb/, file `golomb-all-00`, which also gives the\nconstruction and the prime power `q` used). Rokicki and Dogon exhaustively re-ran all three\nconstructions for every `q` and every multiplier, so these are the shortest rulers those\nconstructions can give; they offer a reward for beating any of their lengths from 36 marks on.\n`m ≤ 28` is proven optimal (Wikipedia's Golomb ruler table, distributed.net OGR-24 .. OGR-28).\n**None of the lengths below is proven optimal.**\n\n| m | best-known length | construction | proven |\n|---|---|---|---|\n| 29 | 623 | projective plane, q = 29 | no |\n| 30 | 680 | projective plane, q = 29 | no |\n| 31 | 747 | projective plane, q = 31 | no |\n| 32 | 784 | projective plane, q = 31 | no |\n| 33 | 859 | projective plane, q = 32 | no |\n| 34 | 938 | projective plane, q = 37 | no |\n| 35 | 987 | affine plane, q = 37 | no |\n| 36 | 1005 | affine plane, q = 37 | no |\n| 37 | 1099 | projective plane, q = 37 | no |\n| 38 | 1146 | projective plane, q = 37 | no |\n| 39 | 1252 | projective plane, q = 41 | no |\n| 40 | 1282 | affine plane, q = 41 | no |\n\nRokicki and Dogon note that only six small orders have optimal rulers shorter than any\nconstruction gives; whether that ever happens again is the open question. Beating an entry means\na ruler shorter than every Singer, Bose–Chowla and Ruzsa ruler with that many marks.\n\nIf you beat one, the marks are the evidence: they are in the eval log. Say so in your notes so the\nhub can update the table and tell distributed.net and Rokicki–Dogon.\n\n## Iterating\n\n- Start on one or two orders: `ZT_EVAL_INSTANCES=29,30 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 instant.\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 rulers longer than four times the record.\n- All three constructions give *modular* Golomb rulers (distinct differences mod `M`), and the\n  recipe is the same: build the modular set, multiply by every unit `k` mod `M` (each product is\n  again a modular ruler), sort, and take the shortest window of `m` consecutive marks around the\n  circle; also drop marks from sets with more than `m` elements.\n  - Ruzsa (the baseline): prime `p`, primitive root `g`; `{ p·i + (p-1)·g^i mod p(p-1) : 1 ≤ i < p }`\n    has `p-1` marks mod `p(p-1)`.\n  - Bose–Chowla (affine plane): prime power `q`, `θ` a primitive element of `GF(q²)`;\n    `{ a : θ^a - θ ∈ GF(q) }` has `q` marks mod `q²-1`.\n  - Singer (projective plane): `θ` primitive in `GF(q³)`; the exponents `a` whose `θ^a` lies in a\n    fixed 2-dimensional `GF(q)`-subspace of `GF(q³)` form `q+1` marks mod `q²+q+1`, a perfect\n    difference set. Prime `q` needs only integer arithmetic mod `q` with a cubic irreducible;\n    `q = 32` (the 33-mark record) needs `GF(2^15)`.\n  Every record above is one of these with the `q` shown; reproducing them is the first milestone,\n  and a search over `q`, multiplier and window is small enough to finish within the budget.\n- To beat a record you need something else: local search from a construction (move one mark,\n  repair collisions), branch and bound with the distance bitmap (how OGR is searched, hopeless\n  alone at these sizes but useful to close a nearly-complete ruler), or truncating/extending a\n  construction ruler with a few free marks.\n\nWrite one honest line in `NOTES.md`: the idea, and which orders 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 golomb-rulers. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nVerification is exact: the marks must be m distinct non-negative integers and all m(m-1)/2 pairwise\ndifferences must be distinct. Length = max - min is recomputed from the marks; nothing the solver\nreports is trusted. Environment:\n  ZT_EVAL_SEED                    seed handed to ruler() (the instance set is fixed)\n  ZT_EVAL_INSTANCES               comma-separated mark counts m (default \"29,30,...,40\")\n  ZT_EVAL_PER_INSTANCE_SECONDS    time budget handed to ruler() per instance (default 8)\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 length, m -> length. Sources (agreeing on every row): J. B. Shearer, \"Table of lengths of\n# shortest known Golomb rulers\" (IBM Research 1998, archived 2017-06-25 at web.archive.org), and the\n# golomb-all-00 data file of T. Rokicki & G. Dogon, \"Larger Golomb rulers\" (G4G12 2015,\n# http://cube20.org/golomb/), read 2026-09-07. All come from Singer (projective plane) or Bose-Chowla\n# (affine plane) constructions. Optimal lengths are proven only for m <= 28 (distributed.net OGR-28,\n# 2022); none of these is.\nRECORDS = {\"29\": 623, \"30\": 680, \"31\": 747, \"32\": 784, \"33\": 859, \"34\": 938, \"35\": 987, \"36\": 1005,\n           \"37\": 1099, \"38\": 1146, \"39\": 1252, \"40\": 1282}\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nINSTANCES = [x.strip() for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"29,30,31,32,33,34,35,36,37,38,39,40\").split(\",\") if x.strip()]\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"8\"))\nMAX_FACTOR = 4   # refuse rulers longer than 4x the record; they score below 0.25 anyway\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(m: int, marks, max_length: int) -> tuple[int, list[int]]:\n    \"\"\"Exact check. Returns (length, sorted marks shifted to start at 0).\"\"\"\n    if not isinstance(marks, (list, tuple)) or len(marks) != m:\n        raise ValueError(f\"ruler must return a list of exactly {m} marks\")\n    S = []\n    for x in marks:\n        if isinstance(x, bool) or not isinstance(x, int):\n            raise ValueError(f\"mark {x!r} is not an int\")\n        if x < 0:\n            raise ValueError(f\"mark {x} is negative\")\n        S.append(x)\n    if len(set(S)) != m:\n        raise ValueError(\"marks are not distinct\")\n    S.sort()\n    lo = S[0]\n    S = [x - lo for x in S]\n    length = S[-1]\n    if length > max_length:\n        raise ValueError(f\"length {length} is more than the {max_length} this eval accepts\")\n    seen = set()\n    for i in range(m):\n        si = S[i]\n        for j in range(i + 1, m):\n            d = S[j] - si\n            if d in seen:\n                raise ValueError(f\"distance {d} is measured twice (not a Golomb ruler)\")\n            seen.add(d)\n    return length, S\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"ruler.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import ruler as mod  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import ruler.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(mod, \"ruler\"):\n        fail(\"ruler.py must define ruler(m, 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        m = int(lab)\n        t0 = time.time()\n        try:\n            marks = mod.ruler(m, BUDGET, seed)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"ruler({m}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.time() - t0\n        if elapsed > BUDGET * 1.25 + 3.0:\n            fail(f\"ruler({m}) took {elapsed:.1f}s for a {BUDGET:.1f}s budget\", \"timeout\")\n        try:\n            length, S = verify(m, marks, MAX_FACTOR * RECORDS[lab])\n        except ValueError as e:\n            fail(f\"ruler({m}): {e}\", \"wrong_answer\")\n        ratio = RECORDS[lab] / length\n        ratios.append(ratio)\n        per[lab] = {\"length\": length, \"record\": RECORDS[lab], \"ratio\": round(ratio, 6), \"seconds\": round(elapsed, 2)}\n        if length < RECORDS[lab]:\n            beaten.append(lab)\n        print(f\"m={m}: length {length} (record {RECORDS[lab]}), ratio {ratio:.4f}, {elapsed:.1f}s\", flush=True)\n        print(f\"m={m} marks: {S}\", 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":{"ruler.py":"\"\"\"Baseline: Ruzsa's construction. For a prime p with primitive root g, the p-1 residues\np*i + (p-1)*g^i (mod p(p-1)) have distinct pairwise differences mod p(p-1); multiplying by a unit\nkeeps that, so the shortest run of m consecutive marks around the circle, over the first two primes\nabove m and a seeded sample of multipliers, is a Golomb ruler. Scores about 0.9 of the records\n(which come from the Singer and Bose-Chowla constructions). Beat it.\"\"\"\n\nimport math\nimport random\nimport time\n\nMULTIPLIERS = 64   # per prime; deterministic given seed, well inside the budget\n\n\ndef ruler(m: int, time_budget: float, seed: int) -> list[int]:\n    rng = random.Random(seed)\n    t0 = time.time()\n    best = None\n    p = m + 1\n    for _ in range(2):\n        while not is_prime(p):\n            p += 1\n        g = primitive_root(p)\n        M = p * (p - 1)\n        base = [(p * i + (p - 1) * pow(g, i, p)) % M for i in range(1, p)]\n        units = [k for k in range(1, M) if math.gcd(k, M) == 1]\n        rng.shuffle(units)\n        for k in units[:MULTIPLIERS]:\n            if time.time() - t0 > 0.8 * time_budget:\n                break\n            s = sorted(x * k % M for x in base)\n            ext = s + [x + M for x in s]           # unwrap the circle\n            for i in range(len(s)):\n                length = ext[i + m - 1] - ext[i]\n                if best is None or length < best[0]:\n                    best = (length, [x - ext[i] for x in ext[i:i + m]])\n        p += 1\n    return best[1]\n\n\ndef is_prime(p: int) -> bool:\n    return p >= 2 and all(p % q for q in range(2, math.isqrt(p) + 1))\n\n\ndef primitive_root(p: int) -> int:\n    phi, x, q, factors = p - 1, p - 1, 2, []\n    while q * q <= x:\n        if x % q == 0:\n            factors.append(q)\n            while x % q == 0:\n                x //= q\n        q += 1\n    if x > 1:\n        factors.append(x)\n    for g in range(2, p):\n        if all(pow(g, phi // f, p) != 1 for f in factors):\n            return g\n    return 1\n"}}