"""Exact finite-fuel majority walk and source-level probability budgets."""
from dataclasses import dataclass
from fractions import Fraction as F
from math import comb,factorial
from functools import lru_cache


class CorrectionWalk:
    def __init__(self,residents):
        if not isinstance(residents,int) or residents<3:raise ValueError('At least three residents required.')
        self.r=residents
    def probabilities(self,j):
        if not isinstance(j,int) or not 0<j<self.r:raise ValueError('Transient minority count required.')
        return F(self.r-j-1,self.r-2),F(j-1,self.r-2)
    def wrong_consensus(self,j):
        if not isinstance(j,int) or not 0<=j<=self.r:raise ValueError('Minority count outside resident total.')
        if j==0:return F(0)
        if j==self.r:return F(1)
        return F(sum(comb(self.r-3,a) for a in range(j-1)),2**(self.r-3))
    def absorption(self,j,fuel):
        if not isinstance(j,int) or not 0<=j<=self.r or not isinstance(fuel,int) or fuel<0:raise ValueError('Valid initial minority and finite fuel required.')
        active={j:F(1)};hits=[];progress=[]
        if j in [0,self.r]:hits=[(0,j,F(1))];active={}
        for k in range(1,fuel+1):
            nxt={}
            for state,p in active.items():
                for dst,q in zip([state-1,state+1],self.probabilities(state)):
                    if q==0:continue
                    if dst in [0,self.r]:hits.append((k,dst,p*q))
                    else:nxt[dst]=nxt.get(dst,F(0))+p*q
            active=nxt
            if sum(p for k,b,p in hits)+sum(active.values())!=1:raise ArithmeticError('Absorbed and transient masses do not sum to one.')
            progress.append((k,sum(p for kk,b,p in hits if b==0),sum(p for kk,b,p in hits if b==self.r),sum(active.values())))
            if not active:break
        moments={b:dict(mass=sum((p for k,endpoint,p in hits if endpoint==b),F(0)),spent=sum((k*p for k,endpoint,p in hits if endpoint==b),F(0))) for b in [0,self.r]}
        return dict(hits=hits,transient=active,moments=moments,progress=progress)


@dataclass(frozen=True)
class Regime:
    name:str
    fuel:int
    minority:int
    gamma_min:F
    beta_max:F
    epsilon_max:F
    prefix_duration:F
    imperfect:bool
    headline:F


REGIMES=(
    Regime('Original',1,1,F(10**9),F(1,10**12),F(1,10**9),F(1,10**9),False,F(4999,5000)),
    Regime('W',1,1,F(2*10**7),F(6,10**11),F(1,10**7),F(1,8*10**7),False,F(4999,5000)),
    Regime('O',1,1,F(10**8),F(1,10**11),F(1,10**8),F(1,4*10**8),True,F(4999,5000)),
    Regime('WO',1,1,F(2*10**7),F(6,10**11),F(1,10**7),F(1,8*10**7),True,F(9997,10000)),
    Regime('F',64,2,F(2*10**7),F(5,10**11),F(1,10**7),F(1,10**7),True,F(2479,2500)))


def positive_exponential_sum(x,degree):return sum((F(x)**k/factorial(k) for k in range(degree+1)),F(0))


def one_minority_bound(regime,core):
    if regime.fuel!=1 or regime.minority!=1:raise ValueError('One-minority certificate requires one fuel unit.')
    exponent=56*regime.gamma_min*regime.prefix_duration
    if positive_exponential_sum(exponent,18)<=10**6:raise ValueError('Declared one-millionth repair allowance is not certified.')
    rare=80*regime.epsilon_max+80**3*regime.beta_max
    prefix=max(2*r*(80-r)+F(r*(r-1),100) for r in range(8,81))
    if prefix+rare>=3216:raise ValueError('Suppressed-clock rate exceeds the prefix certificate.')
    losses=dict(repair=F(1,10**6),prefix=3216*regime.prefix_duration,departure=rare)
    bound=core-sum(losses.values());published=core-F(15,10**6) if regime.name=='Original' else bound
    return dict(lower=max(F(0),bound),published_lower=published,losses=losses,repair_exponent=exponent,prefix_polynomial_max=prefix,headline=regime.headline,passes=published>=regime.headline)


def finite_fuel_bound(core,absorption,endpoint,regime,deadline_failure=F(1,10**12)):
    moment=absorption['moments'][endpoint];v,s=moment['mass'],moment['spent']
    return (core-80*regime.epsilon_max)*v-80**3*regime.beta_max*s-3216*regime.prefix_duration-deadline_failure


def fuel_deadline(regime):
    if regime.fuel!=64 or regime.minority!=2:raise ValueError('This uniform restart-region deadline proof is specific to 64 fuel units and two minorities.')
    exponent=72*regime.gamma_min*regime.prefix_duration
    bound=positive_exponential_sum(exponent,63)/positive_exponential_sum(exponent,300)
    one_exponent=56*regime.gamma_min*regime.fuel*regime.prefix_duration
    one_bound=1/positive_exponential_sum(one_exponent,18)
    rare=80*regime.epsilon_max+regime.fuel*80**3*regime.beta_max
    prefix=max(2*r*(80-r)+F(r*(r-1),100) for r in range(8,81))
    if max(bound,one_bound)>=F(1,10**12) or prefix+rare>=3216:raise ValueError('Finite-fuel timing or suppressed-clock premise fails.')
    return dict(erlang_upper=bound,one_minority_upper=one_bound,exponent=exponent,suppressed_rate_upper=prefix+rare,used_allowance=F(1,10**12))


def selection_bound(q,cutoff=16,mothers_per_program=10):
    if not 0<=q<=1 or not isinstance(cutoff,int) or not 0<=cutoff<=2*mothers_per_program:raise ValueError('Invalid selection specification.')
    n=2*mothers_per_program;coin_failure=F(1+sum(comb(n,j) for j in range(cutoff+1,n+1)),2**n)
    return max(F(0),1-2*mothers_per_program*(1-q)-coin_failure)