"""Independent implementation of the cyclic Newton-edge identity.
Uses polynomial dictionaries and integer exponent arithmetic, not SymPy differentiation.
"""
from fractions import Fraction
import hashlib,json,random
from pathlib import Path

def add(P,e,c):
 P[e]=P.get(e,Fraction(0))+c
 if not P[e]: del P[e]
def deriv(P,var):
 Q={}
 for (u,y),c in P.items():
  n=(u,y)[var]
  if n:
   e=(u-1,y) if var==0 else (u,y-1)
   add(Q,e,c*n)
 return Q
def mul(P,Q):
 R={}
 for (i,j),a in P.items():
  for (k,l),b in Q.items():add(R,(i+k,j+l),a*b)
 return R
def scale(P,c):return {e:c*a for e,a in P.items() if c*a}
def plus(*Ps):
 R={}
 for P in Ps:
  for e,c in P.items():add(R,e,c)
 return R
def ushift(P):return {(i+1,j):c for (i,j),c in P.items()}
def cyclic_D(H,g,m):
 return plus(scale(mul(ushift(deriv(H,0)),deriv(g,1)),m),
             scale(mul(deriv(H,1),plus(g,scale(ushift(deriv(g,0)),m))),-1))

def edge_poly(p,q,r,s,phi,A):
 # phi,A arrays low-to-high in t; expand t=u^q y^p.
 H={};g={}
 for n,c in enumerate(phi):add(H,(r+q*n,s+p*n),Fraction(c))
 for n,c in enumerate(A):add(g,(q*n,p*n),Fraction(c))
 return H,g

def expected_B(p,q,r,s,m,phi,A):
 sigma=Fraction(q*s-p*r,q)
 # t-polynomial dictionaries as exponent -> coefficient
 def td(P):return {i:Fraction(c) for i,c in enumerate(P) if c}
 def tder(P):return {i-1:Fraction(i)*c for i,c in P.items() if i}
 def tmul(P,Q):
  R={}
  for i,a in P.items():
   for j,b in Q.items():R[i+j]=R.get(i+j,Fraction(0))+a*b
  return {i:a for i,a in R.items() if a}
 def tshift(P):return {i+1:a for i,a in P.items()}
 AA,PP=td(A),td(phi)
 R={}
 terms=[(-p,tmul(tshift(tder(PP)),AA)),(-s,tmul(AA,PP)),(-m*q*sigma,tmul(tshift(tder(AA)),PP))]
 for z,P in terms:
  for i,a in P.items():R[i]=R.get(i,Fraction(0))+z*a
 return {i:a for i,a in R.items() if a}

rng=random.Random(731991)
checks=0
for m in range(1,9):
 for q in range(1,7):
  for p in range(0,7):
   import math
   if math.gcd(p,q)!=1:continue
   for r in range(q):
    for s in range(1,5):
     if q*s-p*r<=0:continue
     phi=[rng.randint(-4,4) for _ in range(rng.randint(1,5))];phi[-1]=rng.choice([1,2,3])
     A=[rng.choice([1,2,3])]+[rng.randint(-4,4) for _ in range(rng.randint(1,5))];A[-1]=rng.choice([1,2,3])
     H,g=edge_poly(p,q,r,s,phi,A)
     got=cyclic_D(H,g,m)
     B=expected_B(p,q,r,s,m,phi,A)
     want={}
     for n,c in B.items():add(want,(r+q*n,s-1+p*n),c)
     assert got==want,(m,p,q,r,s,got,want)
     N=len(phi)-1;D=len(A)-1;sigma=Fraction(q*s-p*r,q)
     top=-(p*N+s+m*q*sigma*D)*Fraction(phi[-1])*Fraction(A[-1])
     assert B.get(N+D)==top and top!=0
     checks+=1
cert={'status':'PASS','implementation':'independent polynomial dictionaries','random_edge_checks':checks,'seed':731991}
out=Path(__file__).with_name('independent_certificate.json');out.write_text(json.dumps(cert,indent=2)+'\n')
print(json.dumps(cert,indent=2));print('sha256',hashlib.sha256(out.read_bytes()).hexdigest())