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 | """Checks that the candidates in a folder follow the submission format in README.md: JSON shape, n, and words that are |
| 3 | distinct strings of n binary digits. It does not check that no two words share a descendant. |
| 4 | |
| 5 | usage: python3 tools/check_format.py routes/<branch> (or one .json file) |
| 6 | """ |
| 7 | import json |
| 8 | import pathlib |
| 9 | import sys |
| 10 | |
| 11 | |
| 12 | def errors(candidate): |
| 13 | n, words = candidate.get("n"), candidate.get("words") |
| 14 | if type(n) is not int or n not in (16, 17, 18): |
| 15 | return ['"n" must be one of the integers 16, 17, 18'] |
| 16 | if not isinstance(words, list) or not words: |
| 17 | return ['"words" must be a nonempty list'] |
| 18 | bad = [w for w in words if not isinstance(w, str) or len(w) != n or not set(w) <= {"0", "1"}] |
| 19 | if bad: |
| 20 | return [f"{len(bad)} words are not strings of {n} binary digits, such as {str(bad[0])[:40]!r}"] |
| 21 | return [] if len(set(words)) == len(words) else [f"{len(words) - len(set(words))} words are repeated"] |
| 22 | |
| 23 | |
| 24 | if len(sys.argv) != 2: |
| 25 | sys.exit(__doc__) |
| 26 | target = pathlib.Path(sys.argv[1]) |
| 27 | if target.is_file() and target.suffix != ".json": |
| 28 | sys.exit(f"{target}: candidates are .json files") |
| 29 | files = [target] if target.is_file() else sorted(target.rglob("*.json")) |
| 30 | found = bad = 0 |
| 31 | for path in files: |
| 32 | if path.stat().st_size > 1_000_000: |
| 33 | print(f"{path}: over 1 MB") |
| 34 | bad += 1 |
| 35 | continue |
| 36 | try: |
| 37 | candidate = json.loads(path.read_text()) |
| 38 | except Exception as exc: |
| 39 | print(f"{path}: not valid JSON ({exc})") |
| 40 | bad += 1 |
| 41 | continue |
| 42 | if not isinstance(candidate, dict) or "words" not in candidate: |
| 43 | print(f'{path}: not a candidate (no "words" key); ignored') |
| 44 | continue |
| 45 | found += 1 |
| 46 | problems = errors(candidate) |
| 47 | print(f"{path}: {'; '.join(problems)}" if problems else f"{path}: ok (n{candidate['n']}, {len(candidate['words'])} words)") |
| 48 | bad += bool(problems) |
| 49 | print(f"{found} candidates, {bad} files with format errors") |
| 50 | sys.exit(1 if bad else 0) |
