Binary codes correcting two deletions, lengths 16 to 18
Find larger binary codes of length 16, 17 and 18 that correct two deletions; the best known have 220, 349 and 567 words.
| 1 | #!/usr/bin/env python3 |
| 2 | """Exact check of binary codes that correct two deletions, for the lengths n = 16, 17 and 18. |
| 3 | |
| 4 | A candidate is a JSON object {"n": n, "words": ["0110...", ...]}: distinct strings of n binary digits. It corrects two |
| 5 | deletions when no two of its words share a descendant, a string of length n - 2 obtained by deleting two positions of a |
| 6 | word. Its value is the number of words. The check computes every descendant of every word, as EinsteinArena's verifier |
| 7 | does: exact strings, no floating-point number. Python >= 3.9, standard library only. |
| 8 | """ |
| 9 | import json |
| 10 | from fractions import Fraction |
| 11 | from itertools import combinations |
| 12 | from pathlib import Path |
| 13 | |
| 14 | SIZES = (16, 17, 18) |
| 15 | INSTANCES = tuple(f"n{n}" for n in SIZES) |
| 16 | # instance -> the public record: the largest code reported, who found it, when, and where it is listed |
| 17 | RECORDS = json.loads(Path(__file__).with_name("records.json").read_text()) |
| 18 | RECORD = {k: v["value"] for k, v in RECORDS.items()} |
| 19 | # The sizes of the codes in constructions/ that the project starts from: the record for n = 16, greedy codes otherwise. |
| 20 | START = {"n16": 220, "n17": 316, "n18": 525} |
| 21 | |
| 22 | |
| 23 | class CandidateError(ValueError): |
| 24 | pass |
| 25 | |
| 26 | |
| 27 | def descendants(w: str) -> set[str]: |
| 28 | return {w[:i] + w[i + 1:j] + w[j + 1:] for i, j in combinations(range(len(w)), 2)} |
| 29 | |
| 30 | |
| 31 | def words(candidate: dict) -> tuple[str, list[str]]: |
| 32 | """The candidate's instance ("n17") and its words; raises CandidateError when it is malformed or not a code that |
| 33 | corrects two deletions.""" |
| 34 | n, ws = candidate.get("n"), candidate.get("words") |
| 35 | if type(n) is not int or n not in SIZES: |
| 36 | raise CandidateError('"n" must be one of the integers 16, 17, 18') |
| 37 | if not isinstance(ws, list) or not ws: |
| 38 | raise CandidateError('"words" must be a nonempty list') |
| 39 | for w in ws: |
| 40 | if not isinstance(w, str) or len(w) != n or not set(w) <= {"0", "1"}: |
| 41 | raise CandidateError(f"every word must be a string of {n} binary digits, not {str(w)[:40]!r}") |
| 42 | if len(set(ws)) != len(ws): |
| 43 | raise CandidateError("the words must be distinct") |
| 44 | seen: dict[str, str] = {} |
| 45 | for w in ws: |
| 46 | for d in descendants(w): |
| 47 | other = seen.setdefault(d, w) |
| 48 | if other != w: |
| 49 | raise CandidateError(f"{other} and {w} share the descendant {d}") |
| 50 | return f"n{n}", ws |
| 51 | |
| 52 | |
| 53 | def is_record(instance: str, size: int) -> bool: |
| 54 | return size > RECORD[instance] |
| 55 | |
| 56 | |
| 57 | def score(best: dict[str, int]) -> Fraction: |
| 58 | """The mean over the three lengths of size / record, where a length counts as its starting code when the route has |
| 59 | nothing larger.""" |
| 60 | return sum(Fraction(max(best.get(k, 0), START[k]), RECORD[k]) for k in INSTANCES) / len(INSTANCES) |
| 61 | |
| 62 | |
| 63 | def scan(roots): |
| 64 | """(file, instance, size) for each candidate (*.json with "words") under these folders, in order. For a file that |
| 65 | is unreadable or malformed, instance is None and size says why; other JSON files are not candidates.""" |
| 66 | for root in roots: |
| 67 | for path in sorted(root.rglob("*.json")) if root.exists() else []: |
| 68 | name = str(path.relative_to(root.parent)) |
| 69 | try: |
| 70 | candidate = json.loads(path.read_text()) |
| 71 | except Exception as exc: |
| 72 | yield name, None, f"unreadable ({exc})" |
| 73 | continue |
| 74 | if not isinstance(candidate, dict) or "words" not in candidate: |
| 75 | continue |
| 76 | try: |
| 77 | instance, ws = words(candidate) |
| 78 | except CandidateError as exc: |
| 79 | yield name, None, f"not a code correcting two deletions: {exc}" |
| 80 | continue |
| 81 | yield name, instance, len(ws) |
| 82 | |
| 83 | |
| 84 | def best_of(found) -> dict[str, tuple[int, str]]: |
| 85 | """Each instance's largest code among scanned candidates, with the file that holds it.""" |
| 86 | best = {} |
| 87 | for name, instance, size in found: |
| 88 | if instance and (instance not in best or size > best[instance][0]): |
| 89 | best[instance] = (size, name) |
| 90 | return best |
| 91 | |
| 92 | |
| 93 | def card(instance: str) -> str: |
| 94 | r = RECORDS[instance] |
| 95 | return f"{r['value']} ({r['by']}, {r['date']})" |
