"""Small exact-algebra and matching routines used by the example checks.

All arithmetic is integral or rational. No numerical tolerance is used.
"""
from __future__ import annotations

from fractions import Fraction
from functools import lru_cache
from itertools import combinations, combinations_with_replacement
from typing import Iterable, Sequence


def rank(matrix: Sequence[Sequence[int | Fraction]]) -> int:
    """Compute matrix rank by Gaussian elimination over the rationals."""
    if not matrix:
        return 0
    width = len(matrix[0])
    if any(len(row) != width for row in matrix):
        raise ValueError("Ragged matrix")
    a = [list(map(Fraction, row)) for row in matrix]
    pivot = 0
    for col in range(width):
        row = next((r for r in range(pivot, len(a)) if a[r][col]), None)
        if row is None:
            continue
        a[pivot], a[row] = a[row], a[pivot]
        scale = a[pivot][col]
        a[pivot] = [x / scale for x in a[pivot]]
        for r in range(pivot + 1, len(a)):
            scale = a[r][col]
            if scale:
                a[r] = [x - scale * y for x, y in zip(a[r], a[pivot])]
        pivot += 1
        if pivot == len(a):
            break
    return pivot


def product(matrix: Sequence[Sequence[int]], vector: Sequence[int | Fraction]):
    """Multiply an integer matrix by an exact vector."""
    if any(len(row) != len(vector) for row in matrix):
        raise ValueError("Incompatible dimensions")
    return [sum(x * y for x, y in zip(row, vector)) for row in matrix]


def patterns(values: Sequence[int], multiplicities: Sequence[int], relation: str = "zero"):
    """List every available three-item pattern of the requested sign."""
    if len(values) != len(multiplicities) or min(multiplicities, default=0) < 0:
        raise ValueError("Invalid multiplicities")
    if relation not in {"zero", "nonpositive"}:
        raise ValueError("Unknown sign relation")
    found = []
    for triple in combinations_with_replacement(range(len(values)), 3):
        weight = sum(values[i] for i in triple)
        if (relation == "zero" and weight != 0) or (relation == "nonpositive" and weight > 0):
            continue
        p = [0] * len(values)
        for i in triple:
            p[i] += 1
        if all(x <= n for x, n in zip(p, multiplicities)):
            found.append(tuple(p))
    return found


def incidence(columns: Sequence[Sequence[int]]) -> list[list[int]]:
    if not columns:
        return []
    return [list(row) for row in zip(*columns)]


def maximum_matching(values: Sequence[int], relation: str = "zero"):
    """Return the size and one maximum matching on labelled items.

    The recurrence considers either omitting the first available item or
    using it in each feasible triple. Intended for the eighteen-item example.
    """
    if relation not in {"zero", "nonpositive"}:
        raise ValueError("Unknown sign relation")
    edges = []
    for e in combinations(range(len(values)), 3):
        total = sum(values[i] for i in e)
        if total == 0 or (relation == "nonpositive" and total < 0):
            edges.append((sum(1 << i for i in e), e))
    incident = [[] for _ in values]
    for mask, edge in edges:
        for i in edge:
            incident[i].append((mask, edge))

    @lru_cache(maxsize=None)
    def solve(mask: int):
        if mask.bit_count() < 3:
            return 0, ()
        bit = mask & -mask
        vertex = bit.bit_length() - 1
        best = solve(mask ^ bit)
        for edge_mask, edge in incident[vertex]:
            if edge_mask & mask == edge_mask:
                size, tail = solve(mask ^ edge_mask)
                if size + 1 > best[0]:
                    best = size + 1, (edge,) + tail
        return best

    size, matching = solve((1 << len(values)) - 1)
    return {"size": size, "edges": [list(e) for e in matching], "available_edges": len(edges)}


def check_matching(values: Sequence[int], multiplicities: Sequence[int], triples: Iterable[Sequence[int]]):
    """Check triples specified by values against the actual multiplicities."""
    remaining = dict(zip(values, multiplicities))
    if len(remaining) != len(values):
        raise ValueError("Value classes must be distinct")
    totals = []
    for e in triples:
        if len(e) != 3 or sum(e) > 0:
            raise AssertionError("Invalid nonpositive-sum triple")
        for x in e:
            if remaining.get(x, 0) == 0:
                raise AssertionError("Item used beyond its multiplicity")
            remaining[x] -= 1
        totals.append(sum(e))
    return totals, remaining