"""Secret Santa with no redraws: does anyone pick their own name?"""

from fractions import Fraction
from math import factorial

from ..rng import Stream

NAME = "selfdraw"
FAMILY = "Secret Santa"

RULES = """`people` people each put their name in a hat. The names are shuffled uniformly at random
and each person takes one (equivalently: a uniformly random permutation of the people).
Nobody puts a name back. Report the probability that at least one person ends up with
their own name."""
AGENT_TESTS = [{"people": 10}, {"people": 4}]
AGENT_RETURN = "p"


def pages():
    return [{"params": {"people": n}, "chunks": 1_000, "chunk_size": 10_000} for n in range(3, 31)]


def slug(p):
    return f"secret-santa-someone-draws-their-own-name-{p['people']}-people"


def title(p):
    return f"Secret Santa with {p['people']} people: what is the chance someone draws their own name?"


def intro(p):
    return (f"{p['people']} people each draw one name from a hat, with no redraws. "
            "How often does at least one person get their own name?")


def columns(p):
    return ["games", "anyone_self", "two_or_more_self", "self_draws"]


def sim_chunk(p, seed, chunk, n):
    m = p["people"]
    st = Stream(seed, chunk)
    below = st.below
    out = [n, 0, 0, 0]
    for _ in range(n):
        perm = list(range(m))
        for i in range(m - 1, 0, -1):
            j = below(i + 1)
            perm[i], perm[j] = perm[j], perm[i]
        f = 0
        for i in range(m):
            if perm[i] == i:
                f += 1
        if f:
            out[1] += 1
            if f > 1:
                out[2] += 1
            out[3] += f
    return out


def _derange(n):
    a, b = 1, 0  # D0, D1
    if n == 0:
        return 1
    for k in range(2, n + 1):
        a, b = b, (k - 1) * (a + b)
    return b


def exact(p):
    n = p["people"]
    nf = factorial(n)
    none = Fraction(_derange(n), nf)
    one = Fraction(n * _derange(n - 1), nf)
    return {"headline": 1 - none,
            "cols": {"anyone_self": 1 - none, "two_or_more_self": 1 - none - one},
            "mean_self": Fraction(1),
            "method": "derangement count: D(n)/n! is the chance nobody draws themselves"}


def headline(p, tot):
    return tot[1], tot[0]


def row_labels(p):
    return [("anyone_self", "At least one person draws their own name"),
            ("two_or_more_self", "Two or more people draw their own name")]