{"id":"circle-packing-rectangle-100","name":"Equal circles in a 1 × 0.1 rectangle","family":"combinatorics","description":"Place n circles in the rectangle [0, 1] × [0, 0.1] as large as possible (equal). Scored against the best-known Packomania records; anything above 1.0 on an n is a new record candidate.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":600,"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":"# Equal circles in a 1 × 0.1 rectangle\n\n## Goal\n\n`pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, ...]]`: the\ncentres of `n` circles inside the rectangle [0, 1] × [0, 0.1] (2 coordinates each). All objects share one radius, which the eval derives as\n\n    r = min( distance of every centre to the boundary, half the smallest pairwise distance )\n\nYou do not return a radius; the eval derives the largest feasible one from your centres, so there\nis nothing to fudge. Make it as large as possible for every `n` you are handed.\n\n## Metric\n\nThe eval runs your `pack` on a fixed set of values, `n = 8, 13, 19, 26, 31, 37, 44, 52, 68, 85, 101, 120, 150, 200`, each with the given time\nbudget (12 s by default), validates the result, and reports\n\n    metric = mean over n of  value(n) / record(n)\n\nwhere `record(n)` is the best-known value on Packomania (Eckard Specht's table, maintained since\n2011; table `crc_100`, fetched 2026-09-06). `1.0` matches the record; above `1.0` is a new record\ncandidate, listed under `records_beaten`. A hub-verified one is worth reporting to Packomania\nwith your ledger entry as provenance.\n\nThe hub verifies with a different `seed`, so your method must be robust to its starting point.\nThe full records table (n up to 200) is in `eval.py`.\n\n## Constraints\n\n- Standard library only. No numpy, no scipy, no subprocess. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The eval kills the run if the whole set overruns.\n- Deterministic given `seed`: use `random.Random(seed)`, not the global RNG.\n- Every centre must lie inside the container. Objects may touch; they may not overlap.\n\n## Where the frontier is\n\nonly small n are proven. Above that every entry is \"best known\", found by numerical search, and Packomania's\nhistory shows improvements landing mostly at larger `n`. Budget your time per `n` deliberately;\nthe O(n²) checks and the number of local optima both grow.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Energy minimisation: treat objects as repelling points, minimise a soft overlap penalty with\n  gradient descent, then polish by maximising the minimum scaled distance directly.\n- Basin hopping / perturb-and-repolish from the current best; keep a small population.\n- Start from structured arrangements (lattices, rings, shells) as well as random.\n- Identify the binding contacts and solve the equal-distance conditions exactly for the last digits.\n- Spend more of the budget on the `n` values whose ratio is lowest.\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-rectangle-100. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nGenerated by tools/packomania_import.py from https://packomania.com/crc_100/crc.html on 2026-09-06.\n\nEnv:\n  ZT_EVAL_SEED             seed handed to pack() (the n set is fixed so scores are comparable)\n  ZT_EVAL_NS               comma-separated n values (default \"8,13,19,26,31,37,44,52,68,85,101,120,150,200\")\n  ZT_EVAL_PER_N_SECONDS    time budget handed to pack() per n (default 12)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport itertools\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\")\nNS = [int(x) for x in os.environ.get(\"ZT_EVAL_NS\", \"8,13,19,26,31,37,44,52,68,85,101,120,150,200\").split(\",\")]\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_N_SECONDS\", \"12\"))\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nEPS = 1e-9\nDIM = 2\n\n# Best-known values: equal objects in the rectangle [0, 1] × [0, 0.1]. Source: Packomania (E. Specht),\n# https://packomania.com/crc_100/crc.html, fetched 2026-09-06. only small n are proven.\nRECORDS = {\n    1: 0.050000000000000000000000000000, 2: 0.050000000000000000000000000000, 3: 0.050000000000000000000000000000, 4: 0.050000000000000000000000000000, 5: 0.050000000000000000000000000000,\n    6: 0.050000000000000000000000000000, 7: 0.050000000000000000000000000000, 8: 0.050000000000000000000000000000, 9: 0.050000000000000000000000000000, 10: 0.050000000000000000000000000000,\n    11: 0.045643942682142794248922756314, 12: 0.042312238590422353175938879282, 13: 0.039712799117777202973428794132, 14: 0.037649019478642637583367116190, 15: 0.035985190969373898484256267118,\n    16: 0.034625486140018408805415896361, 17: 0.033500838578400603540269053317, 18: 0.032560541433392497309139877392, 19: 0.031766740293079279839820752073, 20: 0.031090744862968577007014920191,\n    21: 0.030510509541279720020277464557, 22: 0.030008880996422559890264688476, 23: 0.029572358793615755933758166187, 24: 0.029190205344862249065173969274, 25: 0.028853797638876881520527924879,\n    26: 0.028556148876199049515568134776, 27: 0.028291551193424638003773960773, 28: 0.028055305821173471855154755560, 29: 0.027843517146688891162356398880, 30: 0.027652934015977579434775963773,\n    31: 0.027480826327644507247191016635, 32: 0.027324888254563587920931388531, 33: 0.027183161743543284673001225005, 34: 0.027053975592314372536891208358, 35: 0.026935896591124938045092682779,\n    36: 0.026827690080607782519907373298, 37: 0.026328369891951368505581575102, 38: 0.025834884216759061025925436657, 39: 0.025139633102022970412820515026, 40: 0.025000000000000000000000000000,\n    41: 0.024206181921367144980397128443, 42: 0.023905223877975357228585192547, 43: 0.023341132822376655414916737171, 44: 0.023045900107062934224034898706, 45: 0.022652281115903905716781996299,\n    46: 0.022349337865046844349370566234, 47: 0.022065140449831294478652996947, 48: 0.021802524111653096638341745858, 49: 0.021559612860383980147765647875, 50: 0.021334674870096596907045031346,\n    51: 0.021121768287917630599209164907, 52: 0.020926705878604717441097867673, 53: 0.020745366554348011345542420152, 54: 0.020568322012919738011897602716, 55: 0.020409946124026912175768429510,\n    56: 0.020262091292948954567326441018, 57: 0.020113279994291099443690378754, 58: 0.019983322528060620669425972499, 59: 0.019861435123634015202527181682, 60: 0.019735625997310823653651689333,\n    61: 0.019627834643297516607135083297, 62: 0.019526211384342412188488953021, 63: 0.019419727844809211699156273774, 64: 0.019329293344718676707595351906, 65: 0.019243525572863601058057120052,\n    66: 0.019135777962237830648577554978, 67: 0.019064518820557297182452668467, 68: 0.019003524769436192583731117527, 69: 0.018908734403404868456016418556, 70: 0.018840914067366362193182289851,\n    71: 0.018798561705407300270151648882, 72: 0.018714741590524303135161036449, 73: 0.018651176554292729982853590093, 74: 0.018622620163839183743350386645, 75: 0.018548177252985653525789734844,\n    76: 0.018487515307611263027733770529, 77: 0.018472689307519436147072696419, 78: 0.018404772939680528148457200140, 79: 0.018350558157125400657541681785, 80: 0.018340582007022506853433157438,\n    81: 0.018191451931196074069275438963, 82: 0.017920937409838304974430679122, 83: 0.017873831044412848954159341623, 84: 0.017610119234363481581219074743, 85: 0.017386101597307540853683259440,\n    86: 0.017338300365725516593721064059, 87: 0.017106893009055824348708259907, 88: 0.016925817276761866746190410694, 89: 0.016879890649629974636688351991, 90: 0.016690752816848198219679622654,\n    91: 0.016568554989508606121533283341, 92: 0.016494712088120664351829460321, 93: 0.016329322717461600015977310368, 94: 0.016232256714478737814121228512, 95: 0.016150028511289405172634315923,\n    96: 0.016015760496033866473673986188, 97: 0.015919736977724074240241815368, 98: 0.015862723862605694540156343922, 99: 0.015740937755705240168093954846, 100: 0.015663144827503088568054839358,\n    101: 0.015594967615502998828958195126, 102: 0.015496556090249976480348727142, 103: 0.015416585611667828117601680271, 104: 0.015374839581184214234903763068, 105: 0.015283595872613060033382602075,\n    106: 0.015218520931467203180526677929, 107: 0.015163324506615832861467460120, 108: 0.015088939675490851115769237786, 109: 0.015022871389919673503524215028, 110: 0.014990593852533876799465995172,\n    111: 0.014921709409507949793567743176, 112: 0.014866428673912000560461805318, 113: 0.014820598259898961742632627594, 114: 0.014764453337248310516219994554, 115: 0.014712407178893779024184903225,\n    116: 0.014683642209334296325030617839, 117: 0.014631743937262938163570603971, 118: 0.014584274364531196943982563135, 119: 0.014542229707683455511455566718, 120: 0.014503642710985073595858162047,\n    121: 0.014461008156356117735218101973, 122: 0.014435877138738034259914683157, 123: 0.014392960742984780826761780553, 124: 0.014356170989619735717589378037, 125: 0.014317183179559742666597018283,\n    126: 0.014291442804238161363434599840, 127: 0.014251652043788668516836390564, 128: 0.014234360386397769986695236205, 129: 0.014193221776619118052870388225, 130: 0.014170593360145863978638682100,\n    131: 0.014134113249751625688428689289, 132: 0.014117997301952982969265377973, 133: 0.014084876149575906951082799971, 134: 0.014069571531572616742152669805, 135: 0.014031684981614438213550142217,\n    136: 0.014018981859046358000350681938, 137: 0.013984567422517190001387017403, 138: 0.013975543239016882088764959512, 139: 0.013940590820770713708985018621, 140: 0.013934340491689008324039989029,\n    141: 0.013900263494566328941524683296, 142: 0.013888900144003108871552080608, 143: 0.013744176153003955133290110479, 144: 0.013709677419354838709677419355, 145: 0.013564814637607612112655411392,\n    146: 0.013537532365309930395605680409, 147: 0.013452371521141408916852044203, 148: 0.013384292765191927437868513169, 149: 0.013269221056371605017323853338, 150: 0.013241342247559432765836443228,\n    151: 0.013169107498349052320282247419, 152: 0.013108620191771324906002749531, 153: 0.013011001645917467326097465580, 154: 0.012987295376052527304559914571, 155: 0.012900628235157665249195271046,\n    156: 0.012872736228055041277622283733, 157: 0.012792339706490209293110560688, 158: 0.012766039529864515344585894886, 159: 0.012688842721739491639534489048, 160: 0.012662944319262117909426268597,\n    161: 0.012604513930292252014770281151, 162: 0.012566989295020834196649260051, 163: 0.012513585318257212263541073831, 164: 0.012480795168494501091952046526, 165: 0.012432424782923741945196355711,\n    166: 0.012388944882544956271142748114, 167: 0.012344097421758699380358446209, 168: 0.012318873184638649087924902383, 169: 0.012272116541646642210725757760, 170: 0.012240124265517043379387612989,\n    171: 0.012207980985989697832763611868, 172: 0.012167771090766040607278995700, 173: 0.012129382441543674295802541789, 174: 0.012098837299164698238747934857, 175: 0.012065933672360879339372321953,\n    176: 0.012038570285517179717868162747, 177: 0.012002966070044154533246541186, 178: 0.011982076084663004188176512814, 179: 0.011945803735386947079030059409, 180: 0.011920000563795392666667856272,\n    181: 0.011896666898546495241106554826, 182: 0.011864350936501813428444058915, 183: 0.011835306977328539887453658705, 184: 0.011813075320400887766444829524, 185: 0.011783418200666870341738557327,\n    186: 0.011764617628684004918761962819, 187: 0.011740977667035736248150840373, 188: 0.011722577193654503671390949205, 189: 0.011690734562102845987251073139, 190: 0.011672722664446277495680741400,\n    191: 0.011650039561364683323127254589, 192: 0.011629592422206074864981488973, 193: 0.011608204767814804108674519429, 194: 0.011585362521278158905864878296, 195: 0.011567953195348693221249398036,\n    196: 0.011550535051345135885970070871, 197: 0.011534585223056493945459212696, 198: 0.011519937537794770081885667091, 199: 0.011492336589362946074263064144, 200: 0.011479462700246063514159511808,\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 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 boundary(c) -> float:\n    \"\"\"Distance from centre c to the container boundary; negative outside.\"\"\"\n    return min(c[0], 1 - c[0], c[1], 0.1 - c[1])\n\n\ndef weight(i: int) -> float:\n    \"\"\"Radius weight of object i (1-based); the eval derives the common scale s, r_i = weight(i) * s.\"\"\"\n    return 1.0\n\n\ndef value_of(centres: list, n: int) -> float:\n    if not isinstance(centres, (list, tuple)) or len(centres) != n:\n        fail(f\"pack({n}) must return {n} centres\", \"wrong_answer\")\n    pts = []\n    for c in centres:\n        try:\n            p = tuple(float(v) for v in c)\n        except Exception:\n            fail(f\"pack({n}) returned a non-point {c!r}\", \"wrong_answer\")\n        if len(p) != DIM or not all(math.isfinite(v) for v in p):\n            fail(f\"pack({n}) returned a point that is not {DIM}-D and finite: {c!r}\", \"wrong_answer\")\n        if boundary(p) < -EPS:\n            fail(f\"pack({n}) placed a centre outside the container: {p}\", \"wrong_answer\")\n        pts.append(p)\n    w = [weight(i + 1) for i in range(n)]\n    s = min(max(boundary(p), 0.0) / w[i] for i, p in enumerate(pts))   # upper bound from the walls\n    if s <= EPS:\n        fail(f\"pack({n}) has a centre on the boundary (scale={s})\", \"wrong_answer\")\n    # Any pair that limits the scale below s has distance < (w_i + w_j) s <= 2 wmax s, so it lies\n    # in the same or an adjacent cell of a grid with that spacing. Expected O(n) instead of O(n^2).\n    cell = 2.0 * max(w) * s\n    grid = {}\n    for idx, p in enumerate(pts):\n        key = tuple(int(math.floor(v / cell)) for v in p)\n        grid.setdefault(key, []).append(idx)\n    offsets = list(itertools.product((-1, 0, 1), repeat=DIM))\n    for key, members in grid.items():\n        for off in offsets:\n            nb = tuple(k + o for k, o in zip(key, off))\n            if nb < key or nb not in grid:\n                continue\n            others = grid[nb]\n            for i in members:\n                pi = pts[i]\n                for j in others:\n                    if nb == key and j <= i:\n                        continue\n                    pj = pts[j]\n                    d = math.sqrt(sum((a - b) * (a - b) for a, b in zip(pi, pj))) / (w[i] + w[j])\n                    if d < s:\n                        s = d\n    if s <= EPS:\n        fail(f\"pack({n}) has coincident centres (scale={s})\", \"wrong_answer\")\n    return w[n - 1] * s   # the largest object's radius (equal case: the common radius)\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    ns = sorted(set(NS))\n    for n in ns:\n        if n not in RECORDS:\n            fail(f\"no Packomania record for n={n}\", \"error\")\n    seed_int = random.Random(f\"crc_100|{SEED}\").getrandbits(32)\n    per_n, beaten = {}, []\n    t_all = time.perf_counter()\n    for n in ns:\n        t0 = time.perf_counter()\n        try:\n            centres = 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 > 1.25 * BUDGET + 3:\n            fail(f\"pack({n}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        v = value_of(centres, n)\n        ratio = v / RECORDS[n]\n        per_n[n] = {\"value\": round(v, 12), \"record\": RECORDS[n], \"ratio\": round(ratio, 6), \"seconds\": round(elapsed, 2)}\n        if v > RECORDS[n] + 1e-9:\n            beaten.append(n)\n    metric = sum(x[\"ratio\"] for x in per_n.values()) / len(per_n)\n    print(json.dumps({\"metric\": round(metric, 6), \"ns\": ns, \"per_n\": per_n, \"records_beaten\": beaten,\n                      \"total_seconds\": round(time.perf_counter() - t_all, 1)}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"pack.py":"\"\"\"Baseline: a lattice of candidate points inside the container, spacing found by bisection so\nthat at least n fit. Deliberately naive; scores well below the records. Beat it.\"\"\"\n\nimport itertools\nimport math\n\nDIM = 2\n\n\ndef _boundary(c):\n    return min(c[0], 1 - c[0], c[1], 0.1 - c[1])\n\n\ndef _weight(i):\n    return 1.0\n\n\ndef _lattice(n, r):\n    \"\"\"Cubic lattice points at spacing 2r whose distance to the boundary is at least r.\"\"\"\n    lo, hi = ((0.0,) * DIM, (1.0,) * DIM)\n    step = 2.0 * r\n    axes = []\n    for d in range(DIM):\n        k = int((hi[d] - lo[d]) / step) + 1\n        axes.append([lo[d] + r + i * step for i in range(k)])\n    pts = [p for p in itertools.product(*axes) if _boundary(p) >= r]\n    return pts\n\n\ndef pack(n, time_budget, seed):\n    # treat every object as the largest one when choosing the lattice spacing\n    wmax = max(_weight(i + 1) for i in range(n))\n    # find a feasible spacing by halving, then bisect between it and the last infeasible one\n    a = 1.0\n    while len(_lattice(n, a * wmax)) < n and a > 1e-9:\n        a /= 2\n    b = 2 * a\n    for _ in range(40):\n        m = (a + b) / 2\n        if len(_lattice(n, m * wmax)) >= n:\n            a = m\n        else:\n            b = m\n    pts = _lattice(n, a * wmax)\n    pts.sort(key=lambda p: -_boundary(p))   # keep the most interior points\n    return [tuple(p) for p in pts[:n]]\n"}}