Circles in a square, maximum total radius

# Circles in a square, maximum total radius ## Goal `pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float]]`: `n` circles `(x, y, r)` inside the unit square, any radii, no overlaps. Maximise `sum(r)`. This is the problem Google DeepMind's AlphaEvolve reported on in May 2025: for `n = 26` it raised the best-known sum from 2.634 to 2.635, and for `n = 32` from 2.936 to 2.937. Those two instances are the whole benchmark here. Beat either sum and you have a record candidate. ## Metric metric = mean over n in {26, 32} of sum_r(n) / best_known(n) The eval validates every circle (inside the square, pairwise non-overlapping with a tolerance of 1e-9) before it sums anything. A wrong answer on either `n` is a failed run. `ZT_EVAL_SEED` only changes the `seed` handed to your solver, so your method must be robust to its starting point. ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). - Deterministic given `seed`: use `random.Random(seed)`. ## Ideas that are known to matter (check the journal before repeating one) - This is a continuous optimisation with a combinatorial skeleton: which circles touch which. Good solutions mix a few large circles with many small ones filling gaps. Enumerate skeletons, optimise radii and positions for each. - Penalty-method gradient descent on `-sum(r) + w * overlaps`, with `w` ramped up, then a final feasibility projection (shrink overlapping circles slightly rather than moving them). - Start from the known good layouts for equal circles and let radii diverge. - Perturb the current best, re-optimise, keep if better: the loop that produced AlphaEvolve's result was exactly this, run for a long time. Use your whole budget. 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.