{"id":"circle-packing-semicircle","name":"Equal circles in a semicircle","family":"combinatorics","description":"Place n circles in the unit semicircle (radius 1, flat side on y = 0, y >= 0) 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 semicircle\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 unit semicircle (radius 1, flat side on y = 0, y >= 0) (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 `csc`, 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 250) 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-semicircle. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nGenerated by tools/packomania_import.py from https://packomania.com/csc/csc.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 unit semicircle (radius 1, flat side on y = 0, y >= 0). Source: Packomania (E. Specht),\n# https://packomania.com/csc/csc.html, fetched 2026-09-06. only small n are proven.\nRECORDS = {\n    1: 0.500000000000000000000000000000, 2: 0.414213562373095048801688724210, 3: 0.333333333333333333333333333333, 4: 0.276768653914155215717770973809, 5: 0.261203874963741442514768206917,\n    6: 0.240253073352042147999877060493, 7: 0.229142727332434474733758841965, 8: 0.205604646759568224693193969093, 9: 0.205604646759568224693193969093, 10: 0.188262725163240989137465394437,\n    11: 0.180813296439582931755295509684, 12: 0.174492346043946343810794646535, 13: 0.166736205797815901445200032195, 14: 0.163481073179191446749135004898, 15: 0.158625813390680839940422928770,\n    16: 0.151911224282959640349762191330, 17: 0.147955904479076327030170123453, 18: 0.146657116265538436708891253926, 19: 0.141008083760465126860613679638, 20: 0.139095851255553663989391355519,\n    21: 0.134390382953145787637749518707, 22: 0.131288876303240632245712664145, 23: 0.128649676452470314264601082848, 24: 0.126229454067600370337946457283, 25: 0.124584600939271017574727611620,\n    26: 0.121917986048602687422534759871, 27: 0.118570768623816923999271262653, 28: 0.117105282006001788553894567443, 29: 0.115456141678356872441258327524, 30: 0.113965603325473159881345473754,\n    31: 0.111855081493207919511660560499, 32: 0.110502488840286058184874465159, 33: 0.109835130273955511846140435159, 34: 0.107103121134104680260306094216, 35: 0.105783385012527529973759390042,\n    36: 0.104344255391410342613764288256, 37: 0.103223971063542207533249113251, 38: 0.101505935589673642686583068779, 39: 0.100515207677333030487447211782, 40: 0.099066823853548926392800107127,\n    41: 0.097539055719853182722657761532, 42: 0.096615980540062609007691011372, 43: 0.095593885556814456701722189745, 44: 0.094497292784693290216814076218, 45: 0.093666768138434146333617184258,\n    46: 0.092716338800976109854126225032, 47: 0.092056532078109381522021451718, 48: 0.091151466676148447974902892314, 49: 0.090569956715334948592803091939, 50: 0.089093785529075211414743560472,\n    51: 0.088364179559579711980137803642, 52: 0.087817433817507436917753348600, 53: 0.086833227715247571123047179187, 54: 0.086024724524272915212284435041, 55: 0.085034616681704255693300451207,\n    56: 0.084232218436600018938706310867, 57: 0.083551186608543770120847620186, 58: 0.082906284736989599064700932150, 59: 0.082127709357950922726128311941, 60: 0.081505849981968187989940587985,\n    61: 0.080994720910621467867473140675, 62: 0.080610377983216918709021033355, 63: 0.079902784728944282835789240146, 64: 0.079358884120611330517355245231, 65: 0.078767398641700702337515900681,\n    66: 0.078252927327473012271589300631, 67: 0.077610460456189716692324479792, 68: 0.077098474373952776476094769684, 69: 0.076587056192720970122201745956, 70: 0.076061046753782301041080774334,\n    71: 0.075572173580384116622662502751, 72: 0.075107368269508650166404543106, 73: 0.074391154696433685038856423279, 74: 0.073814151887090250484604115224, 75: 0.073302177703898282140658418963,\n    76: 0.072942793329582360457972160478, 77: 0.072651240855613832753602478339, 78: 0.072020041392488325131784951807, 79: 0.071569712383540241464531929381, 80: 0.071321221934945490647412579161,\n    81: 0.070782426789738040589279165590, 82: 0.070417262106960783171239785349, 83: 0.070065755199955661478379241156, 84: 0.069810787636327915246489502250, 85: 0.069236879710708157632342075042,\n    86: 0.068889696390622911874886862883, 87: 0.068438323749736608578027119208, 88: 0.068154499745286623419316957712, 89: 0.067866307455630784618687818612, 90: 0.067565909065404280434944012397,\n    91: 0.067075539860670328771868654670, 92: 0.066734287888443416751957952446, 93: 0.066309736827657244370592660887, 94: 0.065989864733662591610222934810, 95: 0.065624461214805828445766928983,\n    96: 0.065147868190103551087812916524, 97: 0.064842120563689588264432958596, 98: 0.064570058230011335736311251179, 99: 0.064355159479183188001003140181, 100: 0.064027617963500979241270325618,\n    101: 0.063858713932114389981668286256, 102: 0.063495074407009239306180667504, 103: 0.063331902707158091316996652340, 104: 0.062968389993709074665175170172, 105: 0.062745134956874283465793036261,\n    106: 0.062344645156484646343280711621, 107: 0.061996918594682384859981849864, 108: 0.061788945136324301359260655904, 109: 0.061537390875819579361104707617, 110: 0.061391600386263953508502223241,\n    111: 0.061049338306594488898369470864, 112: 0.060828833302910104790631923203, 113: 0.060514942949160794310900317560, 114: 0.060258226781778034522487238732, 115: 0.060005068920134665373887989529,\n    116: 0.059787346818217172425287959466, 117: 0.059404880382065989701249133920, 118: 0.059125781995969617040722861510, 119: 0.058839042929252045505213347427, 120: 0.058589552976949916116335253676,\n    121: 0.058398608171074243638896829099, 122: 0.058202497466008939928676787362, 123: 0.057936521442589162227686619789, 124: 0.057716970061430165940733340774, 125: 0.057576519673373672599891802255,\n    126: 0.057363112651374015289551967877, 127: 0.057171156228861998441429337793, 128: 0.057023696401740350559430156158, 129: 0.056858450373147929471207551799, 130: 0.056618980749969982541393005584,\n    131: 0.056444896325568687438174775459, 132: 0.056158328518030259864979400004, 133: 0.055939287202258638427906066672, 134: 0.055730684474279227538697124271, 135: 0.055528166810711735565664773323,\n    136: 0.055358822867300920493028004721, 137: 0.055238484395898973200967454026, 138: 0.055119941185259247683891942509, 139: 0.054860827582506637196968634678, 140: 0.054657786986961786222348533413,\n    141: 0.054474270635525176887770061360, 142: 0.054235525271534080671143823875, 143: 0.054005084581005638864411108291, 144: 0.053791339351778583437457835021, 145: 0.053625624712269202846110339348,\n    146: 0.053348124250109897128550357978, 147: 0.053133901021816626742358470423, 148: 0.053013007219523555227568453336, 149: 0.052831261764795599078621238822, 150: 0.052736861205212853159147445572,\n    151: 0.052567292135960856989219918725, 152: 0.052458588737549760657134096155, 153: 0.052276717600272380098699339472, 154: 0.052096320393393956927719442935, 155: 0.051945924431120772599258750615,\n    156: 0.051804192590392057461166005662, 157: 0.051662700565055199100219587580, 158: 0.051496533944469923890069304549, 159: 0.051335338235602895511422347968, 160: 0.051222039860754298080917216304,\n    161: 0.051034822131128688105572270067, 162: 0.050876215101825949925229181889, 163: 0.050695270124969824783703309196, 164: 0.050483162710326520798413005956, 165: 0.050373923838376980968173783043,\n    166: 0.050230766889190433625359125229, 167: 0.050155747221105973834495200259, 168: 0.050038681955291150266225434219, 169: 0.049938580982068043467491457178, 170: 0.049821392725851391486219286306,\n    171: 0.049648179120251106520322901365, 172: 0.049460977153927605801878259634, 173: 0.049314832883948881592696062737, 174: 0.049103119141474123843295117455, 175: 0.048926671215871176011511191699,\n    176: 0.048739673766468695518495009095, 177: 0.048568609843831599884174760464, 178: 0.048449849313697606607096734789, 179: 0.048367167313452924026834891491, 180: 0.048219418339379643225718916707,\n    181: 0.048142630866476295943282025530, 182: 0.048041101916841943934176071620, 183: 0.047895781453815042540193936796, 184: 0.047809800090653111600335784513, 185: 0.047711997360871162250729321919,\n    186: 0.047629163892296303139347879425, 187: 0.047459686748637229637816702444, 188: 0.047372985601548134190924734503, 189: 0.047239667869985712361972831662, 190: 0.047133350669894809336948663176,\n    191: 0.046976238840096570870994560849, 192: 0.046818965317731558348937252303, 193: 0.046677137770317288543369684687, 194: 0.046566760008289661053424740026, 195: 0.046459661361732405104955572294,\n    196: 0.046361388872078310142219261373, 197: 0.046234828663281372642005406144, 198: 0.046108443313943600471025127013, 199: 0.046011204980442141959239953984, 200: 0.045925579937177115105495919437,\n    201: 0.045805770099319394159316873640, 202: 0.045706004515499749895611354674, 203: 0.045598196784532409376636311314, 204: 0.045482723793930015186593055605, 205: 0.045405558181820127178382504680,\n    206: 0.045315606543795988629519948894, 207: 0.045158063790004260950869118175, 208: 0.045035630332158932107182880221, 209: 0.044916766538605184111365340363, 210: 0.044747780865852762778279764134,\n    211: 0.044632716935228222702022197045, 212: 0.044560724820715835484536649148, 213: 0.044484054534350586244309783047, 214: 0.044364254453869719695626841222, 215: 0.044291867298695488258218343734,\n    216: 0.044205544144813163164034613395, 217: 0.044104656297529097831634587809, 218: 0.044040449149775568573498578880, 219: 0.043960522487962605587766247053, 220: 0.043873558198413590324981740001,\n    221: 0.043786214316032567296756495927, 222: 0.043675823952184178371503973754, 223: 0.043590637025177062458420285865, 224: 0.043491195240204935987098638545, 225: 0.043422671977047805614872168786,\n    226: 0.043297949555254623393623801509, 227: 0.043178999946733505641794515837, 228: 0.043121154538565252112337247009, 229: 0.043023577180191332566906602128, 230: 0.042978286377706935054374608525,\n    231: 0.042853638751926357175186344436, 232: 0.042795962401677000409819255378, 233: 0.042668510795014132383259678858, 234: 0.042575012883230164198897048953, 235: 0.042469229728586713961237539156,\n    236: 0.042373194552835731045912102960, 237: 0.042276476563515127593717996208, 238: 0.042203298991905187595315693728, 239: 0.042105450229978638564665030000, 240: 0.041981279111216265119145591736,\n    241: 0.041892963553749135370798948264, 242: 0.041793102943229431602492189592, 243: 0.041698207016647027472114587202, 244: 0.041629312396728498086630531291, 245: 0.041524607912420698535850018212,\n    246: 0.041451599501467709544541098636, 247: 0.041369993907840121252558217311, 248: 0.041312575863900977620508259540, 249: 0.041218400962635375161307083547, 250: 0.041124237386118139971190331763,\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(1.0 - math.hypot(c[0], c[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\"csc|{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(1.0 - math.hypot(c[0], c[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 = ((-1.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"}}