Costas array of order 33

"""Verifier for "Costas array of order 33" (statement in costas_33.json).

Problem: a Costas array of order K is a K x K grid with one mark in each row
and each column (a permutation), such that the K*(K-1)/2 vectors joining
pairs of marks are all different. Row r has its mark in column c[r]; the
vector from the mark in row r to the mark in row r + d is (d, c[r+d] - c[r]).
Vectors with different row gaps d are automatically different, so the
condition is: for every gap d, the column differences c[r+d] - c[r] are
pairwise distinct. Costas arrays are known for every order up to 31; 32 and
33 are the smallest orders with none known.

Expected submission: a JSON object with the permutation as JSON integers,
e.g. (order 4)

    {"perm": [0, 1, 3, 2]}

What the verifier checks, in order:
  1. The payload is at most MAX_BYTES characters and is a JSON object with
     exactly the key "perm".
  2. "perm" is a list of exactly K integers in 0..K-1.
  3. The entries are pairwise distinct, i.e. a permutation.
  4. For every row gap d = 1..K-1, the differences c[r+d] - c[r] are
     pairwise distinct.
"""
import json

# Order of the array.
K = 33
# Maximum size of the whole submission, in characters.
MAX_BYTES = 2_000


# ---------------------------------------------------------------------------
# Input-parsing 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


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

def _check(solution):
    # Steps 1-2: read the JSON object and the K column indices.
    sol = _load(solution, ("perm",), MAX_BYTES)
    perm = _int_list(sol["perm"], K, 0, K - 1)

    # Step 3: one mark per column, i.e. no column used twice.
    if len(set(perm)) != K:
        return False

    # Step 4: for each row gap d, all vectors (d, c[r+d] - c[r]) must differ,
    # which means their column components must differ.
    for d in range(1, K):
        diffs = [perm[r + d] - perm[r] for r in range(K - d)]
        if len(set(diffs)) != len(diffs):
            return False
    return True


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