No-three-in-line, 71×71 grid

"""Verifier for "No-three-in-line, 71x71 grid" (statement in no_three_in_line_71.json).

Problem: place 2N points on the N x N grid {0, ..., N-1}^2 so that no three of
them lie on a common straight line, in any direction (not only rows, columns
and diagonals). A row can hold at most 2 such points, so 2N is the most
possible. Solutions are known for every N up to 70; N = 71 is the smallest
open case.

Expected submission: a JSON object with the points as [i, j] pairs of JSON
integers, e.g.

    {"points": [[0, 0], [0, 1], [1, 0], [1, 1]]}

What the verifier checks, in order:
  1. The payload is at most MAX_BYTES characters and is a JSON object with
     exactly the key "points".
  2. "points" is a list of exactly 2N pairs of integers in 0..N-1.
  3. The points are pairwise distinct.
  4. No three points are collinear. Every triple gets the exact integer
     orientation test: C(142, 3) = 467,180 triples at N = 71, about 0.04 s.
"""
import itertools
import json

# Side of the grid; the solver must place 2N points on it.
N = 71
# Maximum size of the whole submission, in characters.
MAX_BYTES = 10_000


# ---------------------------------------------------------------------------
# Input-parsing and geometry helpers. The same code is copied into every
# verifier that needs it, so that each file works on its own.
# ---------------------------------------------------------------------------

def _load(solution, keys, max_bytes):
    """Parse the submission as a JSON object with exactly the given keys, or raise."""
    # Refuse oversized payloads before handing them to the JSON parser.
    if not isinstance(solution, str) or len(solution) > max_bytes:
        raise ValueError
    d = json.loads(solution)
    # It must be an object (not a list, string or number) whose keys are
    # exactly the expected ones: nothing missing, nothing extra.
    if not isinstance(d, dict) or set(d) != set(keys):
        raise ValueError
    return d


def _int_list(values, n, lo, hi):
    """Return `values` if it is a list of exactly n integers in [lo, hi], or raise.

    The length is checked before any element is looked at. `type(v) is int`
    (rather than isinstance) also rejects true and false, which Python treats
    as the integers 1 and 0; floats such as 1.0 and strings such as "1" are
    rejected as well.
    """
    if not isinstance(values, list) or len(values) != n:
        raise ValueError
    for v in values:
        if type(v) is not int or not lo <= v <= hi:
            raise ValueError
    return values


def _int_grid(cells, n, lo, hi):
    """Return exactly n points [i, j] with both coordinates in [lo, hi] as tuples, or raise."""
    if not isinstance(cells, list) or len(cells) != n:
        raise ValueError
    return [tuple(_int_list(c, 2, lo, hi)) for c in cells]


def _orient(a, b, c):
    """Orientation of the triangle a, b, c: > 0 if it turns counterclockwise,
    < 0 if clockwise, 0 if the three points are collinear.

    This is twice the signed area of the triangle, computed exactly because
    the coordinates are integers.
    """
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])


def _no_three_collinear(points):
    """True iff no three of `points` lie on a common line (checks every triple)."""
    return all(_orient(a, b, c) != 0 for a, b, c in itertools.combinations(points, 3))


# ---------------------------------------------------------------------------
# The actual check.
# ---------------------------------------------------------------------------

def _check(solution):
    # Steps 1-2: read the JSON object and the 2N grid points.
    sol = _load(solution, ("points",), MAX_BYTES)
    points = _int_grid(sol["points"], 2 * N, 0, N - 1)

    # Step 3: no point may be used twice.
    if len(set(points)) != len(points):
        return False

    # Step 4: no three points on a line.
    return _no_three_collinear(points)


def verify(solution: str, rng) -> bool:
    """Platform entry point: return True only for a valid, correct solution.

    `rng` (a numpy.random.Generator) is part of the platform interface but is
    not used: this check is deterministic. Any exception (malformed JSON, a bad
    value, ...) means the submission is rejected, so this function never raises.
    """
    try:
        return _check(solution) is True
    except Exception:
        return False