Snakes in the box in dimensions 13 to 16
Find longer snakes, induced paths in the hypercube, in dimensions 13 to 16: beat 2946, 5850, 11,673 and 23,318 edges.
| 1 | #!/usr/bin/env python3 |
| 2 | """Tests of the judge, the format checker and the starting snakes. Run: python3 -I checks/test_judge.py""" |
| 3 | import json |
| 4 | import os |
| 5 | import shutil |
| 6 | import subprocess |
| 7 | import sys |
| 8 | import tempfile |
| 9 | from fractions import Fraction |
| 10 | from pathlib import Path |
| 11 | |
| 12 | PKG = Path(__file__).resolve().parent.parent |
| 13 | JUDGE, REPO = PKG / "checks" / "judge", PKG |
| 14 | sys.dont_write_bytecode = True |
| 15 | sys.path.insert(0, str(JUDGE)) |
| 16 | from snake import INSTANCES, RECORD # noqa: E402 |
| 17 | |
| 18 | |
| 19 | def run(script, *args, cwd, route_dir="routes/x"): |
| 20 | # as the check runs it (python3 checks/judge/check.py), without the environment's PYTHON* variables or user site |
| 21 | env = {"PATH": os.environ.get("PATH", "/usr/bin:/bin"), "SS_ROUTE_DIR": route_dir} |
| 22 | p = subprocess.run([sys.executable, "-E", "-s", "-B", str(script), *map(str, args)], cwd=cwd, capture_output=True, text=True, env=env, timeout=120) |
| 23 | return p.returncode, p.stdout, p.stderr |
| 24 | |
| 25 | |
| 26 | def length(c): |
| 27 | """Independent of the judge: the path's vertices as bit strings, then every pair at Hamming distance 1 must be |
| 28 | consecutive on it. Returns the number of edges, or None when the path is not a snake.""" |
| 29 | d = c["d"] |
| 30 | path = [0] |
| 31 | for ch in c["transitions"]: |
| 32 | path.append(path[-1] ^ (1 << int(ch, 36))) |
| 33 | if len(set(path)) != len(path): |
| 34 | return None |
| 35 | index = {v: i for i, v in enumerate(path)} |
| 36 | for v, i in index.items(): |
| 37 | for b in range(d): |
| 38 | j = index.get(v ^ (1 << b)) |
| 39 | if j is not None and abs(i - j) != 1: |
| 40 | return None |
| 41 | return len(path) - 1 |
| 42 | |
| 43 | |
| 44 | def start(k): |
| 45 | return json.loads((REPO / "constructions" / f"{k}.json").read_text()) |
| 46 | |
| 47 | |
| 48 | def write(folder, files): |
| 49 | for name, content in files.items(): |
| 50 | path = folder / name |
| 51 | path.parent.mkdir(parents=True, exist_ok=True) |
| 52 | if isinstance(content, bytes): |
| 53 | path.write_bytes(content) |
| 54 | else: |
| 55 | path.write_text(content if isinstance(content, str) else json.dumps(content)) |
| 56 | |
| 57 | |
| 58 | def check(files, judge=JUDGE, route_dir="routes/x", main=None): |
| 59 | """Runs verify on a route folder holding these files (and main's constructions/ when given); returns (exit code, |
| 60 | stdout, stderr, metrics or None).""" |
| 61 | with tempfile.TemporaryDirectory() as tmp: |
| 62 | folder = Path(tmp, *route_dir.split("/")) |
| 63 | folder.mkdir(parents=True) |
| 64 | write(folder, files) |
| 65 | if main: |
| 66 | write(Path(tmp, "constructions"), main) |
| 67 | code, out, err = run(judge / "check.py", folder, cwd=tmp, route_dir=route_dir) |
| 68 | metrics = Path(tmp, "metrics.json") |
| 69 | return code, out, err, json.loads(metrics.read_text()) if metrics.exists() else None |
| 70 | |
| 71 | |
| 72 | def judge_with(records, tmp): |
| 73 | """A copy of the judge whose records are changed: {instance: length}.""" |
| 74 | out = Path(tmp, "judge") |
| 75 | shutil.copytree(JUDGE, out) |
| 76 | table = json.loads((JUDGE / "records.json").read_text()) |
| 77 | for k, v in records.items(): |
| 78 | table[k]["value"] = v |
| 79 | (out / "records.json").write_text(json.dumps(table)) |
| 80 | return out |
| 81 | |
| 82 | |
| 83 | def test_starts_are_the_records(): |
| 84 | assert RECORD == {"d13": 2946, "d14": 5850, "d15": 11673, "d16": 23318} |
| 85 | for k in INSTANCES: |
| 86 | c = start(k) |
| 87 | assert f"d{c['d']}" == k and length(c) == RECORD[k], k |
| 88 | code, out, err, m = check({}, route_dir="routes", main={f"{k}.json": start(k) for k in INSTANCES}) |
| 89 | assert code == 0 and not err, out + err |
| 90 | assert m == {"score": 1.0, "score_exact": "1", "subtasks": RECORD, "new_records": []}, m |
| 91 | assert "d16: 23318 edges (constructions/d16.json), +0 against the record\n" in out, out |
| 92 | assert out.strip().endswith("score 1.000000000; no new record"), out |
| 93 | |
| 94 | |
| 95 | def test_score_and_new_records(): |
| 96 | short = {**start("d15"), "transitions": start("d15")["transitions"][:1000]} # a piece of a snake is a snake |
| 97 | with tempfile.TemporaryDirectory() as tmp: |
| 98 | code, out, err, m = check({"a.json": start("d13"), "short.json": short}, judge=judge_with({"d13": 2940}, tmp)) |
| 99 | assert code == 0 and not err, out + err |
| 100 | s = (Fraction(2946, 2940) + 3) / 4 # the short d15 counts as the record |
| 101 | assert m["score_exact"] == str(s) and m["subtasks"] == {"d13": 2946, "d15": 1000} and m["new_records"] == ["d13"], m |
| 102 | assert "d13: 2946 edges (x/a.json), +6 against the record; a new record\n" in out and "d15: 1000 edges (x/short.json), -10673" in out, out |
| 103 | |
| 104 | |
| 105 | def test_paths_that_are_not_snakes_fail(): |
| 106 | for t, message in (("00", "returns to vertex 0 at step 2"), ("010", "steps 0 and 3 are adjacent"), ([0, 1, 0], "steps 0 and 3 are adjacent")): |
| 107 | code, out, err, m = check({"bad.json": {"d": 13, "transitions": t}}) |
| 108 | assert code == 1 and "not a snake" in out and message in out and not err and m is None, (t, out) |
| 109 | |
| 110 | |
| 111 | def test_both_forms_and_whitespace(): |
| 112 | t = start("d13")["transitions"] |
| 113 | spaced = " ".join(t[i:i + 10] for i in range(0, len(t), 10)).upper() |
| 114 | as_list = [int(ch, 36) for ch in t] |
| 115 | code, out, err, m = check({"a.json": {"d": 13, "transitions": spaced}, "b.json": {"d": 13, "transitions": as_list}}) |
| 116 | assert code == 0 and out.count("d13: 2946 edges") == 2 and m["subtasks"] == {"d13": 2946}, out |
| 117 | |
| 118 | |
| 119 | def test_invalid_candidates_fail_cleanly(): |
| 120 | good = start("d14") |
| 121 | cases = { |
| 122 | "dimension": ({**good, "d": 12}, '"d" must be one of'), |
| 123 | "bool": ({**good, "d": True}, '"d" must be one of'), |
| 124 | "step": ({"d": 13, "transitions": "0d"}, "coordinate from 0 to 12"), |
| 125 | "sign": ({"d": 13, "transitions": "0-1"}, "coordinate from 0 to 12"), |
| 126 | "float": ({"d": 13, "transitions": [0, 1.0]}, "coordinate from 0 to 12"), |
| 127 | "true": ({"d": 13, "transitions": [0, True]}, "coordinate from 0 to 12"), |
| 128 | "empty": ({"d": 13, "transitions": " "}, "nonempty string or list"), |
| 129 | "long": ({"d": 13, "transitions": "0" * 8192}, "fewer than 8192 steps"), |
| 130 | "object": ({"d": 13, "transitions": {"0": 1}}, "nonempty string or list"), |
| 131 | } |
| 132 | for name, (candidate, message) in cases.items(): |
| 133 | code, out, err, m = check({"ok.json": good, f"{name}.json": candidate}) |
| 134 | assert code == 1 and message in out and not err, (name, out, err) |
| 135 | assert m["subtasks"] == {"d14": 5850}, (name, m) |
| 136 | |
| 137 | |
| 138 | def test_malformed_files_fail_cleanly(): |
| 139 | for content in ("{not json", "", b"\xff\xfe{"): |
| 140 | code, out, err, m = check({"bad.json": content}) |
| 141 | assert code == 1 and "unreadable" in out and not err and m is None, (out, err) |
| 142 | assert out.strip().splitlines()[-1] == "no valid candidates: 1 failed", out |
| 143 | |
| 144 | |
| 145 | def test_no_candidates(): |
| 146 | for files in ({}, {"notes.json": [1, 2]}, {"README.md": "# x"}): |
| 147 | code, out, err, m = check(files) |
| 148 | assert code == 0 and out.strip() == "no candidates to check" and m is None, out |
| 149 | with tempfile.TemporaryDirectory() as tmp: |
| 150 | code, out, err = run(JUDGE / "check.py", Path(tmp, "missing"), cwd=tmp) |
| 151 | assert code == 0 and out.strip() == "no candidates to check", out |
| 152 | |
| 153 | |
| 154 | def test_improves(): |
| 155 | with tempfile.TemporaryDirectory() as tmp: |
| 156 | main = Path(tmp, "main") |
| 157 | shutil.copytree(REPO / "constructions", main / "constructions") |
| 158 | route = Path(tmp, "route") |
| 159 | write(route, {"a.json": start("d13")}) |
| 160 | code, out, _ = run(JUDGE / "improves.py", route, main, cwd=main) |
| 161 | assert code == 1 and "d13: 2946 edges (route/a.json) against the default branch's 2946, +0; the record is 2946 (William Toner, 2026-10-11)" in out, out |
| 162 | assert out.strip().endswith("no improvement on the default branch"), out |
| 163 | write(main / "constructions", {"d13.json": {**start("d13"), "transitions": start("d13")["transitions"][:2900]}}) |
| 164 | code, out, _ = run(JUDGE / "improves.py", route, main, cwd=main) |
| 165 | assert code == 0 and "+46: improves" in out and out.strip().endswith("improves on the default branch: d13; no new record"), out |
| 166 | code, out, _ = run(judge_with({"d13": 2940}, tmp) / "improves.py", route, main, cwd=main) |
| 167 | assert code == 0 and "a new record, above 2940" in out and out.strip().endswith("new records: d13"), out |
| 168 | code, out, _ = run(JUDGE / "improves.py", Path(tmp, "empty"), main, cwd=main) |
| 169 | assert code == 1 and out.startswith("no snake"), out |
| 170 | code, out, _ = run(JUDGE / "improves.py", main / "routes", main, cwd=main, route_dir="routes") |
| 171 | assert code == 0 and out.strip() == "the default branch holds d13: 2900, d14: 5850, d15: 11673, d16: 23318; no new record", out |
| 172 | |
| 173 | |
| 174 | def test_check_format(): |
| 175 | tool = REPO / "tools" / "check_format.py" |
| 176 | code, out, err = run(tool, REPO / "constructions", cwd=REPO) |
| 177 | assert code == 0 and out.strip().endswith("4 candidates, 0 files with format errors"), out + err |
| 178 | with tempfile.TemporaryDirectory() as tmp: |
| 179 | write(Path(tmp), {"bad.json": {"d": 13, "transitions": "0d1x"}, "dim.json": {"d": 17, "transitions": "0"}, "broken.json": "{", "other.json": "[]"}) |
| 180 | code, out, err = run(tool, tmp, cwd=tmp) |
| 181 | assert code == 1 and "2 steps are not coordinates from 0 to 12" in out and '"d" must be one of' in out, out |
| 182 | assert "not valid JSON" in out and "ignored" in out and out.strip().endswith("2 candidates, 3 files with format errors"), out |
| 183 | |
| 184 | |
| 185 | |
| 186 | if __name__ == "__main__": |
| 187 | failed = 0 |
| 188 | for name, test in list(globals().items()): |
| 189 | if name.startswith("test_"): |
| 190 | try: |
| 191 | test() |
| 192 | print(f"ok {name}") |
| 193 | except Exception as exc: |
| 194 | failed += 1 |
| 195 | print(f"FAIL {name}: {exc!r}") |
| 196 | sys.exit(1 if failed else 0) |
