Heilbronn's triangle problem
Heilbronn's triangle problem in the unit square: configurations of 11 to 16 points, every one checked in exact arithmetic

| 1 | #!/usr/bin/env python3 |
| 2 | """The check: the smallest triangle of each configuration, in exact arithmetic. |
| 3 | |
| 4 | Usage: verify.py FOLDER_OR_FILE... |
| 5 | |
| 6 | A folder means the n<N>.txt files directly in it. Only the instances that scienceslack.json (next to this file) |
| 7 | declares are judged; every other .txt file is named as ignored. A configuration is N lines `x y`, as decimals or |
| 8 | fractions (0.25, 1/3); blank lines and lines starting with # are skipped. |
| 9 | |
| 10 | The last line is what the site shows on the commit: |
| 11 | exit 0 `n = 11: 0.0370370370; n = 12: ...`, each value cut (never rounded up) to ten decimals, |
| 12 | or that there is nothing to check yet; |
| 13 | exit 1 the first thing wrong, with the file and the line to fix. |
| 14 | """ |
| 15 | import itertools |
| 16 | import json |
| 17 | import os |
| 18 | import re |
| 19 | import sys |
| 20 | from fractions import Fraction |
| 21 | from pathlib import Path |
| 22 | |
| 23 | DIGITS = 10 |
| 24 | MAX_BYTES = 64_000 # the longest published coordinates (200 digits each, n = 16) take a tenth of this |
| 25 | NUMBER = re.compile(r"[+-]?(\d+\.?\d*|\.\d+)([eE][+-]?\d{1,3})?|\d+/\d+", re.ASCII) # no exponent Fraction would choke on |
| 26 | |
| 27 | |
| 28 | class Wrong(Exception): |
| 29 | """A configuration the check refuses; its text is what the author reads.""" |
| 30 | |
| 31 | |
| 32 | def shown(text, limit=60): |
| 33 | """A name or a line as it is safe to print: one line, printable, not long.""" |
| 34 | clean = "".join(c if c.isprintable() else "?" for c in text) |
| 35 | return clean if len(clean) <= limit else clean[:limit] + "..." |
| 36 | |
| 37 | |
| 38 | def cut(value): |
| 39 | """A positive fraction as a decimal cut to DIGITS places: never more than the value.""" |
| 40 | whole, rest = divmod(int(value * 10**DIGITS), 10**DIGITS) |
| 41 | return f"{whole}.{rest:0{DIGITS}d}" |
| 42 | |
| 43 | |
| 44 | def instances(): |
| 45 | """The declared instances, as {N: "n = N"}.""" |
| 46 | spec = json.loads((Path(__file__).resolve().parent / "scienceslack.json").read_text(encoding="utf-8")) |
| 47 | found = {} |
| 48 | for name in spec.get("instances", []): |
| 49 | m = re.fullmatch(r"n\s*=\s*(\d+)", name.strip()) |
| 50 | if m: |
| 51 | found[int(m.group(1))] = name.strip() |
| 52 | return found |
| 53 | |
| 54 | |
| 55 | def points(path, n): |
| 56 | """The n points of a file, each with its line number; Wrong if it does not hold n points of the unit square.""" |
| 57 | name = path.name |
| 58 | try: |
| 59 | if path.is_symlink() or not path.is_file(): |
| 60 | raise Wrong(f"{name} is not a regular file: commit the file itself") |
| 61 | if path.stat().st_size > MAX_BYTES: |
| 62 | raise Wrong(f"{name} is larger than {MAX_BYTES // 1000} kB: a configuration is {n} lines of two numbers") |
| 63 | text = path.read_bytes().decode("utf-8") |
| 64 | except (OSError, UnicodeDecodeError): |
| 65 | raise Wrong(f"{name} cannot be read as UTF-8 text") from None |
| 66 | pts = [] |
| 67 | for at, line in enumerate(text.splitlines(), 1): |
| 68 | parts = line.split() |
| 69 | if not parts or parts[0].startswith("#"): |
| 70 | continue |
| 71 | try: |
| 72 | if len(parts) != 2 or not all(NUMBER.fullmatch(p) for p in parts): |
| 73 | raise ValueError |
| 74 | pts.append((at, Fraction(parts[0]), Fraction(parts[1]))) |
| 75 | except (ValueError, ZeroDivisionError): |
| 76 | raise Wrong(f"{name} line {at}: expected two numbers such as `0.25 0.5` or `1/3 2/9`, found `{shown(line.strip())}`") from None |
| 77 | if len(pts) != n: |
| 78 | raise Wrong(f"{name} holds {len(pts)} point{'' if len(pts) == 1 else 's'}: a file named {name} must hold exactly {n}, one `x y` a line") |
| 79 | for at, x, y in pts: |
| 80 | if not (0 <= x <= 1 and 0 <= y <= 1): |
| 81 | raise Wrong(f"{name} line {at}: the point lies outside the unit square: both coordinates must be between 0 and 1") |
| 82 | first = {} |
| 83 | for at, x, y in pts: |
| 84 | if (x, y) in first: |
| 85 | raise Wrong(f"{name} lines {first[(x, y)]} and {at} are the same point: all {n} points must differ") |
| 86 | first[(x, y)] = at |
| 87 | return pts |
| 88 | |
| 89 | |
| 90 | def smallest(pts): |
| 91 | """The smallest triangle: (area, the three line numbers).""" |
| 92 | def doubled(t): |
| 93 | (_, ax, ay), (_, bx, by), (_, cx, cy) = t |
| 94 | return abs((bx - ax) * (cy - ay) - (cx - ax) * (by - ay)) |
| 95 | t = min(itertools.combinations(pts, 3), key=doubled) |
| 96 | return doubled(t) / 2, [p[0] for p in t] |
| 97 | |
| 98 | |
| 99 | def main(args): |
| 100 | if not args: |
| 101 | print(__doc__.strip()) |
| 102 | return 2 |
| 103 | try: |
| 104 | open_ = instances() |
| 105 | except (OSError, ValueError, AttributeError): |
| 106 | open_ = {} |
| 107 | if not open_: |
| 108 | print("verify.py finds no instances `n = N` in the scienceslack.json next to it: the project's maintainers must fix that") |
| 109 | return 2 |
| 110 | wanted = {f"n{n}.txt": n for n in open_} |
| 111 | expected = ", ".join(sorted(wanted, key=wanted.get)) |
| 112 | |
| 113 | judged, ignored = [], [] # ignored: the paths as the author knows them, relative to the folder given |
| 114 | for arg in map(Path, args): |
| 115 | if arg.is_dir(): |
| 116 | for folder, below, names in os.walk(arg): # links to folders are not followed |
| 117 | below.sort() |
| 118 | for name in sorted(names): |
| 119 | if Path(folder) == arg and name in wanted: |
| 120 | judged.append(arg / name) |
| 121 | elif name.lower().endswith(".txt"): |
| 122 | ignored.append((Path(folder) / name).relative_to(arg)) |
| 123 | elif arg.name in wanted and (arg.exists() or arg.is_symlink()): |
| 124 | judged.append(arg) |
| 125 | elif arg.exists(): |
| 126 | ignored.append(Path(arg.name)) |
| 127 | for f in ignored: |
| 128 | why = "a configuration counts only directly in the route's folder" if f.name in wanted else f"only {expected} are judged" |
| 129 | print(f"ignored: {shown(str(f), 120)} ({why})") |
| 130 | |
| 131 | best, wrong = {}, [] |
| 132 | for f in judged: |
| 133 | n = wanted[f.name] |
| 134 | try: |
| 135 | area, lines = smallest(points(f, n)) |
| 136 | if area == 0: |
| 137 | raise Wrong(f"{f.name}: the points on lines {lines[0]}, {lines[1]} and {lines[2]} lie on one line, so the smallest triangle has area 0: move one of them") |
| 138 | except Wrong as e: |
| 139 | wrong.append(str(e)) |
| 140 | print(f"FAILED {e}") |
| 141 | continue |
| 142 | exact = f" (exactly {area})" if area.denominator < 10**6 else "" |
| 143 | print(f"{f.name}: {n} points in the unit square, smallest triangle {cut(area)}{exact}, on lines {lines[0]}, {lines[1]} and {lines[2]}") |
| 144 | best[n] = max(best.get(n, 0), area) |
| 145 | |
| 146 | if wrong: |
| 147 | more = len(wrong) - 1 |
| 148 | print(wrong[0] + (f" (and {more} more in the log)" if more else "")) |
| 149 | return 1 |
| 150 | if not best: |
| 151 | print(f"Nothing to check yet: this route's folder holds none of {expected}." |
| 152 | + (f" {len(ignored)} other file{'s' if len(ignored) > 1 else ''} ignored, named in the log." if ignored else "")) |
| 153 | return 0 |
| 154 | print("; ".join(f"{open_[n]}: {cut(best[n])}" for n in sorted(best))) |
| 155 | return 0 |
| 156 | |
| 157 | |
| 158 | if __name__ == "__main__": |
| 159 | sys.exit(main(sys.argv[1:])) |