"""Original exact alias construction and finite-world sampling proof."""
from fractions import Fraction as F
from collections import Counter
import json
def build(weights):
 if type(weights) is not list or not 1<=len(weights)<=8 or any(type(x) not in [int,F] or x<0 or x>100 for x in weights) or sum(weights)<=0:raise ValueError('1..8 exact nonnegative weights with positive total')
 n=len(weights);p=[F(x,sum(weights)) for x in weights];scaled=[x*n for x in p];small=[i for i,x in enumerate(scaled) if x<1];large=[i for i,x in enumerate(scaled) if x>=1];q=[F(1)]*n;alias=list(range(n));trace=[]
 while small and large:
  low=small.pop();high=large.pop();q[low]=scaled[low];alias[low]=high;old=scaled[high];scaled[high]-=1-scaled[low];trace.append({'under':low,'over':high,'q_under':str(q[low]),'over_before':str(old),'over_after':str(scaled[high])})
  (small if scaled[high]<1 else large).append(high)
 for i in small+large:q[i]=F(1);alias[i]=i
 mass=[F(0)]*n
 for i in range(n):mass[i]+=q[i]/n;mass[alias[i]]+=(1-q[i])/n
 assert mass==p
 return p,q,alias,trace
def choose(q,alias,index,coin):
 if type(index) is not int or not 0<=index<len(q) or type(coin) not in [int,F] or not 0<=coin<1:raise ValueError('valid bin and unit coin in[0,1)')
 return index if coin<q[index] else alias[index]
def demo():
 p,q,a,tr=build([1,2,3]);worlds=[];counts=Counter()
 for i in range(3):
  for c in [F(1,8),F(3,8),F(5,8),F(7,8)]:
   result=choose(q,a,i,c);counts[result]+=1;worlds.append({'uniform_bin':i,'uniform_midpoint_coin':str(c),'outcome':result})
 assert [F(counts[i],12) for i in range(3)]==p
 # Independent cumulative-distribution oracle over six equally likely tickets.
 cdf=[];total=F(0)
 for x in p:total+=x;cdf.append(total)
 tickets=[next(i for i,c in enumerate(cdf) if F(2*k+1,12)<c) for k in range(6)];assert [tickets.count(i) for i in range(3)]==[1,2,3]
 cases=[]
 for weights in [[0,1,0],[1],[1,1,1],[2,0,3,1]]:
  pp,qq,aa,tt=build(weights);cases.append({'weights':weights,'probabilities':[str(x) for x in pp],'q':[str(x) for x in qq],'alias':aa,'analytic_mass_equal':True})
 boundary={'q0':str(q[0]),'below':choose(q,a,0,F(49,100)),'equal':choose(q,a,0,F(1,2))};assert boundary['below']==0 and boundary['equal']==a[0]
 rejected=[]
 for weights in [[],[0,0],[-1,2],[True,1],[float('nan'),1],[1]*9]:
  try:build(weights)
  except ValueError:rejected.append(repr(weights))
  else:raise AssertionError('expected rejection')
 assert choose(q,a,0,0)==0
 try:choose(q,a,0,1)
 except ValueError:coin_one_rejected=True
 else:raise AssertionError('coin1 outside halfopen domain')
 newp,_,_,_=build([3,2,1]);assert newp!=p
 return {'weights':[1,2,3],'probabilities':[str(x) for x in p],'scaled_threshold_q':[str(x) for x in q],'alias_indices':a,'construction':tr,'all_twelve_equal_probability_worlds':worlds,'world_counts':dict(sorted(counts.items())),'independent_CDF_six_ticket_outcomes':tickets,'threshold_equal_uses_alias':boundary,'coin_zero_accepted':True,'coin_one_rejected':coin_one_rejected,'changed_weights_require_rebuild':{'new_weights':[3,2,1],'new_probabilities':[str(x) for x in newp],'old_table_still_represents_old_probabilities':[str(x) for x in p]},'additional_exact_tables':cases,'invalid_weights_rejected':rejected,'scope':'precomputed fixed weights with replacement; table rebuild for changed weights; no reservoir, MCMC, PRNG/security or product throughput claim'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))