#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
unique_xor16_min8_checked.py

[Background: generated by Gwern Branwen on 2026-02-14 for Said Achmiz using GPT-5.2 Pro; checked with Claude-4.6-opus, Gemini-3-pro-preview, Kimi K2.5 Thinking, and DeepSeek, which claim the math and code are correct. Code runs successfully, but no promises are made beyond that.]

Goal
----

Construct 16 distinct 16-bit integers such that:

  (C1) 0x0000 and 0xFFFF do NOT appear among the 16 numbers.

  (C2) There exists at least one subset whose XOR is TARGET = 0xFFFF.

  (C3) The smallest subset that XORs to 0xFFFF has size exactly 8.

  (C4) Among subsets of size exactly 8, exactly ONE subset XORs to 0xFFFF.

  (C5) It is OK if subsets of size 9, 10, ... also XOR to 0xFFFF.

We also provide optional scrambling functions which preserve these properties for TARGET=0xFFFF.

Mathematical core (mandatory anchors)
-------------------------------------

Work in GF(2)^16 (XOR is vector addition).

Define 8 "anchors" over disjoint bit-pairs:

  For k = 0..7:
    A_k = (1 << (2k)) XOR (1 << (2k+1)) = 3 << (2k)

These anchors are:
  0x0003, 0x000C, 0x0030, 0x00C0, 0x0300, 0x0C00, 0x3000, 0xC000

They XOR to 0xFFFF because the eight pairs partition bits 0..15.

Now define 8 "extras" which have no odd bits set:

  extra & 0xAAAA == 0

(0xAAAA has 1s in odd bit positions 1,3,...,15.)

Key "tag-bit" lemma:

- Each odd bit (2k+1) appears in exactly one anchor A_k.
- No extra has any odd bit set.

Therefore, any subset whose XOR is 0xFFFF (which has all odd bits set to 1) must include every
anchor A_k. So any solution subset has size >= 8.

Since the anchors alone XOR to 0xFFFF, size 8 is achievable and minimal (C2,C3).
Uniqueness among size-8 solutions follows: the only 8-subset containing all 8 anchors is the
anchor set itself (C4).

Larger solutions
----------------

Any solution subset must be:

  anchors ∪ E

where E is a subset of the extras.

Because XOR(anchors) = 0xFFFF, we have:

  XOR(anchors ∪ E) = 0xFFFF  <=>  XOR(E) = 0

So larger solutions exist iff the extras contain a nontrivial zero-XOR subset.

We support two modes for extras:

- force_larger_solutions=False:
    extras are 8 even-position one-hot vectors.
    They have no nontrivial zero-XOR subset, so anchors are the only solution overall.

- force_larger_solutions=True:
    extras are chosen to GUARANTEE at least one nontrivial zero-XOR subset.
    We do this in a way that cannot fail:
      take 7 independent even-one-hots, and define the 8th as XOR of a random subset
      of size >=2 of those 7. This creates a dependency of size 3..8 among extras.

Optional scrambling (convenience)
---------------------------------

Sometimes the construction looks “patterned”.

We provide two scrambling transforms which preserve the exact set of solution subsets for 0xFFFF:

1) scramble_bit_permutation:
    Permute bit positions in every number (and optionally shuffle element order).
    This preserves XOR relationships, and 0xFFFF is invariant under bit permutation.

2) scramble_linear_fixing_ffff:
    Apply a random invertible 16×16 linear map A over GF(2) with A*0xFFFF=0xFFFF,
    then optionally shuffle element order.

    For any subset U:
        XOR(A*v for v in U) = A*(XOR(v for v in U))
    So subset XOR equals 0xFFFF before scrambling iff it does after scrambling.

    Invertible + A*0xFFFF=0xFFFF implies no other input maps to 0xFFFF:
        if A*x = 0xFFFF, then x = A^{-1}*0xFFFF = 0xFFFF.

Portability
-----------

This file avoids requiring Python 3.10+.

popcount() uses int.bit_count() when available, otherwise falls back to bin(x).count("1").

Run
---

  python3 unique_xor16_min8_checked.py

This runs the unit tests.

"""

from __future__ import annotations

import itertools
import random
import unittest
from typing import Iterable, List, Optional, Sequence, Tuple

BITS: int = 16
N: int = 16
K: int = 8
TARGET: int = 0xFFFF

ODD_MASK: int = 0xAAAA       # bits 1,3,5,...,15
EVEN_ONLY_MASK: int = 0x5555 # bits 0,2,4,...,14


# -------------------------
# Utilities
# -------------------------

def popcount(x: int) -> int:
    """Return the number of 1 bits in x, compatible with older Python versions."""
    try:
        return x.bit_count()  # Python 3.10+
    except AttributeError:
        return bin(x).count("1")


def xor_of_indices(nums: Sequence[int], idxs: Iterable[int]) -> int:
    """XOR together nums[i] for i in idxs."""
    x = 0
    for i in idxs:
        x ^= nums[i]
    return x


def permute_bits_16(x: int, mapping: Sequence[int]) -> int:
    """
    Permute bit positions of a 16-bit integer.

    mapping[old_bit] = new_bit, mapping is a permutation of 0..15.
    """
    if len(mapping) != 16:
        raise ValueError("mapping must have length 16")
    if sorted(mapping) != list(range(16)):
        raise ValueError("mapping must be a permutation of 0..15")

    y = 0
    for old in range(16):
        if (x >> old) & 1:
            y |= 1 << mapping[old]
    return y & 0xFFFF


def apply_row_matrix(rows: Sequence[int], v: int) -> int:
    """
    Apply a 16x16 GF(2) matrix A to a 16-bit vector v.

    rows[i] is a 16-bit mask representing row i of A.
    Output bit i is parity(rows[i] & v).
    """
    out = 0
    for i, row in enumerate(rows):
        if popcount(row & v) & 1:
            out |= 1 << i
    return out & 0xFFFF


def gf2_rank(rows: Sequence[int], bits: int = 16) -> int:
    """
    Rank over GF(2) of integer row-vectors (Gaussian elimination via XOR).
    """
    basis = [0] * bits
    mask = (1 << bits) - 1

    for r0 in rows:
        r = r0 & mask
        for b in range(bits - 1, -1, -1):
            if (r >> b) & 1:
                if basis[b]:
                    r ^= basis[b]
                else:
                    basis[b] = r
                    break
        # If r reduces to 0, it is dependent and ignored.

    return sum(1 for x in basis if x != 0)


def _rng_from(seed: Optional[int], rng: Optional[random.Random]) -> random.Random:
    """Helper: accept either seed or rng; prefer rng if provided."""
    return rng if rng is not None else random.Random(seed)


def _validate_instance_inputs(
    nums: Sequence[int],
    *,
    solution8: Optional[Sequence[int]] = None,
) -> None:
    """
    Validate basic invariants for a constructed instance.

    Raises ValueError on violation.
    """
    if len(nums) != 16:
        raise ValueError("expected exactly 16 numbers")
    if any((x < 0) or (x > 0xFFFF) for x in nums):
        raise ValueError("all numbers must be 16-bit (0..0xFFFF)")
    if len(set(nums)) != 16:
        raise ValueError("numbers must be distinct")
    if 0 in nums:
        raise ValueError("0x0000 is forbidden among the numbers")
    if TARGET in nums:
        raise ValueError("0xFFFF is forbidden among the numbers")

    if solution8 is not None:
        if len(solution8) != 8:
            raise ValueError("solution8 must have length 8")
        if any((i < 0) or (i >= 16) for i in solution8):
            raise ValueError("solution8 indices must be in 0..15")
        if len(set(solution8)) != 8:
            raise ValueError("solution8 indices must be distinct")
        if xor_of_indices(nums, solution8) != TARGET:
            raise ValueError("provided solution8 does not XOR to 0xFFFF")


# -------------------------
# Core construction
# -------------------------

def make_anchors_for_ffff() -> List[int]:
    """
    Return the eight anchors A_k = 3 << (2k), k=0..7.

    Properties:
      - XOR of all anchors is 0xFFFF.
      - Each anchor has a unique odd bit (2k+1).
      - No anchor is 0x0000 or 0xFFFF.
    """
    anchors = [((3 << (2 * k)) & 0xFFFF) for k in range(8)]
    if xor_of_indices(anchors, range(8)) != TARGET:
        raise AssertionError("anchors must XOR to 0xFFFF")
    if any(a == 0 or a == TARGET for a in anchors):
        raise AssertionError("anchors must not include 0x0000 or 0xFFFF")
    return anchors


def make_extras_even_only(
    *,
    seed: Optional[int] = None,
    rng: Optional[random.Random] = None,
    force_dependency: bool = False,
    max_attempts: int = 10_000,
) -> List[int]:
    """
    Construct 8 extra values with no odd bits set: extra & ODD_MASK == 0.

    - force_dependency=False:
        Return the canonical even-position one-hot vectors:
          [1<<0, 1<<2, ..., 1<<14]
        These have no nontrivial zero-XOR subset.

    - force_dependency=True:
        GUARANTEED dependency construction:
          Take the first 7 canonical one-hots as a linearly independent set.
          Choose a random subset of size 2..7 of those 7 and set dep to their XOR.
          Add dep as the 8th extra.
        This creates a nontrivial zero-XOR subset among extras of size 3..8.

    max_attempts only bounds the random subset selection path defensively
    (though it should never fail in practice).
    """
    if max_attempts <= 0:
        raise ValueError("max_attempts must be positive")

    canonical = [1 << (2 * k) for k in range(8)]  # 0x0001,0x0004,...,0x4000

    if not force_dependency:
        extras = canonical[:]
        if len(set(extras)) != 8:
            raise AssertionError("extras must be distinct")
        if any(e == 0 or e == TARGET for e in extras):
            raise AssertionError("extras must not include 0 or 0xFFFF")
        if any((e & ODD_MASK) != 0 for e in extras):
            raise AssertionError("extras must have no odd bits")
        return extras

    R = _rng_from(seed, rng)

    base = canonical[:7]  # 7 independent vectors
    for _ in range(max_attempts):
        subset_size = R.randrange(2, 8)  # 2..7 inclusive => dependency size 3..8
        chosen = R.sample(base, subset_size)
        dep = 0
        for v in chosen:
            dep ^= v
        dep &= 0xFFFF

        # dep cannot be 0 because subset_size>=2 among independent basis vectors.
        if dep == 0:
            continue
        # dep cannot equal any base element because it has at least 2 bits set.
        if dep in base:
            continue
        # dep remains even-only.
        if (dep & ODD_MASK) != 0:
            continue

        extras = base + [dep]
        if len(set(extras)) == 8 and all((e & ODD_MASK) == 0 for e in extras):
            return extras

    raise RuntimeError("failed to construct dependent extras within max_attempts (unexpected)")


def construct_instance(
    *,
    seed: Optional[int] = None,
    rng: Optional[random.Random] = None,
    force_larger_solutions: bool = False,
    shuffle: bool = False,
    shuffle_seed: Optional[int] = None,
) -> Tuple[List[int], Tuple[int, ...]]:
    """
    Build a 16-number instance satisfying (C1)-(C5) for TARGET=0xFFFF.

    Returns:
      nums: list[int] length 16
      solution8: tuple[int,...] indices of the unique size-8 solution subset

    Randomness controls:

    - Provide rng=... to fully control randomness with a single Random instance.
      If rng is provided, shuffle_seed must be None (enforced), to avoid ambiguity.

    - Provide seed=... to create a new internal Random(seed).

    - If shuffle=True:
        * If shuffle_seed is None, use the same RNG as extras generation.
        * If shuffle_seed is not None, use Random(shuffle_seed) for shuffling
          (deterministic but decoupled from extras generation).
          (This mode is only allowed when rng is None.)
    """
    if rng is not None and shuffle_seed is not None:
        raise ValueError("shuffle_seed cannot be used when rng is provided; choose one randomness source")

    R = _rng_from(seed, rng)

    anchors = make_anchors_for_ffff()
    extras = make_extras_even_only(rng=R, force_dependency=force_larger_solutions)

    nums = extras + anchors

    # In the unshuffled assembly, anchors occupy indices 8..15.
    solution8 = tuple(range(8, 16))

    if shuffle:
        S = R if shuffle_seed is None else random.Random(shuffle_seed)
        perm = list(range(16))
        S.shuffle(perm)

        nums2 = [nums[i] for i in perm]
        inv = {old: new for new, old in enumerate(perm)}
        solution8 = tuple(sorted(inv[i] for i in solution8))
        nums = nums2

    _validate_instance_inputs(nums, solution8=solution8)
    return nums, solution8


# -------------------------
# Verification (brute force)
# -------------------------

def count_solutions_size_k(nums: Sequence[int], target: int, k: int) -> Tuple[int, Optional[Tuple[int, ...]]]:
    """
    Count k-subsets whose XOR equals target.

    Returns (count, first_solution_indices_or_None).
    """
    n = len(nums)
    count = 0
    first = None
    for comb in itertools.combinations(range(n), k):
        if xor_of_indices(nums, comb) == target:
            count += 1
            if first is None:
                first = comb
    return count, first


def verify_minimal_unique_size8(nums: Sequence[int]) -> Tuple[bool, str, Optional[Tuple[int, ...]]]:
    """
    Verify the exact user-level constraints (C1)-(C4) for TARGET=0xFFFF.

      - 16 distinct 16-bit numbers
      - excludes 0x0000 and 0xFFFF
      - no solutions of size < 8
      - exactly one solution of size 8

    Returns (ok, message, unique_size8_solution_or_None).
    """
    try:
        _validate_instance_inputs(nums)
    except ValueError as e:
        return False, str(e), None

    # No solutions smaller than 8.
    for size in range(0, 8):
        c, _ = count_solutions_size_k(nums, TARGET, size)
        if c != 0:
            return False, f"found a solution of size {size} (< 8)", None

    # Exactly one size-8 solution.
    c8, sol8 = count_solutions_size_k(nums, TARGET, 8)
    if c8 != 1:
        return False, f"expected exactly 1 size-8 solution, found {c8}", None

    return True, "ok", sol8


# -------------------------
# Scrambling helpers
# -------------------------

def scramble_bit_permutation(
    nums: Sequence[int],
    solution8: Sequence[int],
    *,
    seed: Optional[int] = None,
    rng: Optional[random.Random] = None,
    shuffle: bool = True,
) -> Tuple[List[int], Tuple[int, ...]]:
    """
    Scramble by permuting bit positions (and optionally shuffling element order).

    Correctness:
      Bit permutation is an invertible linear map P over GF(2)^16.
      For any subset U: XOR(P*v for v in U) = P*(XOR(v for v in U)).
      Since TARGET=0xFFFF is all-ones, P*TARGET == TARGET.

    Therefore, the exact set of solution subsets for 0xFFFF is preserved.

    Safety:
      A pure bit permutation cannot map a nonzero non-0xFFFF value to 0 or 0xFFFF;
      it only reorders bits.
    """
    _validate_instance_inputs(nums, solution8=solution8)
    R = _rng_from(seed, rng)

    bit_perm = list(range(16))
    R.shuffle(bit_perm)
    out = [permute_bits_16(x, bit_perm) for x in nums]
    sol = tuple(solution8)

    if shuffle:
        perm = list(range(16))
        R.shuffle(perm)
        out2 = [out[i] for i in perm]
        inv = {old: new for new, old in enumerate(perm)}
        sol = tuple(sorted(inv[i] for i in sol))
        out = out2

    _validate_instance_inputs(out, solution8=sol)
    return out, sol


def random_invertible_matrix_fixing_ffff(
    *,
    seed: Optional[int] = None,
    rng: Optional[random.Random] = None,
    max_attempts: int = 10_000,
) -> List[int]:
    """
    Sample a random invertible 16x16 GF(2) matrix A (returned as 16 row masks) such that:

      A * 0xFFFF == 0xFFFF

    Condition:
      Let 1 = 0xFFFF be the all-ones vector.
      Output bit i is parity(row_i & 1) = parity(row_i).
      So A*1 = 1 iff every row has odd parity (odd popcount).

    Sampling strategy:
      - Sample random rows.
      - Enforce odd parity deterministically by flipping bit 0 if needed.
      - Test invertibility via rank(A)==16.

    max_attempts bounds the number of invertibility attempts.
    """
    if max_attempts <= 0:
        raise ValueError("max_attempts must be positive")

    R = _rng_from(seed, rng)

    for _ in range(max_attempts):
        rows: List[int] = []
        for _i in range(16):
            r = R.getrandbits(16)
            if r == 0:
                r = 1
            # Force odd parity so A*0xFFFF=0xFFFF.
            if popcount(r) % 2 == 0:
                r ^= 1  # flip bit 0; toggles parity
                if r == 0:
                    r = 1  # extremely unlikely edge-case, but keep strict
            rows.append(r & 0xFFFF)

        if gf2_rank(rows, 16) != 16:
            continue
        # Belt-and-suspenders check.
        if apply_row_matrix(rows, 0xFFFF) != 0xFFFF:
            continue
        return rows

    raise RuntimeError("failed to sample an invertible matrix fixing 0xFFFF within max_attempts")


def scramble_linear_fixing_ffff(
    nums: Sequence[int],
    solution8: Sequence[int],
    *,
    seed: Optional[int] = None,
    rng: Optional[random.Random] = None,
    shuffle: bool = True,
    max_attempts: int = 10_000,
) -> Tuple[List[int], Tuple[int, ...]]:
    """
    Scramble by applying a random invertible linear map A over GF(2)^16 with A*0xFFFF=0xFFFF,
    then optionally shuffling element order.

    Correctness:
      For any subset U:
        XOR(A*v for v in U) = A*(XOR(v for v in U)).
      Since A is invertible and A*TARGET=TARGET, subset XOR equals 0xFFFF before scrambling
      iff it does after scrambling.

    Note:
      Under invertible A with A*0xFFFF=0xFFFF, no other input can map to 0xFFFF.
      So (C1) is preserved automatically from a valid input instance.
      We still re-validate at the end as a cheap invariant check.
    """
    _validate_instance_inputs(nums, solution8=solution8)
    if max_attempts <= 0:
        raise ValueError("max_attempts must be positive")

    R = _rng_from(seed, rng)

    for _ in range(max_attempts):
        A = random_invertible_matrix_fixing_ffff(rng=R, max_attempts=max_attempts)
        out = [apply_row_matrix(A, x) for x in nums]

        # Invertible linear maps preserve distinctness and never map nonzero->0,
        # but keep strict invariants anyway.
        if 0 in out or len(set(out)) != 16:
            continue

        sol = tuple(solution8)

        if shuffle:
            perm = list(range(16))
            R.shuffle(perm)
            out2 = [out[i] for i in perm]
            inv = {old: new for new, old in enumerate(perm)}
            sol = tuple(sorted(inv[i] for i in sol))
            out = out2

        _validate_instance_inputs(out, solution8=sol)
        return out, sol

    raise RuntimeError("failed to scramble within max_attempts (unexpected)")


# -------------------------
# Tests
# -------------------------

class TestUniqueXor16Min8(unittest.TestCase):
    def test_canonical_instance(self) -> None:
        nums, sol8 = construct_instance(force_larger_solutions=False, shuffle=False)

        ok, msg, found = verify_minimal_unique_size8(nums)
        self.assertTrue(ok, msg)
        self.assertEqual(found, tuple(range(8, 16)))
        self.assertEqual(tuple(sol8), tuple(range(8, 16)))
        self.assertEqual(xor_of_indices(nums, sol8), TARGET)

        # In canonical mode, there should be no larger solutions at all.
        for size in range(9, 17):
            c, _ = count_solutions_size_k(nums, TARGET, size)
            self.assertEqual(c, 0)

    def test_force_larger_solutions(self) -> None:
        nums, sol8 = construct_instance(seed=123, force_larger_solutions=True, shuffle=False)

        ok, msg, found = verify_minimal_unique_size8(nums)
        self.assertTrue(ok, msg)
        self.assertEqual(found, tuple(range(8, 16)))
        self.assertEqual(xor_of_indices(nums, sol8), TARGET)

        # Confirm at least one larger solution exists (guaranteed by construction).
        found_larger = False
        for size in range(9, 17):
            c, _ = count_solutions_size_k(nums, TARGET, size)
            if c > 0:
                found_larger = True
                break
        self.assertTrue(found_larger)

    def test_shuffle_updates_solution_indices(self) -> None:
        nums, sol8 = construct_instance(seed=42, force_larger_solutions=False, shuffle=True)
        ok, msg, found = verify_minimal_unique_size8(nums)
        self.assertTrue(ok, msg)
        self.assertEqual(tuple(found), tuple(sol8))
        self.assertEqual(xor_of_indices(nums, sol8), TARGET)

    def test_rng_vs_shuffle_seed_semantics(self) -> None:
        # If rng is provided, shuffle_seed must not be.
        R = random.Random(0)
        with self.assertRaises(ValueError):
            construct_instance(rng=R, shuffle=True, shuffle_seed=123)

    def test_bit_permutation_scramble(self) -> None:
        nums, sol8 = construct_instance(seed=7, force_larger_solutions=True, shuffle=True)
        nums2, sol2 = scramble_bit_permutation(nums, sol8, seed=999, shuffle=True)

        ok, msg, found = verify_minimal_unique_size8(nums2)
        self.assertTrue(ok, msg)
        self.assertEqual(tuple(found), tuple(sol2))
        self.assertEqual(xor_of_indices(nums2, sol2), TARGET)

    def test_linear_scramble_fixing_ffff(self) -> None:
        nums, sol8 = construct_instance(seed=7, force_larger_solutions=True, shuffle=True)
        nums2, sol2 = scramble_linear_fixing_ffff(nums, sol8, seed=2024, shuffle=True)

        ok, msg, found = verify_minimal_unique_size8(nums2)
        self.assertTrue(ok, msg)
        self.assertEqual(tuple(found), tuple(sol2))
        self.assertEqual(xor_of_indices(nums2, sol2), TARGET)

    def test_scramblers_reject_bad_inputs(self) -> None:
        nums, sol8 = construct_instance(seed=1, force_larger_solutions=False, shuffle=False)

        bad_nums = list(nums)
        bad_nums[0] = 0  # forbidden
        with self.assertRaises(ValueError):
            scramble_bit_permutation(bad_nums, sol8, seed=0)

        with self.assertRaises(ValueError):
            scramble_linear_fixing_ffff(bad_nums, sol8, seed=0)

        # Wrong solution indices.
        with self.assertRaises(ValueError):
            scramble_bit_permutation(nums, sol8[:7], seed=0)

    def test_stress_many_seeds_fast(self) -> None:
        # Moderate stress test; still quick since C(16,8)=12870 and we only brute-force
        # sizes <= 8 per instance.
        for s in range(10000):
            nums, sol8 = construct_instance(
                seed=s,
                force_larger_solutions=(s % 2 == 0),
                shuffle=True,
            )
            ok, msg, found = verify_minimal_unique_size8(nums)
            self.assertTrue(ok, f"seed={s}: {msg}")
            self.assertEqual(tuple(found), tuple(sol8))
            self.assertEqual(xor_of_indices(nums, sol8), TARGET)


if __name__ == "__main__":
    unittest.main()