#!/usr/bin/env python3
"""Independent, intentionally simple checker for small finite witnesses."""

from __future__ import annotations

import itertools
import math
import pathlib
import sys


def parse(path: pathlib.Path) -> list[tuple[int, int]]:
    words = path.read_text().split()
    if not words:
        raise ValueError("empty candidate")
    k = int(words[0])
    if k <= 0 or len(words) != 1 + 2 * k:
        raise ValueError("wrong token count or nonpositive k")
    pairs = [(int(words[1 + 2 * i]), int(words[2 + 2 * i])) for i in range(k)]
    previous = 1
    for n, a in pairs:
        if n <= previous:
            raise ValueError("moduli are not strictly increasing above 1")
        if not 0 <= a < n:
            raise ValueError("residue is not canonical")
        previous = n
    return pairs


def covers(pairs: list[tuple[int, int]]) -> bool:
    if not pairs:
        return False
    period = math.lcm(*(n for n, _ in pairs))
    return all(any(x % n == a for n, a in pairs) for x in range(period))


def some_assignment_covers(moduli: list[int]) -> tuple[int, ...] | None:
    if not moduli:
        return None
    # If a cover exists, translating by the negative of its first residue gives
    # one with first residue zero.
    for tail in itertools.product(*(range(n) for n in moduli[1:])):
        residues = (0,) + tail
        if covers(list(zip(moduli, residues))):
            return residues
    return None


def main() -> int:
    if len(sys.argv) != 2:
        print(f"usage: {sys.argv[0]} candidate.txt", file=sys.stderr)
        return 2
    try:
        pairs = parse(pathlib.Path(sys.argv[1]))
        if not covers(pairs):
            raise ValueError("displayed classes do not cover")
        for deleted in range(len(pairs)):
            moduli = [n for i, (n, _) in enumerate(pairs) if i != deleted]
            witness = some_assignment_covers(moduli)
            if witness is not None:
                raise ValueError(
                    f"reducible after deleting {pairs[deleted][0]}: "
                    + ", ".join(f"{a} (mod {n})" for n, a in zip(moduli, witness))
                )
    except (OSError, ValueError) as exc:
        print(f"FAIL: {exc}", file=sys.stderr)
        return 1
    print("PASS: independent exhaustive Python cross-check")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())
