{"id":"triangles-in-triangle-side","name":"Unit equilateral triangles in an equilateral triangle, minimum container side","family":"combinatorics","description":"Erich Friedman's Packing Center problem: pack n unit equilateral triangles, any orientation, into the smallest equilateral triangle, for 24 values of n between 6 and 50 whose best-known packing is not proven optimal. Scored as best-known side / your side, averaged over n.","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 equilateral triangles in an equilateral triangle, minimum container side\n\n## Goal\n\n`pack.py` exposes `pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float]]`:\n`n` unit equilateral triangles `(cx, cy, theta)`, where `(cx, cy)` is the centre (centroid) and\n`theta` is the direction, in **radians**, from the centre to the first vertex; the vertices are\n`(cx, cy) + (1/sqrt(3)) (cos(theta + 2 pi k / 3), sin(theta + 2 pi k / 3))` for `k = 0, 1, 2`, so\n`theta = pi/2` is an upward-pointing triangle and `theta = -pi/2` a downward one. Interiors must be\npairwise disjoint (touching is fine). The container is the smallest **upward-pointing** equilateral\ntriangle that holds every vertex you return; the eval derives its side `s` from your placements,\nyou never report it. Minimise `s`.\n\nThis is \"Triangles in Triangles\" from Erich Friedman's Packing Center. `s(n)` is the side of the\nsmallest equilateral triangle containing `n` unit equilateral triangles. `s(k^2) = k` is trivial\nand `s(5) = 1 + sqrt(3)` is proven (Friedman, 1997); the page says \"most of these have not been\nproven\". The 24 instances here are the values of `n` between 6 and 50 whose record is a\nnon-trivial construction and is not marked proven. Several rows were improved as recently as\nApril-June 2026. Beat any row and you have a new Packing Center record.\n\n## Metric\n\n    metric = mean over the 24 instances of  best_known(n) / s(n)\n\n`s(n)` is computed by pushing the three edges of an upward-pointing equilateral triangle in until\neach touches one of your `3n` vertices; by Viviani's theorem the height of that triangle is minus the\nsum of the three edge offsets, and `s = height / (sqrt(3)/2)`. A packing that matches a record scores\n`1.0` on that `n` (a hair under it where the record is only known as a truncated decimal, see the\ntable) and anything better scores above `1.0`. The eval validates every triangle before it measures\nanything: finite numbers, and no pair of triangles overlapping by more than `EPS = 1e-9`, tested\nwith the separating axis theorem on the six edge normals, the same geometry and tolerance as this\nrepository's square-packing packs. Touching is fine and penetration up to `EPS` is forgiven. A wrong\nanswer on any `n` is a failed run. `ZT_EVAL_SEED` only changes the `seed` handed to your solver, so\nyour method must be robust to its starting point.\n\nThe container's orientation is fixed (pointing up) but yours is not: rotate and translate the whole\npacking freely; only the minimal enclosing upward triangle is measured.\n\n## Records\n\nSource: https://erich-friedman.github.io/packing/triintri/, read 2026-09-07. Where the page gives a\nclosed form the eval evaluates it in full precision. Where it gives only a decimal with a trailing\n`+` (its notation for a truncated value, e.g. `3.992+` means `3.992 <= s < 3.993`), the eval uses the\nprinted digits verbatim: reproducing the true record then scores at most about `0.9998` on that `n`,\nand `records_beaten` is only flagged when you get below the printed digits. None of these rows is\nmarked proven on the page.\n\n| n | best known s | exact form (per the page) | found by |\n|---|---|---|---|\n| 6 | 2.977+ | 13/8 + 3 sqrt(13)/8 | Maurizio Morandi, August 2008 |\n| 10 | 3.5 | 7/2 | Erich Friedman, 1997 |\n| 11 | 3.722+ | 9/4 + 9 sqrt(21)/28 | Erich Friedman, 1997 |\n| 12 | 3.879+ | 2 + 2 cos(pi/9) | David W. Cantrell, July 2007 |\n| 13 | 3.992+ | none given (truncated decimal) | Maurizio Morandi, May 2008 |\n| 17 | 4.465+ | none given (truncated decimal) | Maurizio Morandi, May 2008 |\n| 18 | 4.5 | 9/2 | Erich Friedman, 1997 |\n| 19 | 4.666+ | 14/3 | Maurizio Morandi, May 2008 |\n| 20 | 4.861+ | 33/8 + 9 sqrt(21)/56 | Maurizio Morandi, May 2008 |\n| 21 | 4.923+ | none given (truncated decimal) | Maurizio Morandi, May 2008 |\n| 22 | 4.996+ | none given (truncated decimal) | Maurizio Morandi, May 2008 |\n| 26 | 5.406+ | none given (truncated decimal) | Joah Frenzley, April 2026 |\n| 29 | 5.666+ | 17/3 | David W. Cantrell, July 2007 |\n| 30 | 5.75 | 23/4 | Maurizio Morandi, May 2008 |\n| 31 | 5.90766+ | none given (truncated decimal) | Thomas Schadt, June 2026 |\n| 32 | 5.94593+ | none given (truncated decimal) | Maurizio Morandi, May 2026 |\n| 33 | 5.99759+ | none given (truncated decimal) | Maurizio Morandi, June 2026 |\n| 37 | 6.333+ | 19/3 | Ian Watson, April 2026 |\n| 38 | 6.42823+ | none given (truncated decimal) | Thomas Schadt, June 2026 |\n| 41 | 6.666+ | 20/3 | Emerson Connelly, May 2026 |\n| 42 | 6.75 | 27/4 | Emerson Connelly, May 2026 |\n| 43 | 6.8 | 34/5 | Emerson Connelly, May 2026 |\n| 44 | 6.93076+ | none given (truncated decimal) | Thomas Schadt, June 2026 |\n| 50 | 7.32732+ | 7 + sqrt(21)/14 | Maurizio Morandi, May 2026 |\n\nNot included, for the record: `s = k` for `n = k^2 - 2, k^2 - 1, k^2` (the trivial tiling; the page\nlists these as \"Trivial\"), `s(5) = 1 + sqrt(3)` (proven), and `n = 27, 28` (`s = 11/2`, Friedman\n1997) and `n = 39, 40` (`s = 13/2`, Friedman, April 2026), which share a packing with a larger `n`\nand were left out to keep the set to 24. Also `n = 45, 46` (Morandi, May-June 2026: `6.95922+`,\n`6.99837+`), left out only for size.\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=6,10 python eval.py` runs a subset of the instances.\n- `ZT_EVAL_PER_N_SECONDS=1 python eval.py` shortens the per-`n` budget (default 4 s, so the full\n  24-instance eval takes about 100 s of solver time).\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- The rational records (`7/2`, `9/2`, `14/3`, `17/3`, `23/4`, `19/3`, `20/3`, `27/4`, `34/5`) are\n  the trivial tiling of a side-`k` triangle with one or two rows re-packed by triangles shifted half\n  a unit or flipped: `k` triangles of a row can be replaced by `k + 1` up-and-down triangles in a\n  strip of height `sqrt(3)/2` only with slack, so the trick is a row of height slightly more than\n  `sqrt(3)/2` that holds one extra triangle. Write the families down before searching.\n- The remaining records use triangles rotated by angles other than multiples of 60 degrees wedged\n  into corners; the `2 + 2 cos(pi/9)` record for `n = 12` is the model case.\n- Simulated annealing on `(cx, cy, theta)` with a penalty for overlap plus the container side (the\n  three edge offsets are cheap to update incrementally), shrinking the container whenever the\n  packing is feasible, is what produced the 2026 records; restart often.\n- Finish every candidate with a feasibility projection that pushes overlapping pairs apart along\n  their separating axis, then re-measure the container.\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 triangles-in-triangle-side. 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 4)\n  ZT_EVAL_NS               comma-separated n values (default: the 24 instances below)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport math\nimport os\nimport random\nimport sys\nimport time\nfrom pathlib import Path\n\nDEFAULT_NS = \"6,10,11,12,13,17,18,19,20,21,22,26,29,30,31,32,33,37,38,41,42,43,44,50\"\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_N_SECONDS\", \"4\"))\nNS = [int(x) for x in os.environ.get(\"ZT_EVAL_NS\", DEFAULT_NS).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\nSQRT3 = math.sqrt(3.0)\nCIRCUMRADIUS = 1.0 / SQRT3          # of a unit equilateral triangle\nHEIGHT = SQRT3 / 2.0                # of a unit equilateral triangle\n\n# Best-known side s(n) of an equilateral triangle holding n unit equilateral triangles. Source: Erich\n# Friedman's Packing Center, \"Triangles in Triangles\" (https://erich-friedman.github.io/packing/triintri/),\n# read 2026-09-07. Where the page gives a closed form it is evaluated here in full precision; where it\n# gives only a decimal with a trailing \"+\" (a truncation), that truncated decimal is used verbatim, so\n# matching the true record scores a hair under 1.0 and \"beaten\" is only flagged below the printed digits.\n# None of these n is proven optimal there (\"Found by\", not \"Proved by\"; the page says \"Most of these\n# have not been proven\"). Update when a hub-verified submission beats one.\nRECORDS = {\n    6: 13 / 8 + 3 * math.sqrt(13) / 8,        # 2.977+  Maurizio Morandi, August 2008\n    10: 3.5,                                   # 7/2     Erich Friedman, 1997\n    11: 9 / 4 + 9 * math.sqrt(21) / 28,        # 3.722+  Erich Friedman, 1997\n    12: 2 + 2 * math.cos(math.pi / 9),         # 3.879+  David W. Cantrell, July 2007\n    13: 3.992,                                 # 3.992+  Maurizio Morandi, May 2008 (truncated)\n    17: 4.465,                                 # 4.465+  Maurizio Morandi, May 2008 (truncated)\n    18: 4.5,                                   # 9/2     Erich Friedman, 1997\n    19: 14 / 3,                                # 4.666+  Maurizio Morandi, May 2008\n    20: 33 / 8 + 9 * math.sqrt(21) / 56,       # 4.861+  Maurizio Morandi, May 2008\n    21: 4.923,                                 # 4.923+  Maurizio Morandi, May 2008 (truncated)\n    22: 4.996,                                 # 4.996+  Maurizio Morandi, May 2008 (truncated)\n    26: 5.406,                                 # 5.406+  Joah Frenzley, April 2026 (truncated)\n    29: 17 / 3,                                # 5.666+  David W. Cantrell, July 2007\n    30: 5.75,                                  # 23/4    Maurizio Morandi, May 2008\n    31: 5.90766,                               # 5.90766+  Thomas Schadt, June 2026 (truncated)\n    32: 5.94593,                               # 5.94593+  Maurizio Morandi, May 2026 (truncated)\n    33: 5.99759,                               # 5.99759+  Maurizio Morandi, June 2026 (truncated)\n    37: 19 / 3,                                # 6.333+  Ian Watson, April 2026\n    38: 6.42823,                               # 6.42823+  Thomas Schadt, June 2026 (truncated)\n    41: 20 / 3,                                # 6.666+  Emerson Connelly, May 2026\n    42: 6.75,                                  # 27/4    Emerson Connelly, May 2026\n    43: 6.8,                                   # 34/5    Emerson Connelly, May 2026\n    44: 6.93076,                               # 6.93076+  Thomas Schadt, June 2026 (truncated)\n    50: 7 + math.sqrt(21) / 14,                # 7.32732+  Maurizio Morandi, May 2026\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        # 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 vertices(cx: float, cy: float, theta: float) -> list[tuple[float, float]]:\n    \"\"\"The three vertices of the unit equilateral triangle centred at (cx, cy), counter-clockwise.\n    theta is the direction of the first vertex from the centre; theta = pi/2 points up.\"\"\"\n    return [(cx + CIRCUMRADIUS * math.cos(theta + k * 2 * math.pi / 3),\n             cy + CIRCUMRADIUS * math.sin(theta + k * 2 * math.pi / 3)) for k in range(3)]\n\n\ndef axes(pts: list[tuple[float, float]]) -> list[tuple[float, float]]:\n    \"\"\"Unit normals of the three edges.\"\"\"\n    out = []\n    for i in range(3):\n        (x1, y1), (x2, y2) = pts[i], pts[(i + 1) % 3]\n        nx, ny = -(y2 - y1), x2 - x1\n        nrm = math.hypot(nx, ny)\n        if nrm > 1e-12:\n            out.append((nx / nrm, ny / nrm))\n    return out\n\n\ndef project(pts: list[tuple[float, float]], ax: tuple[float, float]) -> tuple[float, float]:\n    ps = [x * ax[0] + y * ax[1] for x, y in pts]\n    return min(ps), max(ps)\n\n\ndef overlap(pa: list, pb: list) -> bool:\n    \"\"\"Separating axis theorem on two triangles (given by vertices); True if they share interior deeper than EPS.\"\"\"\n    for ax in axes(pa) + axes(pb):\n        lo1, hi1 = project(pa, ax)\n        lo2, hi2 = project(pb, 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\n# Inward unit normals of an upward-pointing equilateral container (bottom, right, left edge).\nCONTAINER_NORMALS = [(0.0, 1.0), (-SQRT3 / 2, -0.5), (SQRT3 / 2, -0.5)]\n\n\ndef container_side(pts: list[list[tuple[float, float]]]) -> float:\n    \"\"\"Side of the smallest upward-pointing equilateral triangle containing every vertex.\n    Each edge is pushed in until it touches a vertex; by Viviani's theorem the height of the\n    resulting triangle is minus the sum of the three edge offsets.\"\"\"\n    offsets = [min(nx * x + ny * y for p in pts for x, y in p) for nx, ny in CONTAINER_NORMALS]\n    height = -sum(offsets)\n    return height / HEIGHT\n\n\ndef validate(tris: list, n: int) -> float:\n    \"\"\"Check the packing and return the side of the smallest equilateral triangle containing it.\"\"\"\n    if not isinstance(tris, (list, tuple)) or len(tris) != n:\n        fail(f\"pack({n}) must return {n} triangles\", \"wrong_answer\")\n    centres, pts = [], []\n    for t in tris:\n        try:\n            cx, cy, theta = float(t[0]), float(t[1]), float(t[2])\n        except Exception:\n            fail(f\"pack({n}) returned a non-triangle {t!r}\", \"wrong_answer\")\n        if not all(map(math.isfinite, (cx, cy, theta))):\n            fail(f\"pack({n}) returned a triangle with non-finite parameters\", \"wrong_answer\")\n        centres.append((cx, cy))\n        pts.append(vertices(cx, cy, theta))\n    for i in range(n):\n        for j in range(i + 1, n):\n            # cheap circumcircle rejection first, then the exact SAT test\n            if math.hypot(centres[i][0] - centres[j][0], centres[i][1] - centres[j][1]) >= 2 * CIRCUMRADIUS:\n                continue\n            if overlap(pts[i], pts[j]):\n                fail(f\"pack({n}): triangles {i} and {j} overlap\", \"wrong_answer\")\n    return container_side(pts)\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\"triside|{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            tris = 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        s = validate(tris, n)\n        if s <= 0:\n            fail(f\"pack({n}) returned a degenerate packing\", \"wrong_answer\")\n        rec = RECORDS[n]\n        per_n[n] = {\"side\": round(s, 10), \"record\": round(rec, 12), \"ratio\": round(rec / s, 6), \"seconds\": round(elapsed, 2)}\n        if s < rec - 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: the trivial packing. A side-k equilateral triangle tiles into k*k unit triangles\n(row r from the bottom holds k-r pointing up and k-r-1 pointing down); take k = ceil(sqrt(n)) and\nthe first n of them. Scores about 0.85-0.99 of the records. Beat it.\"\"\"\n\nimport math\n\nH = math.sqrt(3) / 2   # height of a unit equilateral triangle\n\n\ndef pack(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float]]:\n    k = math.ceil(math.sqrt(n))\n    out = []\n    for r in range(k):\n        y0 = r * H\n        for j in range(k - r):                       # upward triangles: centroid H/3 above the row's base\n            out.append((r / 2 + j + 0.5, y0 + H / 3, math.pi / 2))\n        for j in range(k - r - 1):                   # downward triangles: apex on the row's base\n            out.append((r / 2 + j + 1.0, y0 + 2 * H / 3, -math.pi / 2))\n    return out[:n]\n"}}