Ternary covering code K₃(6,1)

"""Verifier for "Ternary covering code K_3(6,1)" (statement in covering_code_ternary.json).

Problem: find at most MAX_SIZE words of length LEN over the alphabet
{0, ..., Q-1} (the codewords) such that every one of the Q**LEN words is
within Hamming distance RADIUS of some codeword, i.e. differs from it in at
most RADIUS positions. The smallest possible size for Q = 3, LEN = 6,
RADIUS = 1 is known to lie between 71 and 73, so a code of 72 words would be
a new record.

Expected submission: a JSON object with the codewords as lists of JSON
integers, e.g.

    {"codewords": [[0, 0, 0, 0, 0, 0], [1, 1, 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 "codewords".
  2. "codewords" is a list of at most MAX_SIZE codewords, each exactly LEN
     integers in 0..Q-1. (Repeated codewords are allowed; they only waste
     space.)
  3. The Hamming balls of radius RADIUS around the codewords together contain
     all Q**LEN words.

With the defaults a ball holds 1 + 6 * 2 = 13 words, so step 3 builds a set
of at most 72 * 13 = 936 words and compares its size with 3**6 = 729.
"""
import json

# Alphabet size (ternary).
Q = 3
# Length of the words.
LEN = 6
# Covering radius: every word must be within this Hamming distance of a codeword.
RADIUS = 1
# Largest allowed number of codewords (73 is the best known).
MAX_SIZE = 72
# Maximum size of the whole submission, in characters.
MAX_BYTES = 10_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 _ball(word, radius):
    """All words (as tuples) within Hamming distance `radius` of `word`."""
    ball = {word}
    for _ in range(radius):
        # Grow the ball by one: change one position of every word found so far.
        ball |= {w[:i] + (s,) + w[i + 1:] for w in ball for i in range(len(w)) for s in range(Q)}
    return ball


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

def _check(solution):
    # Step 1: read the JSON object with its single key "codewords".
    sol = _load(solution, ("codewords",), MAX_BYTES)

    # Step 2: at most MAX_SIZE codewords of LEN symbols each. The count is
    # checked before any codeword is parsed.
    codewords = sol["codewords"]
    if not isinstance(codewords, list) or len(codewords) > MAX_SIZE:
        return False
    words = [tuple(_int_list(c, LEN, 0, Q - 1)) for c in codewords]

    # Step 3: collect every word covered by some codeword; all Q**LEN words
    # must be there.
    covered = set()
    for w in words:
        covered |= _ball(w, RADIUS)
    return len(covered) == Q ** LEN


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