#!/usr/bin/env python3
"""Exact uniqueness and line-solvability of random small nonograms.

Reproduces the acceptance rule of the Altamens Pixel Logic generator
(makePixels in app/lib/puzzleCollection.ts): each cell is filled with
probability p = 0.55, a grid is accepted when it has at least one filled and
one empty cell and its row and column clues have exactly one solution, and
the generator gives up after 60 attempts and shows a fixed striped fallback.

Requires Python 3.9+ and NumPy. Uniqueness is exact enumeration over all
2^(n*n) grids. Line solvability is exact for 3x3 and 4x4; for 5x5 it is a
seeded Monte Carlo estimate (SEED, MC_DRAWS) with a 95% Wilson interval,
because single-line deduction on all 25 million unique 5x5 grids is slow in
pure Python. Writes results.csv and by_fill.csv to the working directory.
"""
import csv, sys
from fractions import Fraction
import numpy as np

P_FILL = Fraction(55, 100)
ATTEMPTS = 60
SEED = 20261118
# Published counts used as checks: OEIS A242876 (uniquely solvable n x n
# nonograms) and A391619 (solvable by single-line reasoning), retrieved 2026-11-18.
OEIS_UNIQUE = {3: 384, 4: 52362, 5: 25309575}
OEIS_LINE = {3: 384, 4: 51234, 5: 24976511}
MC_DRAWS = 200_000


def runs(bits):
    out, c = [], 0
    for b in bits:
        if b:
            c += 1
        elif c:
            out.append(c); c = 0
    if c:
        out.append(c)
    return tuple(out) or (0,)


def line_bits(v, n):
    return [(v >> i) & 1 for i in range(n)]


def enumerate_size(n):
    """Return dict: clue key -> list of grid ints, using numpy for speed."""
    clue_of = [runs(line_bits(v, n)) for v in range(2 ** n)]
    ids = {c: i for i, c in enumerate(sorted(set(clue_of)))}
    lut = np.array([ids[c] for c in clue_of], dtype=np.int64)
    k = len(ids)
    g = np.arange(2 ** (n * n), dtype=np.int64)
    rows = [(g >> (n * r)) & (2 ** n - 1) for r in range(n)]
    key = np.zeros_like(g)
    for r in range(n):
        key = key * k + lut[rows[r]]
    for c in range(n):
        col = np.zeros_like(g)
        for r in range(n):
            col |= ((rows[r] >> c) & 1) << r
        key = key * k + lut[col]
    del rows
    _, inv, counts = np.unique(key, return_inverse=True, return_counts=True)
    unique_mask = counts[inv] == 1
    filled = np.zeros_like(g)
    for i in range(n * n):
        filled += (g >> i) & 1
    return g, unique_mask, filled


def grid_rows(gint, n):
    return [line_bits((gint >> (n * r)) & (2 ** n - 1), n) for r in range(n)]


def line_solve(rows_clues, cols_clues, n):
    """Iterate single-line deduction until no change. True if fully solved."""
    cands = {}
    allines = [tuple(line_bits(v, n)) for v in range(2 ** n)]
    by_clue = {}
    for ln in allines:
        by_clue.setdefault(runs(ln), []).append(ln)
    grid = [[None] * n for _ in range(n)]
    changed = True
    while changed:
        changed = False
        for axis in (0, 1):
            clues = rows_clues if axis == 0 else cols_clues
            for i in range(n):
                cur = [grid[i][j] if axis == 0 else grid[j][i] for j in range(n)]
                fits = [ln for ln in by_clue[clues[i]]
                        if all(c is None or c == b for c, b in zip(cur, ln))]
                for j in range(n):
                    if cur[j] is None:
                        vals = {ln[j] for ln in fits}
                        if len(vals) == 1:
                            v = vals.pop()
                            if axis == 0:
                                grid[i][j] = v
                            else:
                                grid[j][i] = v
                            changed = True
    return all(c is not None for row in grid for c in row)


def solved_by_lines(gint, n):
    rr = grid_rows(gint, n)
    rc = [runs(r) for r in rr]
    cc = [runs([rr[r][c] for r in range(n)]) for c in range(n)]
    return line_solve(rc, cc, n)


def mc_line_solvable(g, uniq, n, p, draws, seed):
    """Share of accepted grids (drawn at fill rate p) that line logic solves."""
    rng = np.random.default_rng(seed)
    cells = n * n
    acc = ok = 0
    while acc < draws:
        bits = rng.random((50_000, cells)) < p
        ints = (bits.astype(np.int64) << np.arange(cells, dtype=np.int64)).sum(axis=1)
        k = bits.sum(axis=1)
        keep = uniq[ints] & (k > 0) & (k < cells)
        for gi in ints[keep]:
            if acc >= draws:
                break
            acc += 1
            ok += solved_by_lines(int(gi), n)
    return ok, acc


def wilson(x, m, z=1.959964):
    ph = x / m
    d = 1 + z * z / m
    c = (ph + z * z / (2 * m)) / d
    h = z * ((ph * (1 - ph) / m + z * z / (4 * m * m)) ** 0.5) / d
    return c - h, c + h


def weight(k, cells, p):
    return p ** k * (1 - p) ** (cells - k)


def main():
    out, by_fill = [], []
    for n in (3, 4, 5):
        cells = n * n
        g, uniq, filled = enumerate_size(n)
        total = len(g)
        n_unique = int(uniq.sum())
        assert n_unique == OEIS_UNIQUE[n], (n, n_unique)
        u_by_k = np.bincount(filled[uniq], minlength=cells + 1)
        all_by_k = np.bincount(filled, minlength=cells + 1)
        for k in range(cells + 1):
            by_fill.append({"grid": f"{n}x{n}", "filled_cells": k,
                            "grids": int(all_by_k[k]), "unique": int(u_by_k[k]),
                            "unique_pct": round(100 * int(u_by_k[k]) / int(all_by_k[k]), 2)})
        if n == 4:
            # smallest-index examples: one ambiguous grid, one unique grid not solved by lines
            amb = int(g[~uniq][0]) if (~uniq).any() else None
            hard = next(int(x) for x in g[uniq] if not solved_by_lines(int(x), n))
            for name, gi in (("ambiguous", amb), ("unique_not_line_solvable", hard)):
                rr = grid_rows(gi, n)
                print(name, ["".join("#" if b else "." for b in r) for r in rr],
                      "rows", [runs(r) for r in rr],
                      "cols", [runs([rr[r][c] for r in range(n)]) for c in range(n)], file=sys.stderr)
        ls_by_k = np.zeros(cells + 1, dtype=np.int64)
        ls_count = None
        if n <= 4:
            ls_count = 0
            for gi in g[uniq]:
                if solved_by_lines(int(gi), n):
                    ls_count += 1
                    ls_by_k[bin(int(gi)).count("1")] += 1
        if ls_count is not None:
            assert ls_count == OEIS_LINE[n], (n, ls_count)
        print(n, total, n_unique, ls_count, file=sys.stderr)
        for label, p in (("uniform p=0.50", Fraction(1, 2)), ("Pixel Logic p=0.55", P_FILL)):
            p_unique = sum(Fraction(int(u_by_k[k])) * weight(k, cells, p) for k in range(cells + 1))
            # generator acceptance excludes all-empty (k=0) and all-filled (k=cells)
            p_accept = sum(Fraction(int(u_by_k[k])) * weight(k, cells, p) for k in range(1, cells))
            if ls_count is not None:
                ls_pct = float(sum(Fraction(int(ls_by_k[k])) * weight(k, cells, p) for k in range(1, cells)) / p_accept) * 100
                ls_low = ls_high = ls_pct
                ls_method = "exact"
            else:
                ok, m = mc_line_solvable(g, uniq, n, float(p), MC_DRAWS, SEED)
                ls_pct = ok / m * 100
                lo, hi = wilson(ok, m)
                ls_low, ls_high = lo * 100, hi * 100
                ls_method = f"Monte Carlo, {m} accepted grids, seed {SEED}"
            p_fallback = (1 - p_accept) ** ATTEMPTS
            exp_attempts = (1 - p_fallback) / p_accept  # E[min(geometric, 60)]
            mean_fill_acc = sum(Fraction(k * int(u_by_k[k])) * weight(k, cells, p) for k in range(1, cells)) / p_accept / cells
            out.append({
                "grid": f"{n}x{n}", "draw": label,
                "grids_total": total, "grids_unique": n_unique,
                "grids_unique_line_solvable": "" if ls_count is None else ls_count,
                "p_unique_pct": round(float(p_unique) * 100, 4),
                "p_accept_per_attempt_pct": round(float(p_accept) * 100, 4),
                "line_solvable_given_accepted_pct": round(ls_pct, 2),
                "line_solvable_95ci_low_pct": round(ls_low, 2),
                "line_solvable_95ci_high_pct": round(ls_high, 2),
                "line_solvable_method": ls_method,
                "p_fallback_after_60": f"{float(p_fallback):.2e}",
                "expected_attempts_capped_60": round(float(exp_attempts), 2),
                "mean_fill_accepted_pct": round(float(mean_fill_acc) * 100, 1),
            })
    with open("results.csv", "w", newline="") as f:
        w = csv.DictWriter(f, fieldnames=list(out[0].keys()))
        w.writeheader(); w.writerows(out)
    with open("by_fill.csv", "w", newline="") as f:
        w = csv.DictWriter(f, fieldnames=list(by_fill[0].keys()))
        w.writeheader(); w.writerows(by_fill)
    for r in out:
        print(r)


if __name__ == "__main__":
    main()
