Six sixth powers

"""Verifier for "Six sixth powers" (statement in sixth_powers.json).

Problem: find between 2 and 6 positive integers t_1, ..., t_k and a positive
integer b such that

    t_1**6 + t_2**6 + ... + t_k**6 == b**6

The smallest known solution uses 7 terms; a solution with 6 or fewer is new.

Expected submission: a JSON object with a list of terms and the base b, all
as decimal strings:

    {"terms": ["3", "4", "5"], "b": "6"}

What the verifier checks, in order:
  1. The payload is at most MAX_BYTES characters and is a JSON object with
     exactly the keys "terms" and "b".
  2. "terms" is a list with between 2 and MAX_TERMS entries. At least two
     terms are required because t**6 == b**6 with one term is trivial.
  3. Every term and b are well-formed decimal strings of at most MAX_DIGITS
     digits (see _parse_int) and are at least 1. Zero is excluded because
     0**6 + b**6 == b**6 would be trivial.
  4. Each power is small enough to compute: EXP * bit length of the number
     must be at most MAX_POWER_BITS (checked before any power is computed).
  5. The sum of the terms raised to EXP equals b raised to EXP, exactly.
"""
import json

# The exponent. The tests set it to 5 to check the known fifth-power identity
# 27**5 + 84**5 + 110**5 + 133**5 == 144**5.
EXP = 6
# The largest number of terms allowed. The tests raise it to 7 to check the
# known seven-term identity with b = 1141.
MAX_TERMS = 6
# Maximum number of digits allowed in each term and in b.
MAX_DIGITS = 10_000
# Maximum size, in bits, of any single power, measured as EXP * bit length.
# It only protects against modified constants: at the defaults the largest
# power is about 200,000 bits, so this limit is never reached.
MAX_POWER_BITS = 1_000_000
# Maximum size of the whole submission, in characters.
MAX_BYTES = 80_000


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

def _parse_int(s, max_digits, allow_neg=False):
    """Convert a strictly formatted decimal string to an int, or raise ValueError.

    Accepted: "0", "42", and "-42" when allow_neg is True.
    Rejected: anything that is not a string (for example a JSON number), "",
    "+42", " 42", "007", "-0", non-ASCII digits such as "٣", and strings with
    more than max_digits digits.
    """
    # Cheap length check before any real work: at most max_digits digits,
    # plus one character for an optional minus sign.
    if not isinstance(s, str) or len(s) > max_digits + 1:
        raise ValueError
    # Split off the sign. A "-" is only allowed where negative values make sense.
    neg = s.startswith("-")
    if neg and not allow_neg:
        raise ValueError
    body = s[1:] if neg else s
    # What remains must be 1 to max_digits ASCII digits with no leading zero
    # ("0" on its own is fine). isascii() is needed because isdigit() also
    # accepts digits from other scripts.
    if not (body.isascii() and body.isdigit()) or len(body) > max_digits or (len(body) > 1 and body[0] == "0"):
        raise ValueError
    # "-0" is not a canonical way to write zero.
    if neg and body == "0":
        raise ValueError
    # Python (3.11 and later) refuses int() on strings longer than 4300 digits
    # by default, so the number is built from chunks of 4000 digits.
    n = 0
    for i in range(0, len(body), 4000):
        chunk = body[i:i + 4000]
        n = n * 10 ** len(chunk) + int(chunk)
    return -n if neg else n


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


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

def _check(solution):
    # Step 1: read the JSON object with the keys "terms" and "b".
    sol = _load(solution, ("terms", "b"), MAX_BYTES)

    # Step 2: "terms" must be a list of 2 to MAX_TERMS entries. The length is
    # checked before parsing anything so an oversized list costs nothing.
    terms = sol["terms"]
    if not isinstance(terms, list) or not 2 <= len(terms) <= MAX_TERMS:
        return False

    # Step 3: parse every term and b; all must be positive.
    ts = [_parse_int(t, MAX_DIGITS) for t in terms]
    b = _parse_int(sol["b"], MAX_DIGITS)
    if min(ts) < 1 or b < 1:
        return False

    # Step 4: a b-bit number raised to EXP has at most EXP * b bits; refuse
    # anything above the limit before computing it.
    if any(EXP * v.bit_length() > MAX_POWER_BITS for v in ts + [b]):
        return False

    # Step 5: the equation itself, with exact integer arithmetic.
    return sum(t ** EXP for t in ts) == b ** EXP


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
    number, ...) means the submission is rejected, so this function never raises.
    """
    try:
        return _check(solution) is True
    except Exception:
        return False