{"id":"unit-cube-packing","name":"Unit cubes in the smallest cube","family":"combinatorics","description":"Erich Friedman's cubes-in-cubes problem (AlphaEvolve repository problem 35, packing in a dilate): place n unit cubes, freely rotated, with disjoint interiors so that their axis-aligned bounding cube is as small as possible, for n in {9, 10, 11, 12, 13, 14, 28}. Scored against the best-known side lengths.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"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":"# Unit cubes in the smallest cube\n\n## Goal\n\n`pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float, float, float, float]]`:\n`n` unit cubes `(x, y, z, ax, ay, az)`. `(x, y, z)` is the centre; `ax, ay, az` are Euler angles in\n**degrees**, applied as `R = Rz(az) @ Ry(ay) @ Rx(ax)` to the axis-aligned cube `[-1/2, 1/2]^3`\nbefore translating (the AlphaEvolve convention, so its constructions port unchanged). Interiors\nmust be pairwise disjoint (touching is fine). The container is the smallest axis-aligned cube\naround all `8n` vertices, so `side(n) = max over the three coordinate axes of (max - min)`.\nMinimise `side(n)`. Rotating the whole configuration is free, so an axis-aligned container loses\nnothing.\n\n`s(n)`, the smallest such side, is Erich Friedman's \"Cubes in Cubes\" problem (Packing Center),\nand problem 35 (\"packing in a dilate\", arXiv:2511.02864 section 6.19) of the AlphaEvolve repository\nof problems. AlphaEvolve's contribution was `n = 11`: its construction (in the repository notebook;\nthe eval below scores it at side 2.894531) beat Friedman's 1998 table and was listed as a world\nrecord, and has since been improved twice, most recently by Haowei Lin (July 2026). For every\n`n < 34` not in the table the trivial `ceil(n^(1/3))` grid is still the best known, so the whole\nrange is soft.\n\n## Metric\n\n    metric = mean over n in {9, 10, 11, 12, 13, 14, 28} of  best_known(n) / side(n)\n\nThe eval validates every cube before measuring anything: six finite numbers, and no pair of cubes\noverlapping by more than `EPS = 1e-9`, tested with the full separating axis theorem (3 + 3 face\nnormals plus the 9 edge-edge cross products, skipping cross products of nearly parallel edges as\nthe AlphaEvolve verifier does). Touching is fine and penetration up to `EPS` is forgiven, the\nconvention of this repository's other packing evals (the AlphaEvolve notebook instead demanded a\nstrict `1e-9` gap). Then it recomputes `side(n)` from the vertices itself; nothing your solver\nreports is trusted. A wrong answer on any `n` is a failed run. `ZT_EVAL_SEED` only changes\nthe `seed` handed to your solver, so your method must be robust to its starting point.\n\n## Records\n\nSource: Erich Friedman, \"Cubes in Cubes\", Packing Center (fetched 2026-09-07). None of these is\nproven optimal; the page marks nothing as proven, and the only trivially proven values are\n`s(8) = 2` and `s(27) = 3` (volume). Values written `x+` on the page are used as written, so a\npacking exactly matching the record scores `1.0` up to the truncation.\n\n| n | best known side | found by |\n|---|---|---|\n| 9 | 2 + 1/sqrt(2) = 2.70710678... | Erich Friedman, 1998 |\n| 10 | 2 + 1/sqrt(2) = 2.70710678... | Erich Friedman, 1998 (same packing as n = 9) |\n| 11 | 2.88295 | Haowei Lin, July 2026 (previous: AlphaEvolve 2.894531, problem 35) |\n| 12 | 2.93277 | Haowei Lin, July 2026 |\n| 13 | 2.956 | Erich Friedman, 1998 |\n| 14 | 2 + 7 sqrt(2)/10 = 2.98994949... | Erich Friedman, 1998 |\n| 28 | 3 + 1/sqrt(2) = 3.70710678... | Erich Friedman, 1998 (same packing serves n = 28..33) |\n\n## Constraints\n\n- Standard library only. No numpy, no scipy. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The eval kills a call at `1.25 * time_budget + 3 s`.\n- Deterministic given `seed`: use `random.Random(seed)`.\n\n## Iterating quickly\n\n- `ZT_EVAL_NS=9,11 python eval.py` runs a subset of the instances.\n- `ZT_EVAL_PER_N_SECONDS=2 python eval.py` shortens the per-`n` budget (default 15 s, so the\n  full seven-instance eval takes about 105 s of solver time).\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Friedman's `2 + 1/sqrt(2)` packings put eight axis-aligned cubes in the corners and stand the\n  rest on a face diagonal (45 degrees about one axis) in the slack. The `n = 11` and `n = 12`\n  records tilt the inner cubes off every symmetry axis; the AlphaEvolve `n = 11` packing has the\n  three inner cubes at three unrelated orientations.\n- Squeeze loops: fix the corner cubes, move each inner cube towards the centre by bisection on the\n  overlap test, then shrink the corner cubes' bounding box uniformly by bisection. This is the\n  `squeeze_placements_3d` routine AlphaEvolve was given; write your own, it is short.\n- Simulated annealing over `(x, y, z, ax, ay, az)` with the penalty `side + w * overlap_depth`,\n  where overlap depth is the smallest projected penetration over the 15 SAT axes.\n- Snap angles to `{0, 45, 90, atan(1/sqrt(2)) = 35.264..} + multiples of 90` before a final polish.\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 unit-cube-packing. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED             seed handed to pack()\n  ZT_EVAL_PER_N_SECONDS    time budget per n (default 15)\n  ZT_EVAL_NS               comma-separated n values (default \"9,10,11,12,13,14,28\")\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\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_N_SECONDS\", \"15\"))\nNS = [int(x) for x in os.environ.get(\"ZT_EVAL_NS\", \"9,10,11,12,13,14,28\").split(\",\")]\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nEPS = 1e-9\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\n# Best-known side of a cube containing n unit cubes. Source: Erich Friedman, \"Cubes in Cubes\",\n# Packing Center (fetched 2026-09-07): n=9,10 and 28 by Friedman 1998 (2+1/sqrt2, 3+1/sqrt2),\n# n=11 2.88295+ and n=12 2.93277+ by Haowei Lin (July 2026; n=11 previously AlphaEvolve's\n# 2.894531, repository problem 35), n=13 2.956+ and n=14 2+7sqrt2/10 by Friedman 1998.\n# None is proven optimal. Update when a hub-verified submission beats one.\nRECORDS = {9: 2 + math.sqrt(0.5), 10: 2 + math.sqrt(0.5), 11: 2.88295, 12: 2.93277, 13: 2.956,\n           14: 2 + 0.7 * math.sqrt(2), 28: 3 + math.sqrt(0.5)}\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        # dynamic imports and raw file/process access are not part of the problem either\n        ident = node.id if isinstance(node, ast.Name) else node.attr if isinstance(node, ast.Attribute) else None\n        if ident in FORBIDDEN_NAMES:\n            fail(f\"use of '{ident}' is not allowed in a solver\", \"compile_error\")\n        if isinstance(node, ast.ImportFrom) and node.level:\n            fail(\"relative imports are not allowed in a solver\", \"compile_error\")\n\n\ndef rotation(ax: float, ay: float, az: float) -> list[list[float]]:\n    \"\"\"R = Rz(az) @ Ry(ay) @ Rx(ax), angles in degrees (the AlphaEvolve convention).\"\"\"\n    rx, ry, rz = math.radians(ax), math.radians(ay), math.radians(az)\n    cx, sx, cy, sy, cz, sz = math.cos(rx), math.sin(rx), math.cos(ry), math.sin(ry), math.cos(rz), math.sin(rz)\n    mx = [[1, 0, 0], [0, cx, -sx], [0, sx, cx]]\n    my = [[cy, 0, sy], [0, 1, 0], [-sy, 0, cy]]\n    mz = [[cz, -sz, 0], [sz, cz, 0], [0, 0, 1]]\n\n    def mul(a, b):\n        return [[sum(a[i][k] * b[k][j] for k in range(3)) for j in range(3)] for i in range(3)]\n\n    return mul(mz, mul(my, mx))\n\n\nclass Cube:\n    __slots__ = (\"verts\", \"axes\", \"c\")\n\n    def __init__(self, x: float, y: float, z: float, ax: float, ay: float, az: float):\n        r = rotation(ax, ay, az)\n        self.c = (x, y, z)\n        self.axes = [(r[0][k], r[1][k], r[2][k]) for k in range(3)]  # face normals = columns of R\n        self.verts = [(x + sum(r[0][k] * s[k] for k in range(3)),\n                       y + sum(r[1][k] * s[k] for k in range(3)),\n                       z + sum(r[2][k] * s[k] for k in range(3)))\n                      for s in itertools.product((-0.5, 0.5), repeat=3)]\n\n\ndef project(verts, ax):\n    ps = [v[0] * ax[0] + v[1] * ax[1] + v[2] * ax[2] for v in verts]\n    return min(ps), max(ps)\n\n\ndef overlap(a: Cube, b: Cube) -> bool:\n    \"\"\"Full SAT for two boxes: 6 face normals and 9 edge-edge cross products.\"\"\"\n    cand = list(a.axes) + list(b.axes)\n    for u in a.axes:\n        for v in b.axes:\n            w = (u[1] * v[2] - u[2] * v[1], u[2] * v[0] - u[0] * v[2], u[0] * v[1] - u[1] * v[0])\n            nrm = math.sqrt(w[0] ** 2 + w[1] ** 2 + w[2] ** 2)\n            if nrm > 1e-6:  # nearly parallel edges are covered by the face normals\n                cand.append((w[0] / nrm, w[1] / nrm, w[2] / nrm))\n    for ax in cand:\n        lo1, hi1 = project(a.verts, ax)\n        lo2, hi2 = project(b.verts, ax)\n        if hi1 <= lo2 + EPS or hi2 <= lo1 + EPS:\n            return False  # separated (touching, or overlapping by at most EPS, counts as separated)\n    return True\n\n\ndef validate(placements: list, n: int) -> float:\n    if not isinstance(placements, (list, tuple)) or len(placements) != n:\n        fail(f\"pack({n}) must return {n} cubes\", \"wrong_answer\")\n    cubes = []\n    for p in placements:\n        try:\n            vals = [float(p[i]) for i in range(6)]\n            if len(p) != 6:\n                raise ValueError\n        except Exception:\n            fail(f\"pack({n}) returned a non-cube {p!r}\", \"wrong_answer\")\n        if not all(map(math.isfinite, vals)):\n            fail(f\"pack({n}) returned a cube with non-finite parameters\", \"wrong_answer\")\n        cubes.append(Cube(*vals))\n    for i in range(n):\n        for j in range(i + 1, n):\n            # cheap circumsphere rejection first (half-diagonal is sqrt(3)/2), then the exact SAT test\n            if math.dist(cubes[i].c, cubes[j].c) >= math.sqrt(3):\n                continue\n            if overlap(cubes[i], cubes[j]):\n                fail(f\"pack({n}): cubes {i} and {j} overlap\", \"wrong_answer\")\n    allv = [v for c in cubes for v in c.verts]\n    return max(max(v[k] for v in allv) - min(v[k] for v in allv) for k in range(3))\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    seed_int = random.Random(f\"cubes|{SEED}\").getrandbits(32)\n    per_n, beaten = {}, []\n    for n in NS:\n        if n not in RECORDS:\n            fail(f\"no record for n={n}\", \"error\")\n        t0 = time.perf_counter()\n        try:\n            placements = 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        side = validate(placements, n)\n        per_n[n] = {\"side\": round(side, 10), \"record\": round(RECORDS[n], 10), \"ratio\": round(RECORDS[n] / side, 6), \"seconds\": round(elapsed, 2)}\n        if side < RECORDS[n] - 1e-9:\n            beaten.append(n)\n    metric = sum(v[\"ratio\"] for v in per_n.values()) / len(per_n)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_n\": per_n, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"pack.py":"\"\"\"Baseline: axis-aligned cubes filling an m x m x m grid, m = ceil(n ** (1/3)); side m. Scores about\n0.90-0.99 of the records. Beat it.\"\"\"\n\nimport math\n\n\ndef pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float, float, float, float]]:\n    m = math.ceil(round(n ** (1 / 3), 9))\n    out = []\n    for k in range(m):\n        for j in range(m):\n            for i in range(m):\n                if len(out) < n:\n                    out.append((i + 0.5, j + 0.5, k + 0.5, 0.0, 0.0, 0.0))\n    return out\n"}}