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 | """Checks that the candidates in a folder follow the submission format in README.md: JSON shape, d, and steps that are |
| 3 | coordinates from 0 to d - 1. It does not follow the path, so it does not check that it is a snake. |
| 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 | d, t = candidate.get("d"), candidate.get("transitions") |
| 14 | if type(d) is not int or d not in (13, 14, 15, 16): |
| 15 | return ['"d" must be one of the integers 13, 14, 15, 16'] |
| 16 | if isinstance(t, str): |
| 17 | t = ["0123456789abcdefghijklmnopqrstuvwxyz".find(c) for c in t.lower() if not c.isspace()] |
| 18 | if not isinstance(t, list) or not t or len(t) >= 2 ** d: |
| 19 | return [f'"transitions" must be a nonempty string or list of fewer than {2 ** d} steps'] |
| 20 | bad = [s for s in t if type(s) is not int or not 0 <= s < d] |
| 21 | return [f"{len(bad)} steps are not coordinates from 0 to {d - 1}"] if bad else [] |
| 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 "transitions" not in candidate: |
| 43 | print(f'{path}: not a candidate (no "transitions" key); ignored') |
| 44 | continue |
| 45 | found += 1 |
| 46 | problems = errors(candidate) |
| 47 | print(f"{path}: {'; '.join(problems)}" if problems else f"{path}: ok (d{candidate['d']})") |
| 48 | bad += bool(problems) |
| 49 | print(f"{found} candidates, {bad} files with format errors") |
| 50 | sys.exit(1 if bad else 0) |
