#!/usr/bin/env python3 """Exact check of snakes in the box: induced paths in the hypercube Q_d, for d = 13, 14, 15 and 16. A candidate is a JSON object {"d": d, "transitions": ...}: the path from the vertex 0, one step per edge, each step the 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 record pages write them (whitespace is ignored), or a list of integers, as EinsteinArena's "actions". The path is a 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 its number of edges. Integer arithmetic only. Python >= 3.9, standard library only. """ import json from fractions import Fraction from pathlib import Path DIMENSIONS = (13, 14, 15, 16) INSTANCES = tuple(f"d{d}" for d in DIMENSIONS) # instance -> the public record: the longest snake reported, who found it, when, and where it is RECORDS = json.loads(Path(__file__).with_name("records.json").read_text()) RECORD = {k: v["value"] for k, v in RECORDS.items()} class CandidateError(ValueError): pass def steps(candidate: dict) -> tuple[str, list[int]]: """The candidate's instance ("d15") and its steps; raises CandidateError when it is malformed or not a snake.""" d, t = candidate.get("d"), candidate.get("transitions") if type(d) is not int or d not in DIMENSIONS: raise CandidateError('"d" must be one of the integers 13, 14, 15, 16') if isinstance(t, str): # base-36 digits; -1 for anything else, refused below t = ["0123456789abcdefghijklmnopqrstuvwxyz".find(c) for c in t.lower() if not c.isspace()] if not isinstance(t, list) or not t or len(t) >= 2 ** d: raise CandidateError(f'"transitions" must be a nonempty string or list of fewer than {2 ** d} steps') if not all(type(s) is int and 0 <= s < d for s in t): raise CandidateError(f"every step must be a coordinate from 0 to {d - 1}") path = [0] for s in t: path.append(path[-1] ^ (1 << s)) where: dict[int, int] = {} for i, v in enumerate(path): if v in where: raise CandidateError(f"the path returns to vertex {v} at step {i} (first at step {where[v]})") where[v] = i for i, v in enumerate(path): for c in range(d): j = where.get(v ^ (1 << c)) if j is not None and abs(i - j) != 1: raise CandidateError(f"the vertices at steps {min(i, j)} and {max(i, j)} are adjacent: a chord") return f"d{d}", t def is_record(instance: str, length: int) -> bool: return length > RECORD[instance] def score(best: dict[str, int]) -> Fraction: """The mean over the four dimensions of length / record, where a dimension counts as its record when the route has nothing longer (main starts from the records, so it scores exactly 1).""" return sum(Fraction(max(best.get(k, 0), RECORD[k]), RECORD[k]) for k in INSTANCES) / len(INSTANCES) def scan(roots): """(file, instance, length) for each candidate (*.json with "transitions") under these folders, in order. For a file that is unreadable or malformed, instance is None and length says why; other JSON files are not candidates.""" for root in roots: for path in sorted(root.rglob("*.json")) if root.exists() else []: name = str(path.relative_to(root.parent)) try: candidate = json.loads(path.read_text()) except Exception as exc: yield name, None, f"unreadable ({exc})" continue if not isinstance(candidate, dict) or "transitions" not in candidate: continue try: instance, t = steps(candidate) except CandidateError as exc: yield name, None, f"not a snake: {exc}" continue yield name, instance, len(t) def best_of(found) -> dict[str, tuple[int, str]]: """Each instance's longest snake among scanned candidates, with the file that holds it.""" best = {} for name, instance, length in found: if instance and (instance not in best or length > best[instance][0]): best[instance] = (length, name) return best def card(instance: str) -> str: r = RECORDS[instance] return f"{r['value']} ({r['by']}, {r['date']})"