{"id":"grid-no-isosceles","name":"Isosceles-free subsets of the n x n grid","family":"discrete-geometry","description":"AlphaEvolve repository problem 59: choose as many points of the n x n integer grid as possible so that no three of them form an isosceles triangle (flat triangles, i.e. a point midway between two others, count too). Scored against the best-known sizes for n in {16, 32, 64, 100}.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["solver.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":"# Isosceles-free subsets of the n x n grid\n\n## Goal\n\n`solver.py` exposes `solve(n: int, time_budget: float, seed: int) -> list[tuple[int, int]]`: a list\nof distinct grid points `(x, y)` with integer coordinates in `0..n-1` such that no three of them form\nan isosceles triangle. Maximise the number of points.\n\nThree distinct points `a, b, c` form a forbidden triangle when two of the three pairwise distances\nare equal, `|ab| = |bc|` for some labelling. Flat triangles count: a point midway between two others\nis `|ab| = |bc|` with `b` on the segment, so three points in arithmetic progression on any line are\nalso forbidden. Equivalently: for every point `a` of your set, the distances from `a` to all the\nother points must be pairwise distinct.\n\nThis is problem 59 of the AlphaEvolve repository of problems (Georgiev, Gomez-Serrano, Tao, Wagner,\n\"Mathematical exploration and discovery at scale\", arXiv:2511.02864, section 6.39), a question asked\nindependently by Wu, Ellenberg-Jain and possibly Erdos. Asymptotically only `n / sqrt(log n) <~\nC(n) <~ exp(-c (log n)^(1/9)) n^2` is known; even `C(n) < n^1.99` is open. Computationally, SAT\nsolvers settle `n <= 32`, the optimal sizes look linear (about `16n/9` was the guess in the\nPatternBoost paper), and the records for `n = 64` and `n = 100` were found by machine search after\nmonths of human attempts. AlphaEvolve found 112 points in the 64 x 64 grid (a size the PatternBoost\nauthors had been chasing for months) and 164 in the 100 x 100 grid, and the authors \"believe this is\nstill not optimal\".\n\n## Instances and records\n\nEvery instance is scored against the best-known size. `record_ratio` for an instance is\n`size / record`, so 1.0 is a match and above 1.0 is a new record.\n\n| n | best known | proven optimal | source |\n|---|---|---|---|\n| 16 | 28 | yes (SAT) | Charton, Ellenberg, Wagner, Williamson, \"PatternBoost\", arXiv:2411.00566, section 4.1, Figure 12; quoted as C(16) = 28 in arXiv:2511.02864 section 6.39 |\n| 32 | 56 | yes (SAT) | same, Figure 12; quoted as C(32) = 56 in arXiv:2511.02864 section 6.39 |\n| 64 | 112 | no | AlphaEvolve, arXiv:2511.02864 section 6.39 and repository problem 59 (notebook `sol_64`); previous best 110 (PatternBoost), 108 by classical search |\n| 100 | 164 | no | AlphaEvolve, arXiv:2511.02864 section 6.39 and repository problem 59 (notebook `sol_100`); previous best 160 (PatternBoost), 154 by classical search |\n\nThe two small instances are calibration: they tell you whether your search finds known optima at\nall. The two large ones are open; the 100 x 100 record in particular is believed to be beatable.\nThe repository lists problem 59 as a world record set by AlphaEvolve.\n\n## Metric\n\n    metric = mean over n in {16, 32, 64, 100} of  size(n) / record(n)\n\nThe eval re-derives everything from the point list you return: integer coordinates inside the grid,\nno repeated points, and the isosceles-free check on every apex. Any violation on any `n` is a failed\nrun (`wrong_answer`), and a solver that raises or overruns `1.25 * time_budget + 3` seconds fails\ntoo. `ZT_EVAL_SEED` only changes the `seed` handed to your solver; the instance set is fixed, so\nyour method has to be robust to its starting point.\n\n## Constraints\n\n- Standard library only. No numpy, no scipy, no numba. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The default is 25 s per instance, so a full eval takes\n  about 100 s; use the whole budget, nothing is gained by returning early.\n- Deterministic given `seed`: use `random.Random(seed)`.\n- Coordinates are `0..n-1` (the AlphaEvolve notebook convention; the papers use `1..n`).\n\n## Iterating quickly\n\n- `ZT_EVAL_INSTANCES=64` (comma-separated `n` values from the table) runs a subset.\n- `ZT_EVAL_PER_INSTANCE_SECONDS=5` shrinks the per-instance budget.\n\nExample: `ZT_EVAL_INSTANCES=16,32 ZT_EVAL_PER_INSTANCE_SECONDS=5 python eval.py`.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Keep an incremental structure: for each point the set of squared distances to the others. Adding a\n  point `q` is legal iff no distance from `q` repeats and no existing point already has that\n  distance. That makes add / remove / check `O(|S|)`, which is what every strong search relies on.\n- The records are close to four-fold symmetric (reflections in a horizontal and a vertical axis).\n  The axes need not pass through the centre: for even `n` they may be offset by half a cell in one\n  direction (e.g. `(31, 31.5)` instead of `(31.5, 31.5)` for `n = 64`). Search over symmetric\n  generator orbits first, then break the symmetry with a few asymmetric moves.\n- Almost nothing sits near the middle of the grid. Excluding a large central block shrinks the\n  candidate set considerably; how large a block is safe is not known.\n- Iterated local search (remove 8-30% of the points, greedily refill from the boundary inward,\n  keep if not worse, accept equal-size moves to drift across plateaus) is the loop that reached\n  110 and 112 for `n = 64`. Run it for the whole budget.\n- The best small-`n` constructions look very different from one another, so restarts from several\n  symmetric seeds beat one long run from a single one.\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 grid-no-isosceles. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED                   seed handed to solve()\n  ZT_EVAL_PER_INSTANCE_SECONDS   time budget per grid size n (default 25)\n  ZT_EVAL_INSTANCES              comma-separated grid sizes n (default \"16,32,64,100\")\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\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_INSTANCE_SECONDS\", \"25\"))\nINSTANCES = [int(x) for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"16,32,64,100\").split(\",\")]\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\n# Best-known size of an isosceles-free subset of the n x n grid (coordinates 0..n-1).\n#   16, 32: optimal, proved by SAT search (Charton, Ellenberg, Wagner, Williamson, \"PatternBoost\",\n#           arXiv:2411.00566, section 4.1, Figure 12; quoted as C(16)=28, C(32)=56 in arXiv:2511.02864\n#           section 6.39).\n#   64, 100: AlphaEvolve (Georgiev, Gomez-Serrano, Tao, Wagner, arXiv:2511.02864 section 6.39;\n#           repository of problems, problem 59), improving PatternBoost's 110 and 160. Not proved optimal.\n# Update when a hub-verified submission exceeds these.\nRECORDS = {16: 28, 32: 56, 64: 112, 100: 164}\nPROVEN = {16, 32}\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 solver.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 _coord(v, n: int) -> int:\n    if isinstance(v, bool) or not isinstance(v, (int, float)) or v != int(v):\n        fail(f\"solve({n}) returned a non-integer coordinate {v!r}\", \"wrong_answer\")\n    return int(v)\n\n\ndef validate(points, n: int) -> int:\n    \"\"\"Check the returned point set and return its size. Nothing the solver reports is trusted.\"\"\"\n    if not isinstance(points, (list, tuple, set, frozenset)):\n        fail(f\"solve({n}) must return a list of (x, y) integer pairs\", \"wrong_answer\")\n    pts = []\n    for p in points:\n        try:\n            x, y = p\n        except Exception:\n            fail(f\"solve({n}) returned a non-point {p!r}\", \"wrong_answer\")\n        x, y = _coord(x, n), _coord(y, n)\n        if not (0 <= x < n and 0 <= y < n):\n            fail(f\"solve({n}) placed a point outside the grid: ({x}, {y})\", \"wrong_answer\")\n        pts.append((x, y))\n    if len(set(pts)) != len(pts):\n        fail(f\"solve({n}) returned a repeated point\", \"wrong_answer\")\n    # Isosceles-free: for every apex a, the squared distances to all other points are distinct.\n    # Flat triangles are covered too (a midway between b and c gives |ab| = |ac|).\n    for i, (ax, ay) in enumerate(pts):\n        seen: dict[int, int] = {}\n        for j, (bx, by) in enumerate(pts):\n            if i == j:\n                continue\n            d = (ax - bx) * (ax - bx) + (ay - by) * (ay - by)\n            if d in seen:\n                fail(f\"solve({n}): isosceles triangle with apex {pts[i]} and base {pts[seen[d]]}, {(bx, by)} \"\n                     f\"(squared legs {d})\", \"wrong_answer\")\n            seen[d] = j\n    return len(pts)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"solver.py\")\n    sys.dont_write_bytecode = True  # a stale solver.pyc must never be what gets scored\n    sys.path.insert(0, str(here))\n    try:\n        import solver as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import solver.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"solve\"):\n        fail(\"solver.py must define solve(n, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"noiso|{SEED}\").getrandbits(32)\n    per_n, beaten = {}, []\n    for n in INSTANCES:\n        if n not in RECORDS:\n            fail(f\"no record for n={n}\", \"error\")\n        t0 = time.perf_counter()\n        try:\n            points = cand.solve(n, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"solve({n}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"solve({n}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        size = validate(points, n)\n        per_n[n] = {\"size\": size, \"record\": RECORDS[n], \"proven_optimal\": n in PROVEN,\n                    \"ratio\": round(size / RECORDS[n], 6), \"seconds\": round(elapsed, 2)}\n        if size > RECORDS[n]:\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":{"solver.py":"\"\"\"Baseline: greedy outside-in build plus a fixed number of ruin-and-recreate rounds.\n\nScores about 0.8 of the records and, with the default budget, finishes early. Beat it.\n\"\"\"\n\nimport random\nimport time\n\n\nclass IsoFree:\n    \"\"\"An isosceles-free point set with O(|S|) can_add / add / remove.\"\"\"\n\n    def __init__(self):\n        self.points = []\n        self.d2s = {}  # point -> set of squared distances to the other points\n\n    def can_add(self, q):\n        if q in self.d2s:\n            return False\n        seen = set()\n        for p in self.points:\n            d = (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2\n            if d in seen or d in self.d2s[p]:\n                return False\n            seen.add(d)\n        return True\n\n    def add(self, q):\n        s = set()\n        for p in self.points:\n            d = (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2\n            self.d2s[p].add(d)\n            s.add(d)\n        self.points.append(q)\n        self.d2s[q] = s\n\n    def remove(self, q):\n        self.points.remove(q)\n        del self.d2s[q]\n        for p in self.points:\n            self.d2s[p].discard((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2)\n\n\ndef solve(n: int, time_budget: float, seed: int) -> list[tuple[int, int]]:\n    rng = random.Random(seed)\n    deadline = time.perf_counter() + time_budget\n    c = (n - 1) / 2\n    # Records keep almost every point near the boundary, so only the outer band is a candidate.\n    band = n // 4\n    cells = [(x, y) for x in range(n) for y in range(n) if max(abs(x - c), abs(y - c)) >= band]\n\n    def outside_in():\n        keyed = [(-max(abs(x - c), abs(y - c)), rng.random(), (x, y)) for x, y in cells]\n        keyed.sort()\n        return [p for _, _, p in keyed]\n\n    s = IsoFree()\n    for p in outside_in():\n        if s.can_add(p):\n            s.add(p)\n    best = list(s.points)\n\n    for _ in range(150):  # a fixed round count keeps the result deterministic under seed\n        if time.perf_counter() > deadline:  # only bites when the budget is cut short\n            break\n        for p in rng.sample(s.points, max(1, len(s.points) // 6)):\n            s.remove(p)\n        for p in outside_in():\n            if s.can_add(p):\n                s.add(p)\n        if len(s.points) >= len(best):\n            best = list(s.points)\n        else:  # go back to the best set\n            for p in list(s.points):\n                s.remove(p)\n            for p in best:\n                s.add(p)\n    return best\n"}}