{"id":"hypersphere-packing-4d","name":"Equal hyperspheres in a 4-D ball","family":"combinatorics","description":"Place n hyperspheres in the unit ball in 4 dimensions 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 hyperspheres in a 4-D ball\n\n## Goal\n\n`pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, ...]]`: the\ncentres of `n` hyperspheres inside the unit ball in 4 dimensions (4 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 = 5, 8, 12, 16, 20, 25, 30, 40, 50, 60, 80, 100`, 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 `hsp4`, 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 300) 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 hypersphere-packing-4d. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nGenerated by tools/packomania_import.py from https://packomania.com/hsp4/hsp4.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 \"5,8,12,16,20,25,30,40,50,60,80,100\")\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\", \"5,8,12,16,20,25,30,40,50,60,80,100\").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 = 4\n\n# Best-known values: equal objects in the unit ball in 4 dimensions. Source: Packomania (E. Specht),\n# https://packomania.com/hsp4/hsp4.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.441518440112,\n    6: 0.414213562373, 7: 0.414213562373, 8: 0.414213562373, 9: 0.392944640987, 10: 0.392280956059,\n    11: 0.382838054889, 12: 0.379795897113, 13: 0.370481999157, 14: 0.368408375855, 15: 0.362916293358,\n    16: 0.356226222001, 17: 0.351532811847, 18: 0.349469104305, 19: 0.347197094453, 20: 0.347197094453,\n    21: 0.339546206978, 22: 0.333802699406, 23: 0.333333333333, 24: 0.333333333333, 25: 0.333333333333,\n    26: 0.324771535266, 27: 0.323945806542, 28: 0.319877628168, 29: 0.317459037864, 30: 0.315990168743,\n    31: 0.313159704035, 32: 0.311458932449, 33: 0.310154401219, 34: 0.308815216672, 35: 0.306285269828,\n    36: 0.303143148415, 37: 0.301235817121, 38: 0.300651321630, 39: 0.297669990199, 40: 0.295854844085,\n    41: 0.294797502608, 42: 0.293368844389, 43: 0.292419588808, 44: 0.291127113403, 45: 0.289236012044,\n    46: 0.286691165360, 47: 0.284970492933, 48: 0.283980525334, 49: 0.282540848919, 50: 0.281364857635,\n    51: 0.281261778192, 52: 0.278712353673, 53: 0.277952002667, 54: 0.276798004181, 55: 0.275874520804,\n    56: 0.273814710292, 57: 0.272711368137, 58: 0.272039211500, 59: 0.271059814521, 60: 0.270294660358,\n    61: 0.269622572869, 62: 0.268830626376, 63: 0.268114739680, 64: 0.266800405039, 65: 0.265294765188,\n    66: 0.264968466676, 67: 0.264026543809, 68: 0.262885925177, 69: 0.261916266401, 70: 0.261266627691,\n    71: 0.260636725181, 72: 0.260127117620, 73: 0.259369077971, 74: 0.258522851648, 75: 0.258082894946,\n    76: 0.257688781287, 77: 0.257434674091, 78: 0.256958022526, 79: 0.256468324828, 80: 0.255463163131,\n    81: 0.254058669351, 82: 0.252894034506, 83: 0.252008330509, 84: 0.251296923021, 85: 0.250610150755,\n    86: 0.249710499519, 87: 0.249149531018, 88: 0.248505598356, 89: 0.247998099891, 90: 0.247386955229,\n    91: 0.246960900415, 92: 0.246689832003, 93: 0.246502468889, 94: 0.245932827006, 95: 0.245100274372,\n    96: 0.244513498515, 97: 0.243874998759, 98: 0.243524972021, 99: 0.243259915388, 100: 0.243022037871,\n    101: 0.242327122009, 102: 0.241661468889, 103: 0.241051212866, 104: 0.240535464233, 105: 0.240195408090,\n    106: 0.239472470586, 107: 0.238986214814, 108: 0.238490717810, 109: 0.238116740820, 110: 0.237733257728,\n    111: 0.237355353009, 112: 0.237131194237, 113: 0.236792514357, 114: 0.236630043629, 115: 0.236364128573,\n    116: 0.236222422236, 117: 0.236108284019, 118: 0.236077896536, 119: 0.236068068183, 120: 0.236067977500,\n    121: 0.236067977500, 122: 0.236067977500, 123: 0.236067977500, 124: 0.236067977500, 125: 0.236067977500,\n    126: 0.236067977500, 127: 0.236067977500, 128: 0.236067977500, 129: 0.231651340790, 130: 0.231357014792,\n    131: 0.229728590394, 132: 0.228922953625, 133: 0.227953914564, 134: 0.227351412942, 135: 0.226922653844,\n    136: 0.226201706521, 137: 0.225752991090, 138: 0.225246166112, 139: 0.224938240752, 140: 0.224518599354,\n    141: 0.224016561889, 142: 0.224009237740, 143: 0.224009237740, 144: 0.224009237740, 145: 0.224009237740,\n    146: 0.222552396380, 147: 0.222230775041, 148: 0.221806081573, 149: 0.221581652790, 150: 0.221322459749,\n    151: 0.221156600901, 152: 0.220960306508, 153: 0.220858357788, 154: 0.220677273610, 155: 0.220570761438,\n    156: 0.220308265077, 157: 0.219922039177, 158: 0.219265888196, 159: 0.218842806513, 160: 0.218358476129,\n    161: 0.217891658736, 162: 0.217540823657, 163: 0.217115168538, 164: 0.216915247633, 165: 0.216544096525,\n    166: 0.216234104242, 167: 0.216116299209, 168: 0.215990389718, 169: 0.215785895566, 170: 0.215589695168,\n    171: 0.215441346347, 172: 0.215283327160, 173: 0.215123800036, 174: 0.214963144967, 175: 0.214479938085,\n    176: 0.213572614060, 177: 0.213176991646, 178: 0.212946462894, 179: 0.212786720718, 180: 0.212694219639,\n    181: 0.212260374152, 182: 0.211886963127, 183: 0.211388144925, 184: 0.211219475545, 185: 0.211098797707,\n    186: 0.210974452576, 187: 0.210842684779, 188: 0.210577303068, 189: 0.210238549209, 190: 0.209897197672,\n    191: 0.209705533764, 192: 0.209246565087, 193: 0.208883620176, 194: 0.208471720939, 195: 0.208201733458,\n    196: 0.207769000003, 197: 0.207577856839, 198: 0.207363289662, 199: 0.207237988509, 200: 0.207171250658,\n    201: 0.207033547283, 202: 0.206950551663, 203: 0.206826275050, 204: 0.206669089615, 205: 0.206513135301,\n    206: 0.205971347322, 207: 0.205680470429, 208: 0.205326174942, 209: 0.204873955169, 210: 0.204754919947,\n    211: 0.204554129122, 212: 0.204282473989, 213: 0.204053178162, 214: 0.203884464476, 215: 0.203682998566,\n    216: 0.203582040585, 217: 0.203438871092, 218: 0.203249074120, 219: 0.203077482827, 220: 0.202684437558,\n    221: 0.202442735831, 222: 0.202231971063, 223: 0.202080362450, 224: 0.201963483182, 225: 0.201799219541,\n    226: 0.201601959620, 227: 0.201442633079, 228: 0.201229175588, 229: 0.200948660213, 230: 0.200703953344,\n    231: 0.200469707763, 232: 0.200198460569, 233: 0.199881165280, 234: 0.199518174987, 235: 0.199132267633,\n    236: 0.199043512610, 237: 0.198816768626, 238: 0.198618169475, 239: 0.198409763193, 240: 0.198296277128,\n    241: 0.198168862783, 242: 0.198080781303, 243: 0.197943065870, 244: 0.197626510067, 245: 0.197471541826,\n    246: 0.197281067718, 247: 0.197007638164, 248: 0.196957374644, 249: 0.196789909070, 250: 0.196647342526,\n    251: 0.196483284240, 252: 0.196419092207, 253: 0.196090977289, 254: 0.195925475109, 255: 0.195739634189,\n    256: 0.195457675033, 257: 0.195348467651, 258: 0.195241428378, 259: 0.195134753841, 260: 0.194923256104,\n    261: 0.194780312043, 262: 0.194569235607, 263: 0.194252794272, 264: 0.193945031204, 265: 0.193821526678,\n    266: 0.193616836431, 267: 0.193334818158, 268: 0.193195426079, 269: 0.193044690391, 270: 0.192897916042,\n    271: 0.192672648784, 272: 0.192419764302, 273: 0.192204193016, 274: 0.192131554148, 275: 0.191931092256,\n    276: 0.191793782372, 277: 0.191693753237, 278: 0.191568585500, 279: 0.191418109175, 280: 0.191286022130,\n    281: 0.191164050267, 282: 0.190918796673, 283: 0.190682901353, 284: 0.190411059207, 285: 0.190162824429,\n    286: 0.190015795234, 287: 0.189854910552, 288: 0.189757878142, 289: 0.189698103066, 290: 0.189544054026,\n    291: 0.189311206202, 292: 0.189189285138, 293: 0.189107605443, 294: 0.188826715133, 295: 0.188587142981,\n    296: 0.188377529662, 297: 0.188258501287, 298: 0.188158854076, 299: 0.187991586199, 300: 0.187648382196,\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(sum(x * x for x in c))\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\"hsp4|{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 = 4\n\n\ndef _boundary(c):\n    return 1.0 - math.sqrt(sum(x * x for x in c))\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"}}