{"id":"circle-packing-quadrant","name":"Equal circles in a quarter disk","family":"combinatorics","description":"Place n circles in the unit quadrant (radius 1, x >= 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 quarter disk\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 quadrant (radius 1, x >= 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 `ccq`, 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 600) 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-quadrant. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nGenerated by tools/packomania_import.py from https://packomania.com/ccq/ccq.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 quadrant (radius 1, x >= 0, y >= 0). Source: Packomania (E. Specht),\n# https://packomania.com/ccq/ccq.html, fetched 2026-09-06. only small n are proven.\nRECORDS = {\n    1: 0.414213562373095048801688724211, 2: 0.276768653914155215717770973809, 3: 0.240253073352042147999877060493, 4: 0.205604646759568224693193969093, 5: 0.180960531653868302007734251938,\n    6: 0.167632184592678242543441991309, 7: 0.163243161142003991913329124676, 8: 0.150154807084741322297665096450, 9: 0.139429107850471597338690683436, 10: 0.135072985268351994987422353792,\n    11: 0.127840596125867863162619218933, 12: 0.125441937332820688361738236682, 13: 0.118280294043166541218397318535, 14: 0.115456141678356872441258327524, 15: 0.110212024387959910148530104616,\n    16: 0.107771974554386810881887575168, 17: 0.104571563125836898331644050466, 18: 0.102431610396020738261052586657, 19: 0.100690695170108760185749609484, 20: 0.097064861746472257626375696150,\n    21: 0.095341841141922509471481302590, 22: 0.092357812035589777023034182141, 23: 0.090855472209869065449883091814, 24: 0.089194524043168924059610389804, 25: 0.087830975905185831831546124292,\n    26: 0.086028881020132430920462047286, 27: 0.084931362539244210178247227126, 28: 0.082763227492774399007205548930, 29: 0.081560146728344274824249725274, 30: 0.080566190424326355573787305069,\n    31: 0.078902983099998773519415823186, 32: 0.077900800624123658619302848501, 33: 0.076699896995223654046948938047, 34: 0.075703248146737660204245987796, 35: 0.074555758644084592766278171429,\n    36: 0.073839675073728961639686362588, 37: 0.072791736622433279819024691717, 38: 0.071770791677304644383725433205, 39: 0.070892474060411576015783723099, 40: 0.070088729311365557825494148499,\n    41: 0.069105932745766031249481120868, 42: 0.068490562566375397099520563816, 43: 0.067695356551689090397906481699, 44: 0.067092515149803725825711474525, 45: 0.066425531708864791464822896781,\n    46: 0.065644625979000921535821451997, 47: 0.064812778834776259705369595528, 48: 0.064258263442779429307939858065, 49: 0.063682934382299404892909647152, 50: 0.063100032760197409718776519382,\n    51: 0.062382503172326925548522372140, 52: 0.061878492264348670578387579783, 53: 0.061441520765396898744355981343, 54: 0.060866975785767450648172816380, 55: 0.060346853664467115054859642554,\n    56: 0.059814591562794433327835044209, 57: 0.059296796748175769239897558746, 58: 0.058761842243376827266422977046, 59: 0.058229778872367047562758347311, 60: 0.057804691718488802552161420565,\n    61: 0.057337512219285693771525584590, 62: 0.056905282892276613010398287620, 63: 0.056439910614597870967413316364, 64: 0.055980958572200128520988752432, 65: 0.055601707670656490568141957029,\n    66: 0.055310994377172886502427586954, 67: 0.055118371461092659214755488175, 68: 0.054554936898038103346297664058, 69: 0.054233098590001789332564367072, 70: 0.053838632742106852500240476249,\n    71: 0.053412118127950514142737189158, 72: 0.052970965638075540919473044087, 73: 0.052649642462630304848924598240, 74: 0.052361336091511592848657362660, 75: 0.052039382895073807651284596791,\n    76: 0.051659307512809368731043404430, 77: 0.051316388023587913838037419370, 78: 0.050969656550876277737480334185, 79: 0.050729212034025278045646845412, 80: 0.050469995687303621559202946822,\n    81: 0.050128110030006909440350418768, 82: 0.049949115342851746776562775774, 83: 0.049667229534383780971846297946, 84: 0.049370544769394135430585458801, 85: 0.049029773123640570574387596041,\n    86: 0.048718942595282814644415806633, 87: 0.048394069366077102053419807327, 88: 0.048135265567885533375817493726, 89: 0.047860179787749405180935826811, 90: 0.047690815763978770675769818572,\n    91: 0.047425323601201752506735799656, 92: 0.047143089137604011316317166039, 93: 0.046875798407782704872814368992, 94: 0.046622128741765958668086661336, 95: 0.046445632686155081367553277443,\n    96: 0.046162935180602263933367986218, 97: 0.045988795089836153717255600968, 98: 0.045753164215951218411157236927, 99: 0.045543244595615184739876255041, 100: 0.045421461297472835606397648395,\n    101: 0.045119237135243855605965803316, 102: 0.044947642441240489331457360867, 103: 0.044706931172835039134122944581, 104: 0.044442427278154635366223205852, 105: 0.044187434847504235562011350418,\n    106: 0.044021539019473353049777899203, 107: 0.043802414903252930474652138218, 108: 0.043650810083632774908072229540, 109: 0.043437766544493837733801993550, 110: 0.043253319427263113291638813855,\n    111: 0.043146290244897913890471382024, 112: 0.042900591891557121480073940343, 113: 0.042796186715069609522420065930, 114: 0.042568121129894523227427201137, 115: 0.042379410845075479510806140895,\n    116: 0.042207300576844288904254584632, 117: 0.041999098154912066645377558893, 118: 0.041827105447510659508904074709, 119: 0.041664363838892453146555708345, 120: 0.041528702890877599133163133735,\n    121: 0.041343986760658147036947762851, 122: 0.041138228676572956727695854654, 123: 0.041010465996361532835978001803, 124: 0.040839089927107800350836839437, 125: 0.040665412126370336744932079773,\n    126: 0.040539377876827879351713862469, 127: 0.040374700053353078211844978714, 128: 0.040224180670223725750051286983, 129: 0.040096986299053851013745128894, 130: 0.039955883725213528940846256897,\n    131: 0.039893166794404111069602866521, 132: 0.039706823934972434809033287886, 133: 0.039571148531012335795435869060, 134: 0.039418708598368303843710418315, 135: 0.039228586335224107904497680509,\n    136: 0.039040377175033596131444600850, 137: 0.038869939420518748988257412818, 138: 0.038753806920383718788845877120, 139: 0.038630068470524239119782337252, 140: 0.038508217172066278583491662471,\n    141: 0.038360609675454577588528214836, 142: 0.038243452002782303647523987514, 143: 0.038140151285667893761278177377, 144: 0.038010484625616485117434526477, 145: 0.037880672872338656525556105053,\n    146: 0.037738946286662307486037072670, 147: 0.037613632038206761060854006001, 148: 0.037522960168921307510171809305, 149: 0.037419959581488897674409346897, 150: 0.037303294575241679860882953923,\n    151: 0.037201000478867469030233098701, 152: 0.037057268901087325103043447196, 153: 0.036965928716872284240715090158, 154: 0.036864786419029102530610770340, 155: 0.036754827769229165632017488174,\n    156: 0.036588801077363921678210024442, 157: 0.036441609676766279143803520972, 158: 0.036326581378741459515770614291, 159: 0.036214595396599732936784472808, 160: 0.036126897203248359135611356028,\n    161: 0.036013842961928271487250443564, 162: 0.035902660750024352315582990199, 163: 0.035793513625964235951840092217, 164: 0.035690163735959121157000267081, 165: 0.035614818470782992140303152213,\n    166: 0.035540483878409645201041425171, 167: 0.035396031441311011840765685367, 168: 0.035286286809421951933896094377, 169: 0.035211337142045706581704444309, 170: 0.035131504327030047701781647413,\n    171: 0.035024827414996293002405846074, 172: 0.034938288290569209804865647589, 173: 0.034838788393645312525417554370, 174: 0.034724737628357394981624266152, 175: 0.034604085659898496388435223033,\n    176: 0.034544714159805161443157762361, 177: 0.034425714733016198959654635175, 178: 0.034338961395466148469808486233, 179: 0.034219220192238391547357444435, 180: 0.034131632302507309626736712336,\n    181: 0.034048985423610743240772372524, 182: 0.033938962374132504113036769494, 183: 0.033860758852912077944413528044, 184: 0.033784307231386231211482119723, 185: 0.033689509741173012511171089080,\n    186: 0.033585469192533155822576196616, 187: 0.033487956181852990378473366588, 188: 0.033389836070667013489285012900, 189: 0.033318133697353787556612961590, 190: 0.033258216027685705868085732792,\n    191: 0.033229471138875250172387859205, 192: 0.033144324003588737845442862773, 193: 0.033040447832574320651442401381, 194: 0.033009199226023313246515733583, 195: 0.032918610138601581080442652490,\n    196: 0.032816938579851875349552641872, 197: 0.032752183486519598458011678977, 198: 0.032621030750373598292738511306, 199: 0.032508036449802290521602120629, 200: 0.032416314991862062776762908354,\n    201: 0.032341139243844110976873340178, 202: 0.032274625517629213419874041977, 203: 0.032216567844599663297748040092, 204: 0.032143450312414174543614473832, 205: 0.032061898434788220527537408977,\n    206: 0.032005756775790694201734610015, 207: 0.031921319034744407434386971252, 208: 0.031838380285333429121452062014, 209: 0.031770197444380545022008915611, 210: 0.031724240846375833974275238852,\n    211: 0.031644979518215468277229306373, 212: 0.031535876303173390828052907524, 213: 0.031463656755278974547357818291, 214: 0.031393613119857380370400256274, 215: 0.031362274628565178292807517092,\n    216: 0.031276226227071457755570259890, 217: 0.031234288981354551625977219975, 218: 0.031172934296327957863744269453, 219: 0.031117914617647727699661564768, 220: 0.031034642599658221249627748165,\n    221: 0.030945798183216915640416119819, 222: 0.030867124485691030785727199447, 223: 0.030802108468218903911471402234, 224: 0.030713010890799945946843945397, 225: 0.030638415845131143552309778385,\n    226: 0.030544239678884971435947875531, 227: 0.030491980460813935979623274134, 228: 0.030446503182072384174641514990, 229: 0.030389743945230429480309001555, 230: 0.030327668614238107898328761394,\n    231: 0.030262707641186489881034414118, 232: 0.030185107209498609304012575521, 233: 0.030132018392993824431462111755, 234: 0.030072291534594748628529729973, 235: 0.030013466413265829751794139134,\n    236: 0.029958285434083185622239318163, 237: 0.029900996522178801464063554202, 238: 0.029827790826800158507718326090, 239: 0.029752691470288250271052981213, 240: 0.029729958850170637028357161416,\n    241: 0.029652142689658777191183712633, 242: 0.029603574272423193052297738901, 243: 0.029575055260237009581374385454, 244: 0.029479641982531970795983786093, 245: 0.029434301223297864908324889617,\n    246: 0.029399858135174480431989864407, 247: 0.029313276455027973859518557167, 248: 0.029264275534136050833879170480, 249: 0.029186869521409828909201209103, 250: 0.029135022807625028068733579941,\n    251: 0.029064485789349924015663160531, 252: 0.028992446477917760137558520814, 253: 0.028931951607771604071277051243, 254: 0.028903163657343623601809801592, 255: 0.028826910595817317580385681650,\n    256: 0.028775357303994211639544464647, 257: 0.028740518223450786767892539708, 258: 0.028675194763325213931599657321, 259: 0.028618312221257110647965320099, 260: 0.028579549321180630584186511116,\n    261: 0.028530694264293309806658858612, 262: 0.028462909046514130433804117907, 263: 0.028413515977445579318098207685, 264: 0.028384247152930005079118403281, 265: 0.028332016886475537453048768513,\n    266: 0.028278012352339868655072394711, 267: 0.028207342667237912699672150520, 268: 0.028169688389055924937667091338, 269: 0.028128464128321893028422624860, 270: 0.028056543256419460673600445545,\n    271: 0.028006024648958657048299780157, 272: 0.027974177081458299414150343488, 273: 0.027908598277658195576197012678, 274: 0.027857827733356763573281267172, 275: 0.027809002869611580043845686953,\n    276: 0.027766762021695590196883587765, 277: 0.027712252308508207501176127561, 278: 0.027651746586473511331203320774, 279: 0.027603205063676750129159098713, 280: 0.027557283822103039262338758918,\n    281: 0.027528500959210269395240025131, 282: 0.027456971371556832344307753164, 283: 0.027423092568339987593793257205, 284: 0.027378621660017680993898333014, 285: 0.027319541952565351622787344405,\n    286: 0.027262527000404506097643055888, 287: 0.027227282738064834154013968814, 288: 0.027184084912724336664116236595, 289: 0.027126285109735480099773325569, 290: 0.027082617474715904722383522001,\n    291: 0.027028451655817169996002040364, 292: 0.027015153532960576193361069319, 293: 0.026963393298796673095096643882, 294: 0.026952779910469586871753626154, 295: 0.026896282534245141268997727856,\n    296: 0.026846311008980336499914239667, 297: 0.026826984691625261732435054769, 298: 0.026751887889701993284195349361, 299: 0.026714210616744195414678968929, 300: 0.026678506222513658431066627243,\n    301: 0.026611063497187978843585465957, 302: 0.026568451415399594408249906955, 303: 0.026537197119921067510459751806, 304: 0.026473845498943145372397511873, 305: 0.026428368861103396273542922562,\n    306: 0.026382780604140884620499960803, 307: 0.026345779501268322761034320432, 308: 0.026295433560125655422478155416, 309: 0.026270792596310767593371220947, 310: 0.026220263802355620823232497321,\n    311: 0.026183260063808331187500418783, 312: 0.026149704384675791717372541670, 313: 0.026113588345962279868391766610, 314: 0.026071627270816999028769732908, 315: 0.026044245372997027588186809504,\n    316: 0.026001728777789566083138319856, 317: 0.025956667300572955171849924693, 318: 0.025913419057521647519301362528, 319: 0.025873880129844426268827321696, 320: 0.025833604706265132535870280928,\n    321: 0.025791892763001229175846588380, 322: 0.025741939571621601509666368430, 323: 0.025718394669955269433069891547, 324: 0.025685766035552961609269505651, 325: 0.025646503759898902037330287051,\n    326: 0.025620775101039165388298925403, 327: 0.025574055021668674577623987719, 328: 0.025541398043075788550382834367, 329: 0.025502947913850018450741265738, 330: 0.025453888804897145493236934840,\n    331: 0.025402996513313218258769689179, 332: 0.025393222894083091692421736697, 333: 0.025331718991583996208038694627, 334: 0.025274417657443220262434218170, 335: 0.025235727541835654759100287574,\n    336: 0.025212319216303996332035419014, 337: 0.025180106362549007115942170209, 338: 0.025127493648930660715234515410, 339: 0.025105310641568190410837472353, 340: 0.025079810550795112705843193488,\n    341: 0.025039345325134570390463992011, 342: 0.025009472746826819080944706698, 343: 0.024963787109533376686283541031, 344: 0.024934953384611420901410837794, 345: 0.024904331818785602705154456373,\n    346: 0.024863141314712893527617170247, 347: 0.024828671393335903904711148019, 348: 0.024794951890863088961724915707, 349: 0.024761936081848368680947018782, 350: 0.024713739851045203535994357092,\n    351: 0.024699499759160530401823931534, 352: 0.024662698346676968942279846139, 353: 0.024638827899444183198668238310, 354: 0.024624889275316956566241358686, 355: 0.024565871572170465388571819838,\n    356: 0.024537380495653206696718273285, 357: 0.024513179627408183597143794292, 358: 0.024474979030983906511113313490, 359: 0.024439931730897365686024873207, 360: 0.024418099411021496937738600627,\n    361: 0.024374104691784344911290210250, 362: 0.024344784727005343174600838289, 363: 0.024303460916349719379973316482, 364: 0.024236645536085254409344591279, 365: 0.024210940605576983616499200569,\n    366: 0.024181506859305843535052499429, 367: 0.024147759567863161248362752504, 368: 0.024135214009073084824764430510, 369: 0.024103328975168489989643060068, 370: 0.024073680857806741387767518489,\n    371: 0.024051099798218890263185247011, 372: 0.024002224997826289643970643962, 373: 0.023980653158378101027691655430, 374: 0.023956975687939146109418489328, 375: 0.023925921978370507711464444332,\n    376: 0.023877544233918421546696597603, 377: 0.023840445105782450804506636627, 378: 0.023813161318929372162208370566, 379: 0.023787997673572726452439886911, 380: 0.023778277733292925026055514278,\n    381: 0.023721667787113099706441305661, 382: 0.023691199365845207598242337020, 383: 0.023682545606811748288576876470, 384: 0.023640359088648297780593113600, 385: 0.023619119705674192463215178205,\n    386: 0.023595504619220628089219209110, 387: 0.023561050784462328381417426909, 388: 0.023530134870907997766013511812, 389: 0.023515813252408487006698245007, 390: 0.023464004940269259036801739720,\n    391: 0.023438695745537202163654010385, 392: 0.023415280088837639898832451292, 393: 0.023369553309651990153489687032, 394: 0.023336449933576908392790881778, 395: 0.023305118467398619388846339613,\n    396: 0.023275852263680342752393100021, 397: 0.023243443422249742677425079158, 398: 0.023214515937588520096232447557, 399: 0.023176899634047446644971908724, 400: 0.023158425634302602938395660426,\n    401: 0.023137463211018221331413172434, 402: 0.023119976034264802074362657973, 403: 0.023099177102757106297742644211, 404: 0.023066516766777749381518969482, 405: 0.023034037290668222663867408359,\n    406: 0.023009609058826151530802122308, 407: 0.022988910834185552855048401127, 408: 0.022962990691541337833350972166, 409: 0.022921980434400423643202439477, 410: 0.022901981079742414142011492999,\n    411: 0.022879142899155243349867517376, 412: 0.022839095201610763775615551839, 413: 0.022793277083854117500339575094, 414: 0.022780192595943952362942638870, 415: 0.022770188341761139537705819240,\n    416: 0.022746573209391082187043418376, 417: 0.022734859070069872851851586327, 418: 0.022711596795404007043825973367, 419: 0.022675283982944550104021201172, 420: 0.022663429411007577381545346733,\n    421: 0.022628204726608484423660870676, 422: 0.022610438660737450164283939804, 423: 0.022582719903430084988050885778, 424: 0.022542855161517640009977623589, 425: 0.022506463348736155403987092076,\n    426: 0.022486863273434746289735926608, 427: 0.022455350543739103295850107708, 428: 0.022416500042844109830103866425, 429: 0.022383757336444985432248247254, 430: 0.022345677726957364885653414833,\n    431: 0.022328667329416136446940112383, 432: 0.022310930801806191655044823570, 433: 0.022296416854166189658925694309, 434: 0.022268226913616426976146277727, 435: 0.022253489188125723847878744093,\n    436: 0.022217961917098165546657778261, 437: 0.022191470786345319097112348961, 438: 0.022172320003829324390044442363, 439: 0.022140018882983054477535043003, 440: 0.022119219009668641501832850044,\n    441: 0.022103197140136089008397100400, 442: 0.022080870677980352963606328896, 443: 0.022058132419865172306480901343, 444: 0.022025855149328300394836511485, 445: 0.022009317503037903037593678353,\n    446: 0.021986755947083251691218464749, 447: 0.021958265991916381828893373438, 448: 0.021936780037287257870744448295, 449: 0.021906556524391651675454645434, 450: 0.021878170510679808021358202373,\n    451: 0.021851998603060797984337266316, 452: 0.021844050429071449861265945900, 453: 0.021822188560549746584949560449, 454: 0.021789785085591826347522866893, 455: 0.021784715023646644305786477715,\n    456: 0.021762345306504867192027618671, 457: 0.021736119222546678974380075453, 458: 0.021721351306519111745337524473, 459: 0.021679836135736845661092858785, 460: 0.021655518990601112592322215037,\n    461: 0.021640081712112203344030542066, 462: 0.021601609266137023915603019115, 463: 0.021573800427821525499948618970, 464: 0.021544261123496090198680286439, 465: 0.021511020430517184363983536445,\n    466: 0.021491758131060982018547148551, 467: 0.021469537218493952747155651374, 468: 0.021447767870774872709918072674, 469: 0.021442484669164316332152538659, 470: 0.021412498282437624871710997490,\n    471: 0.021400184100945643441335360934, 472: 0.021383421551668217225306387000, 473: 0.021355001419267357595552718410, 474: 0.021332690950169483911435549243, 475: 0.021309491385006324306079943306,\n    476: 0.021283986054843579072747420800, 477: 0.021266368513719139762217020933, 478: 0.021252847892658428270944561735, 479: 0.021225867692614113303409832221, 480: 0.021202993097285452917749058966,\n    481: 0.021179922862132882456103799962, 482: 0.021157049874202139450165494786, 483: 0.021140786383162876443736271798, 484: 0.021116284642110598858745152860, 485: 0.021097602887796697833218813335,\n    486: 0.021078120213483722962104229358, 487: 0.021061086633128260914411531370, 488: 0.021034698408423612267441809149, 489: 0.021010063953815038044993996571, 490: 0.021000125238925065072298017461,\n    491: 0.020973872388856212396221490521, 492: 0.020955064880945878991166583113, 493: 0.020944029189315782078226970365, 494: 0.020918830040919286981741392392, 495: 0.020892651829300030744979208090,\n    496: 0.020869517522621605272082654198, 497: 0.020860719164140037754921200166, 498: 0.020828916089058836766870209012, 499: 0.020793736958559955092252964200, 500: 0.020779697786477576723778629946,\n    501: 0.020763895315993008214893842516, 502: 0.020737828248266975577453516665, 503: 0.020721441943213831067667922213, 504: 0.020693251846146589090154400217, 505: 0.020669949984295528930630807164,\n    506: 0.020645015670215254247656232723, 507: 0.020622451105094714293542383685, 508: 0.020596613479423901389541557346, 509: 0.020573062187390532145485125063, 510: 0.020540246296382534586108634279,\n    511: 0.020524434941827088606591486444, 512: 0.020508051115268899472636743942, 513: 0.020489442275356826390297314691, 514: 0.020468703772464809137527308983, 515: 0.020451217885907799638074269939,\n    516: 0.020422050079200140636808770641, 517: 0.020411607606633426878065721938, 518: 0.020400834617556697236091400083, 519: 0.020395722284213626511200920639, 520: 0.020375404423138170298419687191,\n    521: 0.020357233745065556345453332753, 522: 0.020347770604561796496897625899, 523: 0.020328227710253574662539337721, 524: 0.020319248618310499822598558354, 525: 0.020308264877176185452449703970,\n    526: 0.020287717586877138035195287918, 527: 0.020270082335564298517135580165, 528: 0.020254171388196264646141651198, 529: 0.020219739867038641510341672640, 530: 0.020206610781630880979592352044,\n    531: 0.020187871088901171483484232898, 532: 0.020162374359423076943448058987, 533: 0.020147023488640563906669366545, 534: 0.020137672127129520066022845518, 535: 0.020110910704116174753797552101,\n    536: 0.020099378335907983944720270383, 537: 0.020067525987997299370900846968, 538: 0.020048746805423463475476831984, 539: 0.020039334758652242471760610993, 540: 0.020021823084566423486560940436,\n    541: 0.019990059510644059185056059490, 542: 0.019971860632539188340265532143, 543: 0.019947123728155304741262128176, 544: 0.019928563724360743906682225980, 545: 0.019918618775271735677200336175,\n    546: 0.019897827802797069543581056880, 547: 0.019870679589388971428946468750, 548: 0.019851848219804439704122764937, 549: 0.019825008792702710606798755408, 550: 0.019807672338155458435207602730,\n    551: 0.019792604042147465543369230006, 552: 0.019777659441892802440276294124, 553: 0.019759734676033163495916375948, 554: 0.019755175752640678755132975793, 555: 0.019727282455869897251134851742,\n    556: 0.019714517483349964535589386284, 557: 0.019700600744853614636351669625, 558: 0.019674481207313941999217608968, 559: 0.019660821259872105533559858010, 560: 0.019658605329311913132868507968,\n    561: 0.019643294792062520671749261034, 562: 0.019636102746979281664480453561, 563: 0.019620047237248877906790680118, 564: 0.019604197008931883145709139046, 565: 0.019585172618235626782754170124,\n    566: 0.019572018640672778343609869855, 567: 0.019565033172685002188972507428, 568: 0.019544838916416805640492549246, 569: 0.019526232856979078051594758427, 570: 0.019508533871087089664263116822,\n    571: 0.019487175054926464045287662068, 572: 0.019469393585919683613881927162, 573: 0.019448034345373357185372140669, 574: 0.019432216344118874490499342252, 575: 0.019410347178486366029101273643,\n    576: 0.019390132594888085352069623604, 577: 0.019383960140962656818283386948, 578: 0.019357712238773236840430485802, 579: 0.019334308602987189204582065163, 580: 0.019318382583051953373008741819,\n    581: 0.019295298342752575406950732792, 582: 0.019283848536953743618625367945, 583: 0.019267889755314265622772074420, 584: 0.019247926865902439781204847571, 585: 0.019230272488535883644598078810,\n    586: 0.019211573142449990737284322705, 587: 0.019185324932114592187929785666, 588: 0.019169841597838940952964085748, 589: 0.019159781495014877962036642823, 590: 0.019144376088411274580378426481,\n    591: 0.019129962756147227408600548617, 592: 0.019109962194278504572796308229, 593: 0.019102207636575821058459644842, 594: 0.019085496934730710125866218984, 595: 0.019065810984877064980631034797,\n    596: 0.019052974788866087634248111647, 597: 0.019046101391334905818654541463, 598: 0.019027181397767250138410239739, 599: 0.019018384780189938935674833170, 600: 0.018995948824214276328477016848,\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[0], 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\"ccq|{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[0], 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"}}