#!/usr/bin/env python3 """Exact check of binary codes that correct two deletions, for the lengths n = 16, 17 and 18. A candidate is a JSON object {"n": n, "words": ["0110...", ...]}: distinct strings of n binary digits. It corrects two deletions when no two of its words share a descendant, a string of length n - 2 obtained by deleting two positions of a word. Its value is the number of words. The check computes every descendant of every word, as EinsteinArena's verifier does: exact strings, no floating-point number. Python >= 3.9, standard library only. """ import json from fractions import Fraction from itertools import combinations from pathlib import Path SIZES = (16, 17, 18) INSTANCES = tuple(f"n{n}" for n in SIZES) # instance -> the public record: the largest code reported, who found it, when, and where it is listed RECORDS = json.loads(Path(__file__).with_name("records.json").read_text()) RECORD = {k: v["value"] for k, v in RECORDS.items()} # The sizes of the codes in constructions/ that the project starts from: the record for n = 16, greedy codes otherwise. START = {"n16": 220, "n17": 316, "n18": 525} class CandidateError(ValueError): pass def descendants(w: str) -> set[str]: return {w[:i] + w[i + 1:j] + w[j + 1:] for i, j in combinations(range(len(w)), 2)} def words(candidate: dict) -> tuple[str, list[str]]: """The candidate's instance ("n17") and its words; raises CandidateError when it is malformed or not a code that corrects two deletions.""" n, ws = candidate.get("n"), candidate.get("words") if type(n) is not int or n not in SIZES: raise CandidateError('"n" must be one of the integers 16, 17, 18') if not isinstance(ws, list) or not ws: raise CandidateError('"words" must be a nonempty list') for w in ws: if not isinstance(w, str) or len(w) != n or not set(w) <= {"0", "1"}: raise CandidateError(f"every word must be a string of {n} binary digits, not {str(w)[:40]!r}") if len(set(ws)) != len(ws): raise CandidateError("the words must be distinct") seen: dict[str, str] = {} for w in ws: for d in descendants(w): other = seen.setdefault(d, w) if other != w: raise CandidateError(f"{other} and {w} share the descendant {d}") return f"n{n}", ws def is_record(instance: str, size: int) -> bool: return size > RECORD[instance] def score(best: dict[str, int]) -> Fraction: """The mean over the three lengths of size / record, where a length counts as its starting code when the route has nothing larger.""" return sum(Fraction(max(best.get(k, 0), START[k]), RECORD[k]) for k in INSTANCES) / len(INSTANCES) def scan(roots): """(file, instance, size) for each candidate (*.json with "words") under these folders, in order. For a file that is unreadable or malformed, instance is None and size 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 "words" not in candidate: continue try: instance, ws = words(candidate) except CandidateError as exc: yield name, None, f"not a code correcting two deletions: {exc}" continue yield name, instance, len(ws) def best_of(found) -> dict[str, tuple[int, str]]: """Each instance's largest code among scanned candidates, with the file that holds it.""" best = {} for name, instance, size in found: if instance and (instance not in best or size > best[instance][0]): best[instance] = (size, name) return best def card(instance: str) -> str: r = RECORDS[instance] return f"{r['value']} ({r['by']}, {r['date']})"