Hadamard matrix of order 668

"""Verifier for "Hadamard matrix of order 668" (statement in hadamard_668.json).

Problem: find an N x N matrix H with entries +1 and -1 whose rows are pairwise
orthogonal, i.e. H * H^T = N * I. Such matrices can only exist for N = 1, 2
or a multiple of 4, and the Hadamard conjecture says they exist for every
multiple of 4. 668 was the smallest open order until August 2026, when
constructions for it (and for every other open order below 2000) were
announced. The problem is therefore solved; this verifier is kept as a
template for matrix certificates.

Expected submission: a JSON object with the rows as lists of JSON integers
1 and -1, e.g. (a 2 x 2 stand-in)

    {"matrix": [[1, 1], [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 "matrix".
  2. "matrix" is N rows of N integers, each 1 or -1.
  3. Every pair of rows is orthogonal (dot product 0). The diagonal of
     H * H^T is automatically N, since every entry squares to 1.

How step 3 is done: multiplying out all C(668, 2) = 222,778 row pairs would
take about 150 million multiplications, far too slow in pure Python. Instead
each row becomes a bitmask with a 1 wherever the entry is -1. Two entries
multiply to +1 where the rows agree and to -1 where they differ, so

    dot(a, b) = N - 2 * (number of positions where they differ)
              = N - 2 * popcount(mask_a XOR mask_b)

and the rows are orthogonal exactly when popcount(mask_a XOR mask_b) = N / 2.
That is one XOR and one bit count per pair, a few hundredths of a second.
"""
import itertools
import json

# Order of the matrix.
N = 668
# Maximum size of the whole submission, in characters. A 668 x 668 matrix
# written with ", " separators is about 1.6 MB.
MAX_BYTES = 4_000_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


def _int_matrix(rows, n, lo, hi):
    """Return `rows` if it is an n x n list of lists of integers in [lo, hi], or raise."""
    if not isinstance(rows, list) or len(rows) != n:
        raise ValueError
    for row in rows:
        _int_list(row, n, lo, hi)
    return rows


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

def _check(solution):
    # Steps 1-2: read the JSON object and the N x N matrix. The range -1..1
    # still allows 0, which is excluded separately.
    sol = _load(solution, ("matrix",), MAX_BYTES)
    rows = _int_matrix(sol["matrix"], N, -1, 1)
    if any(0 in row for row in rows):
        return False

    # Each row as a bitmask with a 1 where the entry is -1. The bit order does
    # not matter, as long as it is the same for every row.
    masks = [int("".join("1" if v < 0 else "0" for v in row), 2) for row in rows]

    # Step 3: rows a and b are orthogonal iff they differ in exactly N / 2 places.
    for a, b in itertools.combinations(masks, 2):
        if 2 * (a ^ b).bit_count() != N:
            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