{"id":"circle-packing-rectangle-200","name":"Equal circles in a 1 × 0.2 rectangle","family":"combinatorics","description":"Place n circles in the rectangle [0, 1] × [0, 0.2] 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.2 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.2] (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_200`, 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 347) 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-200. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nGenerated by tools/packomania_import.py from https://packomania.com/crc_200/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.2]. Source: Packomania (E. Specht),\n# https://packomania.com/crc_200/crc.html, fetched 2026-09-06. only small n are proven.\nRECORDS = {\n    1: 0.100000000000000000000000000000, 2: 0.100000000000000000000000000000, 3: 0.100000000000000000000000000000, 4: 0.100000000000000000000000000000, 5: 0.100000000000000000000000000000,\n    6: 0.084524052577349764562923561227, 7: 0.075077640500378546463487396284, 8: 0.068958825895264200037012280989, 9: 0.064797003745975065702681339008, 10: 0.061850317545375803602987430032,\n    11: 0.059693491089449820242245977452, 12: 0.058070323909482229503460718766, 13: 0.056819747776422020642924518493, 14: 0.055836716635766173763732845739, 15: 0.055050511413105583784558276553,\n    16: 0.054412188832468264872991509398, 17: 0.053887046240469780235174544026, 18: 0.052886076962755087244445810439, 19: 0.050516276701207074309823924356, 20: 0.050000000000000000000000000000,\n    21: 0.047148169098807494744715475145, 22: 0.046068938270063788377973868859, 23: 0.044304881270818043187669315550, 24: 0.043493177134262624676914080897, 25: 0.042269960955124823410608895093,\n    26: 0.041669750984812399697557708378, 27: 0.040801395066564593485098624771, 28: 0.040316555991033377499214845493, 29: 0.039722870247268030405054363364, 30: 0.039233338586232517375172577515,\n    31: 0.038839455689618423398312547549, 32: 0.038487051145727202116114240103, 33: 0.038064941614196181081443283241, 34: 0.037778569938339541578791725201, 35: 0.037613330478421455521863720079,\n    36: 0.037268501951520713452221634031, 37: 0.037018969085496882770975369672, 38: 0.036957211574933433058655583170, 39: 0.036683735733267490578414877458, 40: 0.035938232559818867487942312885,\n    41: 0.035747662088825697908318683246, 42: 0.034834280165172963023606057020, 43: 0.033958773032007974007889262796, 44: 0.033756830962913366790012090851, 45: 0.033333333333333333333333333333,\n    46: 0.032596219936162102470717868142, 47: 0.032262319368807558355748046949, 48: 0.031741816059838887383237003268, 49: 0.031376373296674426833354747845, 50: 0.031176464698490098904180455769,\n    51: 0.030768153182597123182619923435, 52: 0.030497677357300217794848863406, 53: 0.030272848686719203069348012687, 54: 0.029984018689822097418773875547, 55: 0.029740240386981680892591733039,\n    56: 0.029616937785747821994635221242, 57: 0.029385881769402513183695232202, 58: 0.029190054222239494253979220981, 59: 0.029017737744080922979966436948, 60: 0.028871754277476068519829366314,\n    61: 0.028697122670198869263698727823, 62: 0.028617382523073494241674128842, 63: 0.028443473954043213802453498439, 64: 0.028345645458148414677783947821, 65: 0.028201133568197784273773044231,\n    66: 0.028139143063145233484305339610, 67: 0.027993448514499621332879920743, 68: 0.027956977538776886207519482085, 69: 0.027812487772841806267220477793, 70: 0.027777800548174088041633491128,\n    71: 0.027279504769527760019684098383, 72: 0.027109714466787749343476270481, 73: 0.026704745881396873341022844175, 74: 0.026475820607740561657212822669, 75: 0.026341555891749357970839864565,\n    76: 0.025974590752105054609119829142, 77: 0.025636928895985156395012313684, 78: 0.025532079059729030689171789773, 79: 0.025288095148916152906272276737, 80: 0.025130533303249093564651149639,\n    81: 0.024961590336989002183904093053, 82: 0.024777535620545268229346529892, 83: 0.024596236628240359656645212368, 84: 0.024486787539065672300089422241, 85: 0.024324423413740596101729963680,\n    86: 0.024197674598329396477495869713, 87: 0.024054996135079111387690298150, 88: 0.023964152169326008376353025628, 89: 0.023819794994046352405071851165, 90: 0.023720963436127793299365231197,\n    91: 0.023626150640801775532889659048, 92: 0.023514548846143155349208012886, 93: 0.023413606816332240363302717861, 94: 0.023318676271278656602769822706, 95: 0.023239142833345730138846468768,\n    96: 0.023170725042556317811729756593, 97: 0.023101069888288189047557560049, 98: 0.023039875075589540163771334181, 99: 0.022927738166668222058309077749, 100: 0.022881112120071583326585408723,\n    101: 0.022790971947177767038369312299, 102: 0.022754152336011154859252561543, 103: 0.022718029191773014002652894110, 104: 0.022620050782971421088872971066, 105: 0.022586342535343294479035018867,\n    106: 0.022509898445356309716209131129, 107: 0.022481657186936888078514247253, 108: 0.022470940523537839138250918772, 109: 0.022301955382957583086584992721, 110: 0.022236615073398454529071990528,\n    111: 0.021939239930453824808338400718, 112: 0.021831637708329681664612111211, 113: 0.021791488616319364922145546648, 114: 0.021495847111172447340057809474, 115: 0.021425201345660810658802759987,\n    116: 0.021249279743191863994701106276, 117: 0.021134661204481532060747479380, 118: 0.021084204421255848374667299304, 119: 0.020883659859864774035782546227, 120: 0.020813957282804213714093530819,\n    121: 0.020689523049209363956781918076, 122: 0.020586014716687988398375963047, 123: 0.020553007096033781907577990351, 124: 0.020394425835144745237345723336, 125: 0.020322511577886842178394769803,\n    126: 0.020226752846638489501213877478, 127: 0.020155021079308652041673091027, 128: 0.020102874050706594697191685189, 129: 0.020001905161608479177554786547, 130: 0.019941052552694549098510509253,\n    131: 0.019859770160478376100973220711, 132: 0.019789101289386861357901992012, 133: 0.019745036704881803256928217024, 134: 0.019690055618071636154123936171, 135: 0.019624651023863632144418726831,\n    136: 0.019559084400308558537495305988, 137: 0.019494770697918633233953144100, 138: 0.019474501536030627368840800306, 139: 0.019402722688937781637879584706, 140: 0.019349767227858497843590697917,\n    141: 0.019299864778513010852351117849, 142: 0.019253496896377514551216946028, 143: 0.019214940160731447463968464624, 144: 0.019172069820366453445389934816, 145: 0.019124794027687288752685154276,\n    146: 0.019089088077777755809559749262, 147: 0.019061390214171943514413227395, 148: 0.018998643430656269386221250424, 149: 0.018980269061929650669912513182, 150: 0.018961762330914637085159860092,\n    151: 0.018897984682813392597327561906, 152: 0.018880546742273365892267891690, 153: 0.018869889939550259644952602946, 154: 0.018807774894311212657423312895, 155: 0.018791120418197754850544438093,\n    156: 0.018784755819323387214698267312, 157: 0.018631505479996644649543668273, 158: 0.018555601980318251752435181389, 159: 0.018529472433616946494800034439, 160: 0.018376963609636770120054985487,\n    161: 0.018270631498207221833658705895, 162: 0.018242069458436795322421020343, 163: 0.018102731366781063787019985970, 164: 0.018016918469994105566898354588, 165: 0.017992306331201388048750009579,\n    166: 0.017900384796189156346517358394, 167: 0.017794178251731241958818268657, 168: 0.017769630920114218155094687843, 169: 0.017670959048961068095108886507, 170: 0.017597614131897344459899261797,\n    171: 0.017570284086487097500356357497, 172: 0.017488659220934484570886930808, 173: 0.017413818330824168591939370427, 174: 0.017389317949191233068268440270, 175: 0.017327936686768345534722978176,\n    176: 0.017257892104308169854179797154, 177: 0.017227550349753667028417565356, 178: 0.017168993872479793767858620284, 179: 0.017118136168072994223091779177, 180: 0.017084667304732212817538035832,\n    181: 0.017037719043471376413552420262, 182: 0.017002321952486092089707934491, 183: 0.016958986068433382988417319663, 184: 0.016926341702645105372235547282, 185: 0.016867959461749889103972291658,\n    186: 0.016851144243951518985002890329, 187: 0.016799439702926256548799225343, 188: 0.016754126269586444381562096751, 189: 0.016735599450278746246069842140, 190: 0.016687805470685709619201234327,\n    191: 0.016664264048079061478220829904, 192: 0.016630409160404547470617339942, 193: 0.016598725533982748946071190444, 194: 0.016565012376738234107830373035, 195: 0.016534560573301617772030844863,\n    196: 0.016505011620721321446910667689, 197: 0.016473065030899144358258880128, 198: 0.016451009996530175800379926859, 199: 0.016437757485613613151929367439, 200: 0.016412404337172521282671549397,\n    201: 0.016367412125580736332143483202, 202: 0.016352971230128453120207638717, 203: 0.016335003007438524680796380123, 204: 0.016300788824294591946405099898, 205: 0.016283013314130158511121657663,\n    206: 0.016273117664787137595561954257, 207: 0.016263528253458056226661978142, 208: 0.016214100185949151206700931970, 209: 0.016203997541366615653336750861, 210: 0.016197533588485788024643407773,\n    211: 0.016161527617815283384135782989, 212: 0.016145071184917156211072513779, 213: 0.016134147011892969370338165664, 214: 0.016129033240963740118320822674, 215: 0.015952300606546573411517567313,\n    216: 0.015913440570239784739764443474, 217: 0.015891603043212421653537834491, 218: 0.015771122920346430310110032169, 219: 0.015722929737572856961970440006, 220: 0.015686317077668465837711019409,\n    221: 0.015682287475429829002194754889, 222: 0.015559743033148525320473202077, 223: 0.015517403922453149948743592611, 224: 0.015507959828895195431526141245, 225: 0.015414147582570061905741172194,\n    226: 0.015389196500966192504915604177, 227: 0.015356598653442342204768214781, 228: 0.015346914376732703074329206786, 229: 0.015272592914550707564691259814, 230: 0.015222320161255296675073465158,\n    231: 0.015201874655402777754787190543, 232: 0.015142113599889771663744247424, 233: 0.015117805531553526486639687665, 234: 0.015076674297568630323818306803, 235: 0.015068153234936757636857744045,\n    236: 0.015016542614505362088761531017, 237: 0.014973694439890158212358313492, 238: 0.014950862594059463768230803946, 239: 0.014905189208923561018049600925, 240: 0.014879010241468044728855165942,\n    241: 0.014862284441798202704729078474, 242: 0.014836179634504955722389074246, 243: 0.014809157149471654085913467510, 244: 0.014767514027629843301439000956, 245: 0.014753543757896975820203890400,\n    246: 0.014730251355284468986647723026, 247: 0.014694705450223536505121284924, 248: 0.014674608405075370061658536002, 249: 0.014649091515656425591467869864, 250: 0.014634379134311154385152716173,\n    251: 0.014600230402988223793220518672, 252: 0.014588637635141936384049837876, 253: 0.014552269390974786019006708181, 254: 0.014532613401094451547740273609, 255: 0.014513418548511107535018076549,\n    256: 0.014509007894035429903235140881, 257: 0.014463641995490234585823322848, 258: 0.014445626927518965109263661803, 259: 0.014435160581007234983049919587, 260: 0.014413174289362975687017575021,\n    261: 0.014387579303850699025408068254, 262: 0.014371863768082800219595407348, 263: 0.014366690561041046744812733409, 264: 0.014350281438593147706317960993, 265: 0.014320797267990881240711127863,\n    266: 0.014313369385927822521587072972, 267: 0.014303340044255015949052755592, 268: 0.014292030283053914975780604014, 269: 0.014262199526132351999241974542, 270: 0.014246778156412688340224152772,\n    271: 0.014244878888492294503185880197, 272: 0.014238001658633590609014677856, 273: 0.014209463222242525918136550078, 274: 0.014195842152846120803722814064, 275: 0.014191231430249436539894248469,\n    276: 0.014188659811412899725474884561, 277: 0.014160843031753967781160959437, 278: 0.014116166064385175597376198196, 279: 0.014098552326307416566690758670, 280: 0.014088086615541166581914287747,\n    281: 0.013983608467831717954930832653, 282: 0.013941395746630152069637111937, 283: 0.013919134422206143447868374666, 284: 0.013913227454569556067358998519, 285: 0.013888890503232114628545060033,\n    286: 0.013791290771027291139314549267, 287: 0.013769254078541286196578363811, 288: 0.013762144311223339911835162742, 289: 0.013687800076955091270090952378, 290: 0.013657595543380449787546093650,\n    291: 0.013636245931610259492524716776, 292: 0.013618614715406392253028436848, 293: 0.013567581001326075240508572286, 294: 0.013536582566144829517507407268, 295: 0.013513784049919584181209925764,\n    296: 0.013494426217611419450977107745, 297: 0.013455789208680202683639836307, 298: 0.013426950715053645052692164867, 299: 0.013398721675631212469921340433, 300: 0.013396433701093527841692147654,\n    301: 0.013352345561474024572363782900, 302: 0.013333559467980713870438025355, 303: 0.013302442233656677545616471048, 304: 0.013295482255178390257042863315, 305: 0.013264867245188762869062269553,\n    306: 0.013236924939678425089883264991, 307: 0.013214968824599887324485606512, 308: 0.013204128112838473908519884548, 309: 0.013191827033906840590059225147, 310: 0.013163055632690517950300429198,\n    311: 0.013146350589477126566525979471, 312: 0.013127887079755592926432455927, 313: 0.013107836875915356707965691291, 314: 0.013077028645298377887078567743, 315: 0.013067342446435727658765583117,\n    316: 0.013056280709957701444835647229, 317: 0.013037610856048166177261148709, 318: 0.013016578896678743575622719033, 319: 0.013000246502312497746176236635, 320: 0.012996316600289142844450667479,\n    321: 0.012967574969175000855752508303, 322: 0.012946031142124085031759012434, 323: 0.012934028411716011079636179332, 324: 0.012930375635174747963957347494, 325: 0.012893483450896425878002116362,\n    326: 0.012891477340906122388411903610, 327: 0.012874850401875841561183981462, 328: 0.012867280056315405690673400041, 329: 0.012848638325300313205203015637, 330: 0.012828078570567147057323019750,\n    331: 0.012816403613032198651055285573, 332: 0.012791440372612162416486721064, 333: 0.012787122106035006136100096453, 334: 0.012772220728125321547950533468, 335: 0.012760416145141007110748621968,\n    336: 0.012754744298248867829149188700, 337: 0.012747208925775783003805939635, 338: 0.012726757664537019866642427832, 339: 0.012714977011556303669697939035, 340: 0.012710713912952269611887098499,\n    341: 0.012709908506956195695178200968, 342: 0.012702672865517648921908910033, 343: 0.012682324965230263197358600471, 344: 0.012673283247371042691716542704, 345: 0.012665895664152951449938995963,\n    346: 0.012664325969963665018044443512, 347: 0.012661545917361545708999024096,\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.2 - 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_200|{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.2 - 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"}}