"""Exact integer tests for the structured-DP unit; Python 3 standard library only.
Run: python foundation-structured-dp-capstone.py [output.json].
All optimization argmins use the smallest candidate index on ties.
"""
from collections import deque
from itertools import product,combinations
import json,pathlib,random,math,sys
OUT=pathlib.Path(sys.argv[1]) if len(sys.argv)>1 else pathlib.Path.cwd()/'foundation-structured-dp-capstone-results.json'
INF=math.inf

def edit_table(A,B):
 m,n=len(A),len(B);D=[[0]*(n+1) for _ in range(m+1)]
 for i in range(m+1):D[i][0]=i
 for j in range(n+1):D[0][j]=j
 for i in range(1,m+1):
  for j in range(1,n+1):D[i][j]=min(D[i-1][j]+1,D[i][j-1]+1,D[i-1][j-1]+(A[i-1]!=B[j-1]))
 i,j=m,n;ops=[]
 while i or j:
  if i and j and D[i][j]==D[i-1][j-1]+(A[i-1]!=B[j-1]):ops.append(('=' if A[i-1]==B[j-1] else 'S',A[i-1],B[j-1]));i-=1;j-=1
  elif i and D[i][j]==D[i-1][j]+1:ops.append(('D',A[i-1],''));i-=1
  else:ops.append(('I','',B[j-1]));j-=1
 return D,ops[::-1]

def apply_ops(A,ops):
 i=0;out=[];cost=0
 for op,a,b in ops:
  if op in('=','S','D'):assert i<len(A) and A[i]==a;i+=1
  if op in('=','S','I'):out.append(b)
  if op!='=':cost+=1
  if op=='=':assert a==b
 assert i==len(A)
 return ''.join(out),cost

def row_cost(A,a0,a1,B,b0,b1,reverse=False):
 # Integer index ranges avoid allocating sliced copies of input strings.
 n=b1-b0;prev=list(range(n+1));aa=range(a1-1,a0-1,-1) if reverse else range(a0,a1)
 for ii,i in enumerate(aa,1):
  row=[ii]+[0]*n
  for j in range(1,n+1):
   bj=b1-j if reverse else b0+j-1
   row[j]=min(prev[j]+1,row[j-1]+1,prev[j-1]+(A[i]!=B[bj]))
  prev=row
 return prev

def hirschberg(A,B,trace=False):
 swaps=False
 if len(B)>len(A):A,B=B,A;swaps=True
 events=[];ops=[];peakwidth=0;maxdepth=0;cells=0
 def rec(a0,a1,b0,b1,depth):
  nonlocal peakwidth,maxdepth,cells
  m,n=a1-a0,b1-b0;maxdepth=max(maxdepth,depth)
  if n==0:ops.extend(('D',A[i],'') for i in range(a0,a1));return
  if m==0:ops.extend(('I','',B[j]) for j in range(b0,b1));return
  if m==1:
   hit=next((j for j in range(b0,b1) if B[j]==A[a0]),None)
   j=b0 if hit is None else hit
   ops.extend(('I','',B[k]) for k in range(b0,j));ops.append(('S' if hit is None else '=',A[a0],B[j]));ops.extend(('I','',B[k]) for k in range(j+1,b1));return
  if n==1:
   hit=next((i for i in range(a0,a1) if A[i]==B[b0]),None)
   i=a0 if hit is None else hit
   ops.extend(('D',A[k],'') for k in range(a0,i));ops.append(('S' if hit is None else '=',A[i],B[b0]));ops.extend(('D',A[k],'') for k in range(i+1,a1));return
  mid=a0+m//2;fw=row_cost(A,a0,mid,B,b0,b1);rv=row_cost(A,mid,a1,B,b0,b1,True);cells+=m*n;peakwidth=max(peakwidth,3*(n+1));sums=[fw[j]+rv[n-j] for j in range(n+1)];j=min(range(n+1),key=lambda j:(sums[j],j))
  if trace:events.append({'A':[a0,a1],'B':[b0,b1],'middle':mid,'forward':fw,'reverse_indexed':[rv[n-j] for j in range(n+1)],'sum':sums,'split':b0+j})
  del fw,rv,sums
  rec(a0,mid,b0,b0+j,depth+1);rec(mid,a1,b0+j,b1,depth+1)
 rec(0,len(A),0,len(B),0)
 if swaps:ops=[({'D':'I','I':'D','=':'=','S':'S'}[op],b,a) for op,a,b in ops]
 return ops,events,{'DP_work_array_cells_bound_excluding_optional_trace':peakwidth,'max_recursion_depth':maxdepth,'DP_cells_computed_above_base':cells,'swapped_to_use_shorter_width':swaps}

def myers(A,B):
 m,n=len(A),len(B);N=m+n;V={1:0};history=[];choices=[];end=None;retired=set()
 for d in range(N+1):
  W={};C={}
  for k in range(-d,d+1,2):
   # Keep a newly reached boundary endpoint in V for its immediate outgoing step,
   # but never recompute that diagonal at a later, strictly larger edit cost.
   if k in retired:continue
   if d==0:x=0;pk=None;op=None
   else:
    candidates=[]
    if k-1 in V:
     px=V[k-1];py=px-(k-1)
     if px<m:candidates.append((px+1,1,k-1,'D'))
    if k+1 in V:
     px=V[k+1];py=px-(k+1)
     if py<n:candidates.append((px,0,k+1,'I'))
    if not candidates:continue
    x,_,pk,op=max(candidates) # furthest x; deletion wins a tie.
   y=x-k
   if not(0<=x<=m and 0<=y<=n):continue
   start=(x,y)
   while x<m and y<n and A[x]==B[y]:x+=1;y+=1
   if x==m or y==n:retired.add(k)
   W[k]=x;C[k]={'previous_diagonal':pk,'operation':op,'snake_start':start,'end':(x,y)}
   if x==m and y==n:end=(d,k);break
  history.append(W);choices.append(C);V=W
  if end:break
 assert end is not None
 d,k=end;parts=[]
 while d>=0:
  c=choices[d][k];x,y=c['end'];sx,sy=c['snake_start'];chunk=[('=',A[sx+i],B[sy+i]) for i in range(x-sx)]
  if c['operation']=='D':chunk=[('D',A[sx-1],'')]+chunk
  elif c['operation']=='I':chunk=[('I','',B[sy-1])]+chunk
  parts.append(chunk);k=c['previous_diagonal'];d-=1
 ops=[o for chunk in parts[::-1] for o in chunk]
 return end[0],ops,history,choices

def insertion_deletion_distance(A,B):
 m,n=len(A),len(B);D=[[0]*(n+1) for _ in range(m+1)]
 for i in range(m+1):D[i][0]=i
 for j in range(n+1):D[0][j]=j
 for i in range(1,m+1):
  for j in range(1,n+1):D[i][j]=min(D[i-1][j]+1,D[i][j-1]+1,D[i-1][j-1] if A[i-1]==B[j-1] else INF)
 return D[m][n]

def monge(A):return all(A[i][j]+A[k][l]<=A[i][l]+A[k][j] for i,k in combinations(range(len(A)),2) for j,l in combinations(range(len(A[0])),2))
def total_monotone(A):
 # Strict implication exactly matches smallest-column argmin convention.
 return all(not(A[i][j]>A[i][l]) or A[k][j]>A[k][l] for i,k in combinations(range(len(A)),2) for j,l in combinations(range(len(A[0])),2))
def minima(A):return[min(range(len(row)),key=lambda j:(row[j],j)) for row in A]

def smawk(rows,cols,value,history=None):
 if not rows:return {}
 assert cols
 reduced=[]
 for c in cols:
  while reduced:
   r=rows[len(reduced)-1]
   if value(r,c)<value(r,reduced[-1]):
    if history is not None:history.append({'event':'pop-column','row':r,'old':reduced[-1],'new':c,'rows':rows})
    reduced.pop()
   else:break
  if len(reduced)<len(rows):reduced.append(c)
  elif history is not None:history.append({'event':'discard-column','column':c,'rows':rows})
 if history is not None:history.append({'event':'reduced','rows':rows,'columns':reduced.copy()})
 ans=smawk(rows[1::2],reduced,value,history);positions={c:i for i,c in enumerate(reduced)};lo=0
 for i in range(0,len(rows),2):
  r=rows[i];hi=positions[ans[rows[i+1]]] if i+1<len(rows) else len(reduced)-1
  ans[r]=min(reduced[lo:hi+1],key=lambda c:(value(r,c),c))
  if history is not None:history.append({'event':'interpolate','row':r,'columns':reduced[lo:hi+1],'answer':ans[r]})
  if i+1<len(rows):lo=hi
 return ans

def prefixes(a):
 S=[0]
 for x in a:S.append(S[-1]+x)
 return S

def partition_dp(a,K,method='brute'):
 n=len(a);S=prefixes(a);table=[[0]+[INF]*n];args=[[None]*(n+1)];counts=[];events=[]
 for t in range(1,K+1):
  prev=table[-1];row=[INF]*(n+1);arg=[None]*(n+1);calls=0
  def val(j,k):
   nonlocal calls
   calls+=1
   return prev[k]+(S[j]-S[k])**2 if k<j else INF
  if method=='brute':
   for j in range(t,n+1):arg[j]=min(range(t-1,j),key=lambda k:(val(j,k),k));row[j]=val(j,arg[j])
  elif method=='divide':
   def solve(l,r,kl,kr):
    if l>r:return
    j=(l+r)//2;arg[j]=min(range(kl,min(kr,j-1)+1),key=lambda k:(val(j,k),k));row[j]=val(j,arg[j]);events.append({'layer':t,'rows':[l,r],'middle':j,'allowed':[kl,min(kr,j-1)],'choice':arg[j]})
    solve(l,j-1,kl,arg[j]);solve(j+1,r,arg[j],kr)
   solve(t,n,t-1,n-1)
  elif method=='smawk':
   aa=smawk(list(range(t,n+1)),list(range(t-1,n)),val)
   for j in range(t,n+1):arg[j]=aa[j];row[j]=val(j,arg[j])
  elif method=='cht':
   hull=MonotoneLines()
   for j in range(t,n+1):
    k=j-1
    if prev[k]<INF:hull.add((-2*S[k],prev[k]+S[k]*S[k],k))
    best,k=hull.query(S[j]);row[j]=S[j]*S[j]+best;arg[j]=k
   calls=hull.comparisons
  elif method=='lichao':
   tree=LiChao(sorted(set(S)))
   for j in range(t,n+1):
    k=j-1
    if prev[k]<INF:tree.add((-2*S[k],prev[k]+S[k]*S[k],k))
    best,k=tree.query(S[j]);row[j]=S[j]*S[j]+best;arg[j]=k
   calls=tree.comparisons
  else:raise ValueError(method)
  table.append(row);args.append(arg);counts.append(calls)
 cuts=[];j=n
 for t in range(K,0,-1):cuts.append(j);j=args[t][j]
 cuts.reverse();return table,args,cuts,counts,events

class MonotoneLines:
 def __init__(self,trace=False):self.Q=deque();self.history=[];self.comparisons=0;self.lastx=None;self.lastm=None;self.trace=trace
 def log(self,*event):
  if self.trace:self.history.append([list(x) if isinstance(x,deque) else x for x in event])
 def add(self,line):
  m,b,k=line
  if self.lastm is not None:assert m<=self.lastm
  self.lastm=m
  if self.Q and self.Q[-1][0]==m:
   old=self.Q[-1]
   if (old[1],old[2])<=(b,k):self.log('equal-slope-discard',line);return
   self.Q.pop();self.log('equal-slope-replace',old,line)
  while len(self.Q)>1:
   a,c=self.Q[-2],self.Q[-1];self.comparisons+=1
   if (c[1]-a[1])*(c[0]-m)>=(b-c[1])*(a[0]-c[0]):self.log('redundant',self.Q.pop(),line)
   else:break
  self.Q.append(line);self.log('insert',line,self.Q)
 def query(self,x):
  if self.lastx is not None:assert x>=self.lastx
  self.lastx=x
  if not self.Q:self.log('query-empty',x);return (INF,math.inf)
  def v(line):return(line[0]*x+line[1],line[2])
  while len(self.Q)>1:
   self.comparisons+=1
   if v(self.Q[1])<v(self.Q[0]):self.log('query-pop',x,self.Q.popleft())
   else:break
  self.log('query',x,self.Q[0]);return v(self.Q[0])

class LiChao:
 def __init__(self,xs,trace=False):
  assert xs and all(a<b for a,b in zip(xs,xs[1:]));self.xs=xs;self.tree={};self.comparisons=0;self.history=[];self.trace=trace
 def log(self,*event):
  if self.trace:self.history.append(event)
 def better(self,a,b,x):self.comparisons+=1;return(a[0]*x+a[1],a[2])<(b[0]*x+b[1],b[2])
 def add(self,line):
  def rec(node,l,r,new):
   if node not in self.tree:self.tree[node]=new;self.log('store',node,l,r,new);return
   mid=(l+r)//2;old=self.tree[node];left=self.better(new,old,self.xs[l]);middle=self.better(new,old,self.xs[mid])
   if middle:self.tree[node],new=new,old;self.log('swap-mid',node,l,r,self.tree[node],new)
   if r-l==1:return
   if left!=middle:rec(node*2,l,mid,new)
   else:rec(node*2+1,mid,r,new)
  rec(1,0,len(self.xs),line)
 def query(self,x):
  import bisect
  p=bisect.bisect_left(self.xs,x);assert p<len(self.xs) and self.xs[p]==x
  node=1;l=0;r=len(self.xs);best=(INF,math.inf);visited=[]
  while True:
   visited.append(node)
   if node in self.tree:
    m,b,k=self.tree[node];self.comparisons+=1;best=min(best,(m*x+b,k))
   if r-l==1:break
   mid=(l+r)//2
   if p<mid:node*=2;r=mid
   else:node=node*2+1;l=mid
  self.log('query',x,visited,best);return best

def optimal_bst(freq,optimized):
 n=len(freq);S=prefixes(freq);D=[[0]*(n+1) for _ in range(n+1)];R=[[None]*(n+1) for _ in range(n+1)];events=[];calls=0
 # Half-open intervals [i,j); root index i<=k<j.
 for length in range(1,n+1):
  for i in range(n-length+1):
   j=i+length
   lo=i if length==1 or not optimized else R[i][j-1]
   hi=j-1 if length==1 or not optimized else R[i+1][j]
   candidates=[]
   for k in range(lo,hi+1):candidates.append((D[i][k]+D[k+1][j]+S[j]-S[i],k));calls+=1
   D[i][j],R[i][j]=min(candidates);events.append({'interval':[i,j],'candidates':[lo,hi],'root':R[i][j],'cost':D[i][j]})
 return D,R,events,calls

def clean(x):
 if isinstance(x,float) and math.isinf(x):return 'inf'
 if isinstance(x,dict):return {str(k):clean(v) for k,v in x.items()}
 if isinstance(x,(list,tuple)):return [clean(v) for v in x]
 return x

def run():
 report={};D,ops=edit_table('CACTUS','CATCUS');assert apply_ops('CACTUS',ops)==('CATCUS',D[-1][-1]);hs,_,_=hirschberg('CACTUS','CATCUS');assert apply_ops('CACTUS',hs)==('CATCUS',2);report['edit']={'hirschberg_script_same_input':hs,'source':'CACTUS','target':'CATCUS','table':D,'script':ops,'distance':D[-1][-1]}
 A,B='CABACDA','ABCDA';ho,events,mem=hirschberg(A,B,trace=True);dd,_=edit_table(A,B);assert apply_ops(A,ho)==(B,dd[-1][-1]);report['hirschberg']={'source':A,'target':B,'script':ho,'distance':dd[-1][-1],'splits':events,'resources':mem}
 A,B='ABCDA','BACDEA';dist,mo,front,choice=myers(A,B);assert apply_ops(A,mo)==(B,dist);assert dist==3;report['myers']={'source':A,'target':B,'distance':dist,'script':mo,'frontiers':front,'choices':choice}
 X=[0,2,5];Y=[-1,1,4,6];M=[[(x-y)**2 for y in Y] for x in X];assert monge(M) and total_monotone(M)
 ordinary=[[0,3,1],[0,1,3]];notmonge=[[0,2],[1,4]];ties=[[0,0],[0,1]]
 assert minima(ordinary)==[0,0] and not total_monotone(ordinary);assert total_monotone(notmonge) and not monge(notmonge);assert total_monotone(ties)
 bd,bo,bf,_=myers('ab','baaa');assert 2 not in bf[2] and apply_ops('ab',bo)==('baaa',bd);report['myers_boundary_pruning']={'source':'ab','target':'baaa','frontiers':bf,'distance':bd,'omitted_reachable_point':[2,0],'reason':'A shorter exact-layer state exists but its completion costs two more edits than the retained boundary path.'}
 # These two inputs exposed repeated scans and retreating starts without retirement.
 retirement_checks=[]
 for A,B in [('abbaaa','bba'),('abbabb','bbaa'),('',''),('','AB'),('AB','')]:
  distance,script,front,choices=myers(A,B);assert distance==insertion_deletion_distance(A,B) and apply_ops(A,script)==(B,distance)
  prior={};retired=set();states=0
  for layer in choices:
   for k,event in layer.items():
    assert k not in retired
    start=event['snake_start'][0];end=event['end'][0]
    if k in prior:assert start>prior[k]
    prior[k]=end;states+=1
    if end==len(A) or end-k==len(B):retired.add(k)
  retirement_checks.append({'source':A,'target':B,'distance':distance,'retained_states':states,'disjoint_same_diagonal_scans':True})
 report['myers_retirement']=retirement_checks
 report['matrix_boundaries']={'monge_squared_distance':M,'ordinary_monotone_not_total':ordinary,'total_not_monge':notmonge,'leftmost_tie_counterexample_to_weak_implication':ties}
 centers=[0,2,3,5,6];bias=[0,1,0,2,-1,1,0];M=[[(x-y)**2+bias[y] for y in range(7)] for x in centers];hist=[];calls=0
 def get(i,j):
  nonlocal calls
  calls+=1;return M[i][j]
 ans=smawk(list(range(5)),list(range(7)),get,hist);assert[ans[i] for i in range(5)]==minima(M)
 report['smawk']={'matrix':M,'argmins':[ans[i] for i in range(5)],'oracle_calls':calls,'history':hist}
 a=[2,0,3,1,4,2,0,5,1,3,2,1];K=4;reference=partition_dp(a,K);methods={}
 for method in['brute','divide','smawk','cht','lichao']:
  table,arg,cuts,cnts,ev=partition_dp(a,K,method);assert table==reference[0] and arg==reference[1];methods[method]={'counts_by_layer':cnts,'count_unit':('oracle_calls' if method in ('brute','divide','smawk') else 'line_pair_or_redundancy_comparisons'),'cuts':cuts,'events':ev}
 assert reference[0][-1][-1]==144 and reference[2]==[4,6,9,12]
 report['capstone']={'workloads':a,'prefixes':prefixes(a),'layers':K,'table':reference[0],'argmins':reference[1],'optimum':144,'cuts':reference[2],'methods':methods}
 freq=[3,1,4,2];b0=optimal_bst(freq,False);b1=optimal_bst(freq,True);assert b0[:2]==b1[:2];report['knuth']={'frequencies':freq,'cost_table':b1[0],'roots':b1[1],'history':b1[2],'cubic_candidates':b0[3],'optimized_candidates':b1[3]}
 empty=MonotoneLines(trace=True);no_candidate=empty.query(0);assert no_candidate==(INF,math.inf)
 empty.add((2,3,0));after_insert=empty.query(0);assert after_insert==(3,0)
 empty.add((0,4,1));later=empty.query(2);assert later==(4,1)
 try:empty.query(1)
 except AssertionError:pass
 else:raise AssertionError('MonotoneLines accepted a decreasing query')
 report['cht_empty_queries']={'before_insertion':no_candidate,'after_insertion_at_same_x':after_insert,'after_next_insertion_at_larger_x':later,'decreasing_query_rejected':True,'history':empty.history}
 lineexample=MonotoneLines(trace=True)
 for line in[(4,0,0),(2,5,1),(0,6,2)]:lineexample.add(line)
 answers=[lineexample.query(x) for x in[-2,0,2,4]]
 report['cht']={'lines':[(4,0,0),(2,5,1),(0,6,2)],'queries':[-2,0,2,4],'answers':answers,'history':lineexample.history}
 tree=LiChao([-3,-1,0,2,5],trace=True);lines=[(2,3,0),(-1,1,1),(0,3,2)]
 for line in lines:tree.add(line)
 answers=[tree.query(x) for x in tree.xs];assert answers==[min((m*x+b,k) for m,b,k in lines) for x in tree.xs]
 report['li_chao']={'coordinates':tree.xs,'lines':lines,'answers':answers,'nodes':tree.tree,'history':tree.history}
 rng=random.Random(2077);checks={'string_pairs':0,'nonnegative_partition_instances':0,'nonnegative_BST_instances':0,'line_insert_query_checks':0,'exhaustive_2_by_3_totally_monotone':0,'monotone_line_query_checks':0}
 words=[''.join(t) for n in range(5) for t in product('AB',repeat=n)]
 for A in words:
  for B in words:
   tab,op=edit_table(A,B);hs,_,_=hirschberg(A,B);assert apply_ops(A,hs)==(B,tab[-1][-1]);dist,op,_,_=myers(A,B);assert apply_ops(A,op)==(B,dist) and dist==insertion_deletion_distance(A,B);checks['string_pairs']+=1
 for _ in range(120):
  n=rng.randrange(2,15);a=[rng.randrange(0,6) for _ in range(n)];K=rng.randrange(1,n+1);ref=partition_dp(a,K)
  for method in['divide','smawk','cht','lichao']:
   ans=partition_dp(a,K,method);assert ans[:2]==ref[:2],(a,K,method,ans[:2],ref[:2])
  for t in range(1,K+1):
   S=prefixes(a);prev=ref[0][t-1];mat=[[prev[k]+(S[j]-S[k])**2 if k<j else INF for k in range(t-1,n)] for j in range(t,n+1)];assert total_monotone(mat)
  checks['nonnegative_partition_instances']+=1
 for n in range(1,7):
  for freq in product(range(3),repeat=n):
   a=optimal_bst(freq,False);b=optimal_bst(freq,True);assert a[:2]==b[:2];checks['nonnegative_BST_instances']+=1
 for flat in product(range(3),repeat=6):
  mat=[list(flat[:3]),list(flat[3:])]
  if total_monotone(mat):
   ans=smawk([0,1],[0,1,2],lambda i,j:mat[i][j]);assert[ans[i] for i in range(2)]==minima(mat);checks['exhaustive_2_by_3_totally_monotone']+=1
 for _ in range(50):
  xs=sorted(set(rng.randrange(-20,21) for _ in range(15)));tr=LiChao(xs);ls=[]
  for k in range(20):
   line=(rng.randrange(-8,9),rng.randrange(-10,11),k);ls.append(line);tr.add(line)
   for x in xs:assert tr.query(x)==min((m*x+b,j) for m,b,j in ls);checks['line_insert_query_checks']+=1
 for _ in range(80):
  hu=MonotoneLines();ls=[];m=20;x=-15
  for k in range(25):
   m-=rng.randrange(0,3);line=(m,rng.randrange(-20,21),k);ls.append(line);hu.add(line);x+=rng.randrange(0,3)
   assert hu.query(x)==min((a*x+b,j) for a,b,j in ls);checks['monotone_line_query_checks']+=1
 hu=MonotoneLines()
 for line in [(3,0,0),(2,0,1),(1,0,2)]:hu.add(line)
 assert hu.query(0)==(0,0) and hu.query(1)==(1,2)
 dims=[2,3,2,10,1];mc=[[0]*4 for _ in range(4)];mr=[[None]*4 for _ in range(4)]
 for L in range(2,5):
  for i in range(5-L):
   j=i+L-1;mc[i][j],mr[i][j]=min((mc[i][k]+mc[k+1][j]+dims[i]*dims[k+1]*dims[j+1],k) for k in range(i,j))
 assert mr[0][2]==1 and mr[0][3]==0
 report['matrix_chain_boundary']={'dimensions':dims,'costs':mc,'split_after_zero_based_matrix':mr}
 negative=None
 for n in range(3,7):
  if negative:break
  for a in product(range(-2,3),repeat=n):
   ref=partition_dp(a,2);op=ref[1][2][2:]
   if any(x>y for x,y in zip(op,op[1:])):
    wrong=partition_dp(a,2,'divide');lc=partition_dp(a,2,'lichao');assert lc[:2]==ref[:2]
    if wrong[0]!=ref[0]:negative={'workloads':a,'prefixes':prefixes(a),'argmins':ref[1][2],'brute':ref[0][2],'invalid_divide_result':wrong[0][2],'li_chao_result':lc[0][2]};break
 assert negative is not None;report['negative_workload_counterexample']=negative;report['cross_checks']=checks
 OUT.parent.mkdir(parents=True,exist_ok=True);OUT.write_text(json.dumps(clean(report),ensure_ascii=False,indent=2)+'\n');print(json.dumps(clean({'edit_distance':D[-1][-1],'hirschberg':mem,'myers':report['myers']['frontiers'],'smawk':report['smawk']['argmins'],'capstone_cuts':reference[2],'capstone_optimum':144,'knuth_cost':b1[0][0][4],'negative':negative,'checks':checks}),ensure_ascii=False,indent=2))
if __name__=='__main__':run()