Equal circles in a square (large n)

# Equal circles in a square (large n) ## Goal `pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, ...]]`: the centres of `n` circles inside the unit square [0, 1]² (2 coordinates each). All objects share one radius, which the eval derives as r = min( distance of every centre to the boundary, half the smallest pairwise distance ) You do not return a radius; the eval derives the largest feasible one from your centres, so there is nothing to fudge. Make it as large as possible for every `n` you are handed. ## Metric The eval runs your `pack` on a fixed set of values, `n = 300, 500, 750, 999, 1500, 2000, 3000, 5000, 7498, 9996`, each with the given time budget (45 s by default), validates the result, and reports metric = mean over n of value(n) / record(n) where `record(n)` is the best-known value on Packomania (Eckard Specht's table, maintained since 2011; table `csq`, fetched 2026-09-06). `1.0` matches the record; above `1.0` is a new record candidate, listed under `records_beaten`. A hub-verified one is worth reporting to Packomania with your ledger entry as provenance. The hub verifies with a different `seed`, so your method must be robust to its starting point. The full records table (n up to 9996) is in `eval.py`. ## Constraints - Standard library only. No numpy, no scipy, no subprocess. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval kills the run if the whole set overruns. - Deterministic given `seed`: use `random.Random(seed)`, not the global RNG. - Every centre must lie inside the container. Objects may touch; they may not overlap. ## Large n This is the large-n variant. Records here were mostly set by long offline optimisation runs, and that is a legitimate way to attack it: your `pack.py` may embed coordinates you found during your attempt (a stored configuration is a solver), as long as it returns them within the budget and the eval can derive the radius. The eval's overlap check is a cell list, so n = 10 000 is validated in seconds; your own local checks should do the same. ## Where the frontier is n <= 30 are proven optimal. Above that every entry is "best known", found by numerical search, and Packomania's history shows improvements landing mostly at larger `n`. Budget your time per `n` deliberately; the O(n²) checks and the number of local optima both grow. ## Ideas that are known to matter (check the journal before repeating one) - Energy minimisation: treat objects as repelling points, minimise a soft overlap penalty with gradient descent, then polish by maximising the minimum scaled distance directly. - Basin hopping / perturb-and-repolish from the current best; keep a small population. - Start from structured arrangements (lattices, rings, shells) as well as random. - Identify the binding contacts and solve the equal-distance conditions exactly for the last digits. - Spend more of the budget on the `n` values whose ratio is lowest. Write one honest line in `NOTES.md`: the idea, and which `n` it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.