#!/usr/bin/env python3 """The check: the smallest triangle of each configuration, in exact arithmetic. Usage: verify.py FOLDER_OR_FILE... A folder means the n.txt files directly in it. Only the instances that scienceslack.json (next to this file) declares are judged; every other .txt file is named as ignored. A configuration is N lines `x y`, as decimals or fractions (0.25, 1/3); blank lines and lines starting with # are skipped. The last line is what the site shows on the commit: exit 0 `n = 11: 0.0370370370; n = 12: ...`, each value cut (never rounded up) to ten decimals, or that there is nothing to check yet; exit 1 the first thing wrong, with the file and the line to fix. """ import itertools import json import os import re import sys from fractions import Fraction from pathlib import Path DIGITS = 10 MAX_BYTES = 64_000 # the longest published coordinates (200 digits each, n = 16) take a tenth of this NUMBER = re.compile(r"[+-]?(\d+\.?\d*|\.\d+)([eE][+-]?\d{1,3})?|\d+/\d+", re.ASCII) # no exponent Fraction would choke on class Wrong(Exception): """A configuration the check refuses; its text is what the author reads.""" def shown(text, limit=60): """A name or a line as it is safe to print: one line, printable, not long.""" clean = "".join(c if c.isprintable() else "?" for c in text) return clean if len(clean) <= limit else clean[:limit] + "..." def cut(value): """A positive fraction as a decimal cut to DIGITS places: never more than the value.""" whole, rest = divmod(int(value * 10**DIGITS), 10**DIGITS) return f"{whole}.{rest:0{DIGITS}d}" def instances(): """The declared instances, as {N: "n = N"}.""" spec = json.loads((Path(__file__).resolve().parent / "scienceslack.json").read_text(encoding="utf-8")) found = {} for name in spec.get("instances", []): m = re.fullmatch(r"n\s*=\s*(\d+)", name.strip()) if m: found[int(m.group(1))] = name.strip() return found def points(path, n): """The n points of a file, each with its line number; Wrong if it does not hold n points of the unit square.""" name = path.name try: if path.is_symlink() or not path.is_file(): raise Wrong(f"{name} is not a regular file: commit the file itself") if path.stat().st_size > MAX_BYTES: raise Wrong(f"{name} is larger than {MAX_BYTES // 1000} kB: a configuration is {n} lines of two numbers") text = path.read_bytes().decode("utf-8") except (OSError, UnicodeDecodeError): raise Wrong(f"{name} cannot be read as UTF-8 text") from None pts = [] for at, line in enumerate(text.splitlines(), 1): parts = line.split() if not parts or parts[0].startswith("#"): continue try: if len(parts) != 2 or not all(NUMBER.fullmatch(p) for p in parts): raise ValueError pts.append((at, Fraction(parts[0]), Fraction(parts[1]))) except (ValueError, ZeroDivisionError): 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 if len(pts) != n: 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") for at, x, y in pts: if not (0 <= x <= 1 and 0 <= y <= 1): raise Wrong(f"{name} line {at}: the point lies outside the unit square: both coordinates must be between 0 and 1") first = {} for at, x, y in pts: if (x, y) in first: raise Wrong(f"{name} lines {first[(x, y)]} and {at} are the same point: all {n} points must differ") first[(x, y)] = at return pts def smallest(pts): """The smallest triangle: (area, the three line numbers).""" def doubled(t): (_, ax, ay), (_, bx, by), (_, cx, cy) = t return abs((bx - ax) * (cy - ay) - (cx - ax) * (by - ay)) t = min(itertools.combinations(pts, 3), key=doubled) return doubled(t) / 2, [p[0] for p in t] def main(args): if not args: print(__doc__.strip()) return 2 try: open_ = instances() except (OSError, ValueError, AttributeError): open_ = {} if not open_: print("verify.py finds no instances `n = N` in the scienceslack.json next to it: the project's maintainers must fix that") return 2 wanted = {f"n{n}.txt": n for n in open_} expected = ", ".join(sorted(wanted, key=wanted.get)) judged, ignored = [], [] # ignored: the paths as the author knows them, relative to the folder given for arg in map(Path, args): if arg.is_dir(): for folder, below, names in os.walk(arg): # links to folders are not followed below.sort() for name in sorted(names): if Path(folder) == arg and name in wanted: judged.append(arg / name) elif name.lower().endswith(".txt"): ignored.append((Path(folder) / name).relative_to(arg)) elif arg.name in wanted and (arg.exists() or arg.is_symlink()): judged.append(arg) elif arg.exists(): ignored.append(Path(arg.name)) for f in ignored: why = "a configuration counts only directly in the route's folder" if f.name in wanted else f"only {expected} are judged" print(f"ignored: {shown(str(f), 120)} ({why})") best, wrong = {}, [] for f in judged: n = wanted[f.name] try: area, lines = smallest(points(f, n)) if area == 0: 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") except Wrong as e: wrong.append(str(e)) print(f"FAILED {e}") continue exact = f" (exactly {area})" if area.denominator < 10**6 else "" print(f"{f.name}: {n} points in the unit square, smallest triangle {cut(area)}{exact}, on lines {lines[0]}, {lines[1]} and {lines[2]}") best[n] = max(best.get(n, 0), area) if wrong: more = len(wrong) - 1 print(wrong[0] + (f" (and {more} more in the log)" if more else "")) return 1 if not best: print(f"Nothing to check yet: this route's folder holds none of {expected}." + (f" {len(ignored)} other file{'s' if len(ignored) > 1 else ''} ignored, named in the log." if ignored else "")) return 0 print("; ".join(f"{open_[n]}: {cut(best[n])}" for n in sorted(best))) return 0 if __name__ == "__main__": sys.exit(main(sys.argv[1:]))