{"id":"sphere-packing-sphere","name":"Equal spheres in a sphere","family":"combinatorics","description":"Place n spheres in the unit ball (radius 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 spheres in a sphere\n\n## Goal\n\n`pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, ...]]`: the\ncentres of `n` spheres inside the unit ball (radius 1) (3 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 `ssp`, 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 1000) 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 sphere-packing-sphere. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nGenerated by tools/packomania_import.py from https://packomania.com/ssp/ssp.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 = 3\n\n# Best-known values: equal objects in the unit ball (radius 1). Source: Packomania (E. Specht),\n# https://packomania.com/ssp/ssp.html, fetched 2026-09-06. only small n are proven.\nRECORDS = {\n    1: 1.000000000000, 2: 0.500000000000, 3: 0.464101615138, 4: 0.449489742783, 5: 0.414213562373,\n    6: 0.414213562373, 7: 0.385913557400, 8: 0.378024844801, 9: 0.366025403785, 10: 0.353049430432,\n    11: 0.344576516755, 12: 0.344576516755, 13: 0.333333333333, 14: 0.323504674183, 15: 0.318304823107,\n    16: 0.310975923325, 17: 0.305693961650, 18: 0.301296589342, 19: 0.295332333897, 20: 0.287890825717,\n    21: 0.286832818119, 22: 0.279342624810, 23: 0.275670701290, 24: 0.271341339941, 25: 0.271191827927,\n    26: 0.266851272489, 27: 0.262232080452, 28: 0.260305475681, 29: 0.257925462478, 30: 0.255330557656,\n    31: 0.253116209529, 32: 0.250787448179, 33: 0.248762350343, 34: 0.247052663501, 35: 0.244833658425,\n    36: 0.243132164915, 37: 0.240686558293, 38: 0.240519372142, 39: 0.236745240285, 40: 0.234999237637,\n    41: 0.232755981857, 42: 0.232118623301, 43: 0.229732967254, 44: 0.228163038226, 45: 0.226911569263,\n    46: 0.225168199111, 47: 0.223507049839, 48: 0.222405942149, 49: 0.221278177007, 50: 0.219758275796,\n    51: 0.218550295807, 52: 0.216930407731, 53: 0.216288057367, 54: 0.214920670908, 55: 0.213441688789,\n    56: 0.213067869308, 57: 0.211327241143, 58: 0.210480101312, 59: 0.209759450876, 60: 0.209426996435,\n    61: 0.209108659202, 62: 0.206739154000, 63: 0.205954921018, 64: 0.204107219252, 65: 0.203076051707,\n    66: 0.202108764115, 67: 0.201216632889, 68: 0.200002230133, 69: 0.199281532516, 70: 0.198688729141,\n    71: 0.197222141221, 72: 0.196285915470, 73: 0.195628445518, 74: 0.195146793635, 75: 0.193964427622,\n    76: 0.192947674925, 77: 0.192254117422, 78: 0.191458926390, 79: 0.190659742093, 80: 0.189727325517,\n    81: 0.188970653150, 82: 0.188297320002, 83: 0.187640284124, 84: 0.186956031676, 85: 0.186411242185,\n    86: 0.185610957844, 87: 0.184952925832, 88: 0.184275885830, 89: 0.183598057582, 90: 0.182937330629,\n    91: 0.182353276900, 92: 0.181782421764, 93: 0.181286816986, 94: 0.180820375937, 95: 0.180532959436,\n    96: 0.179567271930, 97: 0.179019633861, 98: 0.178499675043, 99: 0.177879839132, 100: 0.177439223049,\n    101: 0.176688867565, 102: 0.176215110923, 103: 0.175681317426, 104: 0.175184121787, 105: 0.174670246799,\n    106: 0.174167434485, 107: 0.173608258062, 108: 0.173168221779, 109: 0.172638823470, 110: 0.172285622418,\n    111: 0.171744763732, 112: 0.171331227895, 113: 0.170853998626, 114: 0.170449574714, 115: 0.169844873619,\n    116: 0.169416014365, 117: 0.169057962712, 118: 0.168723599855, 119: 0.168129445780, 120: 0.167683162280,\n    121: 0.167217751301, 122: 0.166844562670, 123: 0.166501095219, 124: 0.166046011632, 125: 0.165707392901,\n    126: 0.165236192632, 127: 0.164897399764, 128: 0.164797177360, 129: 0.164142581214, 130: 0.163801770859,\n    131: 0.163545333743, 132: 0.163232271313, 133: 0.162963979279, 134: 0.162832431396, 135: 0.162579700716,\n    136: 0.162377505731, 137: 0.161772816367, 138: 0.161135317283, 139: 0.160746481721, 140: 0.160407536677,\n    141: 0.160041657637, 142: 0.159699981108, 143: 0.159449054966, 144: 0.159153649105, 145: 0.158609167903,\n    146: 0.158248840832, 147: 0.157784117755, 148: 0.157569359432, 149: 0.157097566347, 150: 0.156791541716,\n    151: 0.156639601709, 152: 0.156045993115, 153: 0.155704877618, 154: 0.155370357768, 155: 0.154990721956,\n    156: 0.154643961095, 157: 0.154338501545, 158: 0.154083535103, 159: 0.153739285883, 160: 0.153403357533,\n    161: 0.153102131936, 162: 0.152793586534, 163: 0.152493953330, 164: 0.152224382259, 165: 0.151988754849,\n    166: 0.151626257544, 167: 0.151301831791, 168: 0.150987186808, 169: 0.150689896199, 170: 0.150452861896,\n    171: 0.150136920417, 172: 0.149892326079, 173: 0.149662426611, 174: 0.149322781215, 175: 0.149028363986,\n    176: 0.148746153967, 177: 0.148444299701, 178: 0.148152689318, 179: 0.147915023152, 180: 0.147649322270,\n    181: 0.147349702922, 182: 0.147073489170, 183: 0.146797966222, 184: 0.146535497150, 185: 0.146258233310,\n    186: 0.145978949142, 187: 0.145706907536, 188: 0.145452947787, 189: 0.145245497123, 190: 0.144968950591,\n    191: 0.144714894423, 192: 0.144508021238, 193: 0.144287551916, 194: 0.144082324351, 195: 0.143781006891,\n    196: 0.143581247013, 197: 0.143375209098, 198: 0.143082424861, 199: 0.142826267421, 200: 0.142593294458,\n    201: 0.142366448864, 202: 0.142130524291, 203: 0.141925141987, 204: 0.141735079717, 205: 0.141577621807,\n    206: 0.141275111632, 207: 0.141029599591, 208: 0.140785079876, 209: 0.140573023821, 210: 0.140365259385,\n    211: 0.140198175138, 212: 0.140021682216, 213: 0.139762719890, 214: 0.139549758852, 215: 0.139337959075,\n    216: 0.139127521285, 217: 0.138934610172, 218: 0.138758018716, 219: 0.138577783627, 220: 0.138363317813,\n    221: 0.138172488643, 222: 0.137952472614, 223: 0.137781609068, 224: 0.137576162444, 225: 0.137387725432,\n    226: 0.137237816865, 227: 0.137047851476, 228: 0.136831752368, 229: 0.136624488976, 230: 0.136437831304,\n    231: 0.136267332102, 232: 0.136081941226, 233: 0.135911032463, 234: 0.135708938778, 235: 0.135573225232,\n    236: 0.135369403232, 237: 0.135206530601, 238: 0.135036628086, 239: 0.134878141378, 240: 0.134644469895,\n    241: 0.134512621778, 242: 0.134305150087, 243: 0.134152598350, 244: 0.133988933998, 245: 0.133805756701,\n    246: 0.133632050792, 247: 0.133486248706, 248: 0.133346318389, 249: 0.133172202471, 250: 0.133019155360,\n    251: 0.132875845086, 252: 0.132731660835, 253: 0.132583357799, 254: 0.132482775180, 255: 0.132224141801,\n    256: 0.132081965229, 257: 0.131915363620, 258: 0.131688013226, 259: 0.131484220664, 260: 0.131335797850,\n    261: 0.131149067340, 262: 0.130974054754, 263: 0.130856611219, 264: 0.130690863367, 265: 0.130518255647,\n    266: 0.130320182422, 267: 0.130173426996, 268: 0.129972969724, 269: 0.129844323531, 270: 0.129735240880,\n    271: 0.129662549017, 272: 0.129528966956, 273: 0.129404622337, 274: 0.129267249991, 275: 0.129106718465,\n    276: 0.128970902318, 277: 0.128848732105, 278: 0.128696509625, 279: 0.128566099471, 280: 0.128457406677,\n    281: 0.128358017827, 282: 0.128227937370, 283: 0.128113371705, 284: 0.127946811562, 285: 0.127804093369,\n    286: 0.127663659549, 287: 0.127507093531, 288: 0.127378100251, 289: 0.127225969380, 290: 0.127068273470,\n    291: 0.126915642951, 292: 0.126780000894, 293: 0.126641081071, 294: 0.126494097683, 295: 0.126382215143,\n    296: 0.126235791266, 297: 0.126109478031, 298: 0.125962080860, 299: 0.125824264362, 300: 0.125649582321,\n    301: 0.125490931837, 302: 0.125373629555, 303: 0.125214543370, 304: 0.125088795793, 305: 0.124934320247,\n    306: 0.124806919979, 307: 0.124654623016, 308: 0.124500154949, 309: 0.124381242099, 310: 0.124282510831,\n    311: 0.124133187750, 312: 0.124016640410, 313: 0.123879257436, 314: 0.123747407103, 315: 0.123711418243,\n    316: 0.123588709574, 317: 0.123478681974, 318: 0.123337709396, 319: 0.123166336424, 320: 0.122988290754,\n    321: 0.122857918082, 322: 0.122736206214, 323: 0.122567710414, 324: 0.122441755419, 325: 0.122349917470,\n    326: 0.122223501795, 327: 0.122129852979, 328: 0.122048765754, 329: 0.121950939061, 330: 0.121781829182,\n    331: 0.121649560330, 332: 0.121479137749, 333: 0.121355387879, 334: 0.121217703381, 335: 0.121138209374,\n    336: 0.121001833439, 337: 0.120916177697, 338: 0.120807448913, 339: 0.120701534988, 340: 0.120578398495,\n    341: 0.120428195520, 342: 0.120310799980, 343: 0.120232820641, 344: 0.120082017728, 345: 0.119947957457,\n    346: 0.119818993838, 347: 0.119706956324, 348: 0.119606381361, 349: 0.119475705887, 350: 0.119369456838,\n    351: 0.119279659315, 352: 0.119161623265, 353: 0.119070466290, 354: 0.118974323096, 355: 0.118857073934,\n    356: 0.118779160578, 357: 0.118671146696, 358: 0.118608390741, 359: 0.118475240212, 360: 0.118285197830,\n    361: 0.118159920816, 362: 0.118074544675, 363: 0.117971973629, 364: 0.117895423793, 365: 0.117794792790,\n    366: 0.117655898649, 367: 0.117567789804, 368: 0.117496313849, 369: 0.117359143330, 370: 0.117268078317,\n    371: 0.117176099130, 372: 0.117088638479, 373: 0.116977361361, 374: 0.116816592838, 375: 0.116649382316,\n    376: 0.116517400327, 377: 0.116437707874, 378: 0.116330463510, 379: 0.116236516418, 380: 0.116135580344,\n    381: 0.116043427132, 382: 0.115956191693, 383: 0.115874189730, 384: 0.115778491539, 385: 0.115667460476,\n    386: 0.115564726696, 387: 0.115455539866, 388: 0.115367843867, 389: 0.115265212490, 390: 0.115129577836,\n    391: 0.114998604732, 392: 0.114936723140, 393: 0.114856204905, 394: 0.114764603508, 395: 0.114660729042,\n    396: 0.114571512626, 397: 0.114472931498, 398: 0.114373149795, 399: 0.114299465255, 400: 0.114181829812,\n    401: 0.114097010379, 402: 0.114013085024, 403: 0.113898964772, 404: 0.113795342572, 405: 0.113700976381,\n    406: 0.113611659614, 407: 0.113510190517, 408: 0.113416200820, 409: 0.113327255266, 410: 0.113236063862,\n    411: 0.113157487368, 412: 0.113075779255, 413: 0.112982017557, 414: 0.112884972536, 415: 0.112800801459,\n    416: 0.112727652157, 417: 0.112660499304, 418: 0.112592545389, 419: 0.112494307124, 420: 0.112400981512,\n    421: 0.112307226749, 422: 0.112216323292, 423: 0.112109639249, 424: 0.111992307481, 425: 0.111914260069,\n    426: 0.111847607502, 427: 0.111757418008, 428: 0.111666537428, 429: 0.111604820627, 430: 0.111516617369,\n    431: 0.111444952708, 432: 0.111371274886, 433: 0.111298633415, 434: 0.111216099714, 435: 0.111128957747,\n    436: 0.111038564336, 437: 0.110953826244, 438: 0.110862056210, 439: 0.110781726059, 440: 0.110706306299,\n    441: 0.110636129569, 442: 0.110556513581, 443: 0.110480487643, 444: 0.110409970203, 445: 0.110329701864,\n    446: 0.110242721853, 447: 0.110167721842, 448: 0.110070980410, 449: 0.109992259613, 450: 0.109900765714,\n    451: 0.109831301381, 452: 0.109779307967, 453: 0.109708393902, 454: 0.109638537936, 455: 0.109562367061,\n    456: 0.109468890202, 457: 0.109384933764, 458: 0.109309824972, 459: 0.109262665873, 460: 0.109236144306,\n    461: 0.109194716250, 462: 0.109159451241, 463: 0.109123679767, 464: 0.109086950906, 465: 0.109055056704,\n    466: 0.109000035467, 467: 0.108933846376, 468: 0.108882556630, 469: 0.108822657665, 470: 0.108757629852,\n    471: 0.108705128410, 472: 0.108645749588, 473: 0.108596985546, 474: 0.108528179435, 475: 0.108488245184,\n    476: 0.108414012939, 477: 0.108359091922, 478: 0.108304831188, 479: 0.108242617185, 480: 0.108158304104,\n    481: 0.108090978405, 482: 0.108037648961, 483: 0.107990674309, 484: 0.107959980247, 485: 0.107843677630,\n    486: 0.107733535315, 487: 0.107622925268, 488: 0.107519606294, 489: 0.107444020418, 490: 0.107367229019,\n    491: 0.107284635368, 492: 0.107182858284, 493: 0.107108187817, 494: 0.107040073590, 495: 0.106938263603,\n    496: 0.106870917453, 497: 0.106803651805, 498: 0.106729089159, 499: 0.106674106659, 500: 0.106604412779,\n    501: 0.106542750183, 502: 0.106475228019, 503: 0.106397370497, 504: 0.106331698068, 505: 0.106257188747,\n    506: 0.106191809418, 507: 0.106144104523, 508: 0.106083015492, 509: 0.105994105169, 510: 0.105918247007,\n    511: 0.105849319267, 512: 0.105753822823, 513: 0.105689834099, 514: 0.105637116557, 515: 0.105578802177,\n    516: 0.105519541936, 517: 0.105458162290, 518: 0.105384292043, 519: 0.105322028723, 520: 0.105259083876,\n    521: 0.105196808356, 522: 0.105123957373, 523: 0.105060802413, 524: 0.104994703137, 525: 0.104932501974,\n    526: 0.104842223196, 527: 0.104773730241, 528: 0.104705717483, 529: 0.104653196786, 530: 0.104601621148,\n    531: 0.104530261301, 532: 0.104472190838, 533: 0.104408443290, 534: 0.104354681221, 535: 0.104284729436,\n    536: 0.104236224359, 537: 0.104200166810, 538: 0.104139994611, 539: 0.104085424686, 540: 0.104028065780,\n    541: 0.103956095425, 542: 0.103896271526, 543: 0.103840056241, 544: 0.103777798376, 545: 0.103698649209,\n    546: 0.103632560998, 547: 0.103569738029, 548: 0.103516710220, 549: 0.103461319468, 550: 0.103412725757,\n    551: 0.103349986940, 552: 0.103281253115, 553: 0.103192677349, 554: 0.103134643598, 555: 0.103069135601,\n    556: 0.103008498603, 557: 0.102959193065, 558: 0.102890885379, 559: 0.102835060626, 560: 0.102759440802,\n    561: 0.102706403416, 562: 0.102648463746, 563: 0.102584383595, 564: 0.102533756983, 565: 0.102476282129,\n    566: 0.102415656133, 567: 0.102357757586, 568: 0.102303579980, 569: 0.102228477823, 570: 0.102154002125,\n    571: 0.102099211501, 572: 0.102011985884, 573: 0.101960024776, 574: 0.101890845680, 575: 0.101834446460,\n    576: 0.101756954480, 577: 0.101683846137, 578: 0.101644184583, 579: 0.101573311979, 580: 0.101517350947,\n    581: 0.101460762549, 582: 0.101401478527, 583: 0.101333376820, 584: 0.101249350886, 585: 0.101170033064,\n    586: 0.101080252287, 587: 0.101036079748, 588: 0.100979946625, 589: 0.100923818163, 590: 0.100874854803,\n    591: 0.100830846743, 592: 0.100759270929, 593: 0.100720447111, 594: 0.100677806701, 595: 0.100638451902,\n    596: 0.100580242544, 597: 0.100516024832, 598: 0.100458969226, 599: 0.100407480204, 600: 0.100352826383,\n    601: 0.100293713018, 602: 0.100253249532, 603: 0.100198238967, 604: 0.100140346297, 605: 0.100088871777,\n    606: 0.100030071383, 607: 0.099966857936, 608: 0.099924276481, 609: 0.099866127055, 610: 0.099815914868,\n    611: 0.099761292981, 612: 0.099723451037, 613: 0.099673174688, 614: 0.099595586920, 615: 0.099523852223,\n    616: 0.099471113265, 617: 0.099433253615, 618: 0.099386919426, 619: 0.099324395096, 620: 0.099269074844,\n    621: 0.099223699230, 622: 0.099170830062, 623: 0.099104271565, 624: 0.099052086817, 625: 0.099004537774,\n    626: 0.098944637779, 627: 0.098899091950, 628: 0.098846826920, 629: 0.098777652068, 630: 0.098694562519,\n    631: 0.098635078252, 632: 0.098575483131, 633: 0.098524199442, 634: 0.098473505010, 635: 0.098420878433,\n    636: 0.098370546190, 637: 0.098320014828, 638: 0.098273408131, 639: 0.098209083120, 640: 0.098167293330,\n    641: 0.098130127157, 642: 0.098074289947, 643: 0.098029775307, 644: 0.097963014461, 645: 0.097909708948,\n    646: 0.097841862817, 647: 0.097791880162, 648: 0.097741553457, 649: 0.097694837551, 650: 0.097654656277,\n    651: 0.097596161828, 652: 0.097558909594, 653: 0.097517927005, 654: 0.097473970916, 655: 0.097423061088,\n    656: 0.097374559150, 657: 0.097318003293, 658: 0.097273234315, 659: 0.097223365675, 660: 0.097163149548,\n    661: 0.097115694265, 662: 0.097075437605, 663: 0.097023214253, 664: 0.096964500595, 665: 0.096921317265,\n    666: 0.096883374172, 667: 0.096844971710, 668: 0.096803845972, 669: 0.096761054648, 670: 0.096710642894,\n    671: 0.096660381360, 672: 0.096617458730, 673: 0.096567280443, 674: 0.096522541403, 675: 0.096462099918,\n    676: 0.096401378083, 677: 0.096335502932, 678: 0.096285472622, 679: 0.096229771263, 680: 0.096186948877,\n    681: 0.096149167638, 682: 0.096108475555, 683: 0.096053487358, 684: 0.096005239420, 685: 0.095963209581,\n    686: 0.095916791464, 687: 0.095866669265, 688: 0.095819618243, 689: 0.095776521417, 690: 0.095739586337,\n    691: 0.095702112615, 692: 0.095647318573, 693: 0.095609967819, 694: 0.095577604545, 695: 0.095541834438,\n    696: 0.095494840136, 697: 0.095453108585, 698: 0.095408603895, 699: 0.095364768091, 700: 0.095328417403,\n    701: 0.095294937721, 702: 0.095249664637, 703: 0.095203312211, 704: 0.095165539044, 705: 0.095123563481,\n    706: 0.095059583683, 707: 0.095016794188, 708: 0.094971076220, 709: 0.094903939944, 710: 0.094862542816,\n    711: 0.094822548010, 712: 0.094762121119, 713: 0.094723474926, 714: 0.094680907533, 715: 0.094641936116,\n    716: 0.094606023058, 717: 0.094555094518, 718: 0.094516990343, 719: 0.094483068127, 720: 0.094432226719,\n    721: 0.094391454449, 722: 0.094355052458, 723: 0.094314105739, 724: 0.094276320996, 725: 0.094243586191,\n    726: 0.094206583371, 727: 0.094163863674, 728: 0.094123254563, 729: 0.094090172679, 730: 0.094054306383,\n    731: 0.094019615506, 732: 0.093968637774, 733: 0.093937841419, 734: 0.093903845427, 735: 0.093864252048,\n    736: 0.093820484107, 737: 0.093776956596, 738: 0.093748786474, 739: 0.093708313182, 740: 0.093668723933,\n    741: 0.093618639486, 742: 0.093559158917, 743: 0.093524144115, 744: 0.093482804290, 745: 0.093443746426,\n    746: 0.093395398525, 747: 0.093353086356, 748: 0.093300265654, 749: 0.093258982565, 750: 0.093221117289,\n    751: 0.093185964727, 752: 0.093149937062, 753: 0.093115114573, 754: 0.093070640075, 755: 0.093032036861,\n    756: 0.092982185154, 757: 0.092941461286, 758: 0.092896660152, 759: 0.092864965318, 760: 0.092838292626,\n    761: 0.092793567659, 762: 0.092759771726, 763: 0.092722042391, 764: 0.092691384043, 765: 0.092645251156,\n    766: 0.092618448344, 767: 0.092589892854, 768: 0.092563504785, 769: 0.092538600556, 770: 0.092502877290,\n    771: 0.092465977705, 772: 0.092423655880, 773: 0.092393607217, 774: 0.092367699274, 775: 0.092321628711,\n    776: 0.092276871777, 777: 0.092241597342, 778: 0.092191424750, 779: 0.092163493263, 780: 0.092126065352,\n    781: 0.092077593993, 782: 0.092048924358, 783: 0.092015410815, 784: 0.091979107013, 785: 0.091947441499,\n    786: 0.091907728500, 787: 0.091875063534, 788: 0.091844484186, 789: 0.091808077486, 790: 0.091763410768,\n    791: 0.091724762349, 792: 0.091678315780, 793: 0.091638282424, 794: 0.091589188123, 795: 0.091546991564,\n    796: 0.091504596019, 797: 0.091474958782, 798: 0.091438225009, 799: 0.091411539181, 800: 0.091377179372,\n    801: 0.091356377053, 802: 0.091317839738, 803: 0.091297280047, 804: 0.091272294382, 805: 0.091248712362,\n    806: 0.091223937322, 807: 0.091197478621, 808: 0.091168011365, 809: 0.091139609043, 810: 0.091103453432,\n    811: 0.091061406375, 812: 0.091013201078, 813: 0.090969940209, 814: 0.090932347064, 815: 0.090902921087,\n    816: 0.090868058993, 817: 0.090836958344, 818: 0.090811796490, 819: 0.090787068617, 820: 0.090756683093,\n    821: 0.090724778422, 822: 0.090699013068, 823: 0.090672706459, 824: 0.090648398213, 825: 0.090622732401,\n    826: 0.090588790902, 827: 0.090557480811, 828: 0.090524088971, 829: 0.090479618348, 830: 0.090439636341,\n    831: 0.090394941183, 832: 0.090361794430, 833: 0.090329949168, 834: 0.090295906267, 835: 0.090257023056,\n    836: 0.090219139452, 837: 0.090182017342, 838: 0.090145919790, 839: 0.090115773776, 840: 0.090094648732,\n    841: 0.090067208394, 842: 0.090030152352, 843: 0.090001251871, 844: 0.089976898872, 845: 0.089940236862,\n    846: 0.089901911938, 847: 0.089869098934, 848: 0.089833227686, 849: 0.089805139434, 850: 0.089769330303,\n    851: 0.089734966619, 852: 0.089685160166, 853: 0.089636225155, 854: 0.089604194293, 855: 0.089550875590,\n    856: 0.089512277242, 857: 0.089490121022, 858: 0.089459012099, 859: 0.089421799658, 860: 0.089389990162,\n    861: 0.089357998576, 862: 0.089329838954, 863: 0.089300856668, 864: 0.089269162397, 865: 0.089243717312,\n    866: 0.089212319646, 867: 0.089173556116, 868: 0.089143525778, 869: 0.089111219540, 870: 0.089071519105,\n    871: 0.089031505226, 872: 0.089001202540, 873: 0.088971755184, 874: 0.088943641438, 875: 0.088907703200,\n    876: 0.088874817809, 877: 0.088842500836, 878: 0.088809619320, 879: 0.088766129827, 880: 0.088730768934,\n    881: 0.088689098193, 882: 0.088644076014, 883: 0.088609791435, 884: 0.088584568760, 885: 0.088546900610,\n    886: 0.088516524465, 887: 0.088469115386, 888: 0.088430782611, 889: 0.088403439155, 890: 0.088370985662,\n    891: 0.088342899386, 892: 0.088309023354, 893: 0.088279757335, 894: 0.088251261180, 895: 0.088219593254,\n    896: 0.088191710110, 897: 0.088162633052, 898: 0.088129605734, 899: 0.088104192342, 900: 0.088062636910,\n    901: 0.088021334373, 902: 0.087994964316, 903: 0.087969853130, 904: 0.087874111595, 905: 0.087847440430,\n    906: 0.087821787739, 907: 0.087814336288, 908: 0.087781612274, 909: 0.087742963144, 910: 0.087728508253,\n    911: 0.087696190077, 912: 0.087652682056, 913: 0.087628719449, 914: 0.087595383452, 915: 0.087554076144,\n    916: 0.087528740744, 917: 0.087496243125, 918: 0.087496243125, 919: 0.087496243125, 920: 0.087478327225,\n    921: 0.087442462040, 922: 0.087397733207, 923: 0.087363816061, 924: 0.087333159263, 925: 0.087304525621,\n    926: 0.087271798516, 927: 0.087238763494, 928: 0.087211120328, 929: 0.087185370699, 930: 0.087152888328,\n    931: 0.087131502241, 932: 0.087115088012, 933: 0.087076183677, 934: 0.087048934946, 935: 0.087004129144,\n    936: 0.087004129144, 937: 0.086973830667, 938: 0.086937289275, 939: 0.086894934547, 940: 0.086844411504,\n    941: 0.086816195452, 942: 0.086788529874, 943: 0.086746564287, 944: 0.086705758128, 945: 0.086674624964,\n    946: 0.086657652876, 947: 0.086614542393, 948: 0.086585683533, 949: 0.086548783028, 950: 0.086484800910,\n    951: 0.086438900735, 952: 0.086393774066, 953: 0.086363394585, 954: 0.086332666666, 955: 0.086316627916,\n    956: 0.086278255510, 957: 0.086252082479, 958: 0.086220305989, 959: 0.086143888184, 960: 0.086143888184,\n    961: 0.086117451607, 962: 0.086082384080, 963: 0.086039345246, 964: 0.085989262766, 965: 0.085959637651,\n    966: 0.085934361266, 967: 0.085894494967, 968: 0.085867512082, 969: 0.085842538690, 970: 0.085803694870,\n    971: 0.085762995681, 972: 0.085711768687, 973: 0.085687380067, 974: 0.085656096116, 975: 0.085627301671,\n    976: 0.085601380426, 977: 0.085560957376, 978: 0.085530419149, 979: 0.085486672195, 980: 0.085456844251,\n    981: 0.085435858128, 982: 0.085408631809, 983: 0.085384408890, 984: 0.085360872491, 985: 0.085341420113,\n    986: 0.085306077217, 987: 0.085277722370, 988: 0.085248129597, 989: 0.085218509818, 990: 0.085187095860,\n    991: 0.085158445512, 992: 0.085137901776, 993: 0.085108696641, 994: 0.085076933648, 995: 0.085059124634,\n    996: 0.085026217584, 997: 0.084993734086, 998: 0.084958883804, 999: 0.084930865271, 1000: 0.084866089682,\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 1.0 - math.sqrt(c[0] * c[0] + c[1] * c[1] + c[2] * c[2])\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\"ssp|{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 = 3\n\n\ndef _boundary(c):\n    return 1.0 - math.sqrt(c[0] * c[0] + c[1] * c[1] + c[2] * c[2])\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"}}