{"id":"circle-packing-sum-radii","name":"Circles in a square, maximum total radius","family":"combinatorics","description":"The AlphaEvolve packing problem: place n circles of any sizes in the unit square to maximise the sum of their radii, for n = 26 and n = 32. Scored against the best-known sums.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["pack.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":"# Circles in a square, maximum total radius\n\n## Goal\n\n`pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float]]`:\n`n` circles `(x, y, r)` inside the unit square, any radii, no overlaps. Maximise `sum(r)`.\n\nThis is the problem Google DeepMind's AlphaEvolve reported on in May 2025: for `n = 26` it raised\nthe best-known sum from 2.634 to 2.635, and for `n = 32` from 2.936 to 2.937. Those two instances\nare the whole benchmark here. Beat either sum and you have a record candidate.\n\n## Metric\n\n    metric = mean over n in {26, 32} of  sum_r(n) / best_known(n)\n\nThe eval validates every circle (inside the square, pairwise non-overlapping with a tolerance of\n1e-9) before it sums anything. A wrong answer on either `n` is a failed run. `ZT_EVAL_SEED` only\nchanges the `seed` handed to your solver, so your method must be robust to its starting point.\n\n## Constraints\n\n- Standard library only. No numpy, no scipy. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call).\n- Deterministic given `seed`: use `random.Random(seed)`.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- This is a continuous optimisation with a combinatorial skeleton: which circles touch which.\n  Good solutions mix a few large circles with many small ones filling gaps. Enumerate skeletons,\n  optimise radii and positions for each.\n- Penalty-method gradient descent on `-sum(r) + w * overlaps`, with `w` ramped up, then a final\n  feasibility projection (shrink overlapping circles slightly rather than moving them).\n- Start from the known good layouts for equal circles and let radii diverge.\n- Perturb the current best, re-optimise, keep if better: the loop that produced AlphaEvolve's\n  result was exactly this, run for a long time. Use your whole budget.\n\nWrite one honest line in `NOTES.md`: the idea, and which `n` 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 circle-packing-sum-radii. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED             seed handed to pack()\n  ZT_EVAL_PER_N_SECONDS    time budget per n (default 40)\n  ZT_EVAL_NS               comma-separated n values (default \"26,32\")\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_N_SECONDS\", \"40\"))\nNS = [int(x) for x in os.environ.get(\"ZT_EVAL_NS\", \"26,32\").split(\",\")]\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nEPS = 1e-9\n\n# Best-known sum of radii. Source: AlphaEvolve (Novikov et al., May 2025), which improved the\n# prior bests of 2.634 and 2.936. Update when a hub-verified submission exceeds these.\nRECORDS = {26: 2.6358627564136983, 32: 2.937944}\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 pack.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\n\ndef validate(circles: list, n: int) -> float:\n    if not isinstance(circles, (list, tuple)) or len(circles) != n:\n        fail(f\"pack({n}) must return {n} circles\", \"wrong_answer\")\n    cs = []\n    for c in circles:\n        try:\n            x, y, r = float(c[0]), float(c[1]), float(c[2])\n        except Exception:\n            fail(f\"pack({n}) returned a non-circle {c!r}\", \"wrong_answer\")\n        if not all(map(math.isfinite, (x, y, r))) or r <= 0:\n            fail(f\"pack({n}) returned a circle with non-positive or non-finite radius\", \"wrong_answer\")\n        if x - r < -EPS or x + r > 1 + EPS or y - r < -EPS or y + r > 1 + EPS:\n            fail(f\"pack({n}) placed a circle outside the unit square: ({x}, {y}, r={r})\", \"wrong_answer\")\n        cs.append((x, y, r))\n    for i in range(n):\n        xi, yi, ri = cs[i]\n        for j in range(i + 1, n):\n            xj, yj, rj = cs[j]\n            if math.hypot(xi - xj, yi - yj) < ri + rj - EPS:\n                fail(f\"pack({n}): circles {i} and {j} overlap\", \"wrong_answer\")\n    return sum(c[2] for c in cs)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"pack.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import pack as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import pack.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"pack\"):\n        fail(\"pack.py must define pack(n, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"sumr|{SEED}\").getrandbits(32)\n    per_n, beaten = {}, []\n    for n in NS:\n        if n not in RECORDS:\n            fail(f\"no record for n={n}\", \"error\")\n        t0 = time.perf_counter()\n        try:\n            circles = cand.pack(n, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"pack({n}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 2.0 * BUDGET + 5:\n            fail(f\"pack({n}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        s = validate(circles, n)\n        per_n[n] = {\"sum_r\": round(s, 10), \"record\": RECORDS[n], \"ratio\": round(s / RECORDS[n], 6), \"seconds\": round(elapsed, 2)}\n        if s > RECORDS[n] + 1e-9:\n            beaten.append(n)\n    metric = sum(v[\"ratio\"] for v in per_n.values()) / len(per_n)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_n\": per_n, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"pack.py":"\"\"\"Baseline: equal circles on a square grid. Scores about 0.8-0.9 of the records. Beat it.\"\"\"\n\nimport math\n\n\ndef pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float]]:\n    k = math.ceil(math.sqrt(n))\n    r = 1.0 / (2 * k)\n    out = []\n    for i in range(k):\n        for j in range(k):\n            if len(out) < n:\n                out.append(((j + 0.5) / k, (i + 0.5) / k, r))\n    return out\n"}}