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 | """Exact check of snakes in the box: induced paths in the hypercube Q_d, for d = 13, 14, 15 and 16. |
| 3 | |
| 4 | A candidate is a JSON object {"d": d, "transitions": ...}: the path from the vertex 0, one step per edge, each step the |
| 5 | coordinate it flips, in 0..d-1. The steps are a string of base-36 digits ("0"-"9", then "a" = 10 to "f" = 15), as the |
| 6 | record pages write them (whitespace is ignored), or a list of integers, as EinsteinArena's "actions". The path is a |
| 7 | snake when its vertices are distinct and no two of them that are not consecutive on it are adjacent in Q_d. Its value is |
| 8 | its number of edges. Integer arithmetic only. Python >= 3.9, standard library only. |
| 9 | """ |
| 10 | import json |
| 11 | from fractions import Fraction |
| 12 | from pathlib import Path |
| 13 | |
| 14 | DIMENSIONS = (13, 14, 15, 16) |
| 15 | INSTANCES = tuple(f"d{d}" for d in DIMENSIONS) |
| 16 | # instance -> the public record: the longest snake reported, who found it, when, and where it is |
| 17 | RECORDS = json.loads(Path(__file__).with_name("records.json").read_text()) |
| 18 | RECORD = {k: v["value"] for k, v in RECORDS.items()} |
| 19 | |
| 20 | |
| 21 | class CandidateError(ValueError): |
| 22 | pass |
| 23 | |
| 24 | |
| 25 | def steps(candidate: dict) -> tuple[str, list[int]]: |
| 26 | """The candidate's instance ("d15") and its steps; raises CandidateError when it is malformed or not a snake.""" |
| 27 | d, t = candidate.get("d"), candidate.get("transitions") |
| 28 | if type(d) is not int or d not in DIMENSIONS: |
| 29 | raise CandidateError('"d" must be one of the integers 13, 14, 15, 16') |
| 30 | if isinstance(t, str): # base-36 digits; -1 for anything else, refused below |
| 31 | t = ["0123456789abcdefghijklmnopqrstuvwxyz".find(c) for c in t.lower() if not c.isspace()] |
| 32 | if not isinstance(t, list) or not t or len(t) >= 2 ** d: |
| 33 | raise CandidateError(f'"transitions" must be a nonempty string or list of fewer than {2 ** d} steps') |
| 34 | if not all(type(s) is int and 0 <= s < d for s in t): |
| 35 | raise CandidateError(f"every step must be a coordinate from 0 to {d - 1}") |
| 36 | path = [0] |
| 37 | for s in t: |
| 38 | path.append(path[-1] ^ (1 << s)) |
| 39 | where: dict[int, int] = {} |
| 40 | for i, v in enumerate(path): |
| 41 | if v in where: |
| 42 | raise CandidateError(f"the path returns to vertex {v} at step {i} (first at step {where[v]})") |
| 43 | where[v] = i |
| 44 | for i, v in enumerate(path): |
| 45 | for c in range(d): |
| 46 | j = where.get(v ^ (1 << c)) |
| 47 | if j is not None and abs(i - j) != 1: |
| 48 | raise CandidateError(f"the vertices at steps {min(i, j)} and {max(i, j)} are adjacent: a chord") |
| 49 | return f"d{d}", t |
| 50 | |
| 51 | |
| 52 | def is_record(instance: str, length: int) -> bool: |
| 53 | return length > RECORD[instance] |
| 54 | |
| 55 | |
| 56 | def score(best: dict[str, int]) -> Fraction: |
| 57 | """The mean over the four dimensions of length / record, where a dimension counts as its record when the route has |
| 58 | nothing longer (main starts from the records, so it scores exactly 1).""" |
| 59 | return sum(Fraction(max(best.get(k, 0), RECORD[k]), RECORD[k]) for k in INSTANCES) / len(INSTANCES) |
| 60 | |
| 61 | |
| 62 | def scan(roots): |
| 63 | """(file, instance, length) for each candidate (*.json with "transitions") under these folders, in order. For a |
| 64 | file that is unreadable or malformed, instance is None and length says why; other JSON files are not candidates.""" |
| 65 | for root in roots: |
| 66 | for path in sorted(root.rglob("*.json")) if root.exists() else []: |
| 67 | name = str(path.relative_to(root.parent)) |
| 68 | try: |
| 69 | candidate = json.loads(path.read_text()) |
| 70 | except Exception as exc: |
| 71 | yield name, None, f"unreadable ({exc})" |
| 72 | continue |
| 73 | if not isinstance(candidate, dict) or "transitions" not in candidate: |
| 74 | continue |
| 75 | try: |
| 76 | instance, t = steps(candidate) |
| 77 | except CandidateError as exc: |
| 78 | yield name, None, f"not a snake: {exc}" |
| 79 | continue |
| 80 | yield name, instance, len(t) |
| 81 | |
| 82 | |
| 83 | def best_of(found) -> dict[str, tuple[int, str]]: |
| 84 | """Each instance's longest snake among scanned candidates, with the file that holds it.""" |
| 85 | best = {} |
| 86 | for name, instance, length in found: |
| 87 | if instance and (instance not in best or length > best[instance][0]): |
| 88 | best[instance] = (length, name) |
| 89 | return best |
| 90 | |
| 91 | |
| 92 | def card(instance: str) -> str: |
| 93 | r = RECORDS[instance] |
| 94 | return f"{r['value']} ({r['by']}, {r['date']})" |
