A non-contestant's solution to t3

task3heap.py

def generate_moves(n):
    if n:
        for move in generate_moves(n-1):
            yield move
            if n-2 not in move: yield move|{n-1}
    else: yield frozenset()
def heuristic(permutation):
    displacements=tuple(abs(x-i) for i,x in enumerate(permutation))
    return max(displacements),sum(displacements)+1>>1
target=input("Target configuration: ")
if not target.isdigit(): raise RuntimeError("Configuration must consist of digits.")
nwires,current=len(target),tuple(map(int,target))
if set(current)!=set(range(nwires)): raise RuntimeError("Configuration must be a permutation.")
cwidth,ccount=heuristic(current)
considering=[(),(cwidth,ccount,current)]
closed,whichway,cost,index=set(),{},{current:(0,0)},{current:1}
while True:
    cwidth,ccount,current=considering[1]
    last=considering.pop()
    if len(considering)>1:
        newindex=1
        while True:
            left=2*newindex
            right=left+1
            if left>=len(considering): break
            elif right==len(considering):
                if last>considering[left]: successor=left
                else: break
            elif last>considering[left]<=considering[right]: successor=left
            elif last>considering[right]: successor=right
            else: break
            considering[newindex],index[considering[successor][2]],newindex=considering[successor],newindex,successor
        considering[newindex],index[last[2]]=last,newindex
    if not heuristic(current)[0]: break
    closed.add(current)
    cwidth,ccount=cost[current]
    twidth=cwidth+1
    for move in generate_moves(nwires-1):
        tcount=ccount+len(move)
        tentative=twidth,tcount
        neighbor=list(current)
        for i in move: neighbor[i:i+2]=neighbor[i+1],neighbor[i]
        neighbor=tuple(neighbor)
        if neighbor not in closed:
            newindex=index.get(neighbor)
            if not newindex or tentative<cost[neighbor]:
                if not newindex:
                    newindex=len(considering)
                    considering.append(None)
                whichway[neighbor],cost[neighbor]=move,tentative
                nwidth,ncount=heuristic(neighbor)
                insert=twidth+nwidth,tcount+ncount,neighbor
                while considering[newindex>>1]>insert:
                    successor=newindex>>1
                    considering[newindex],index[considering[successor][2]],newindex=considering[successor],newindex,successor
                considering[newindex],index[neighbor]=insert,newindex
current,solution=list(range(nwires)),[]
while tuple(current) in whichway:
    move=whichway[tuple(current)]
    solution.append(move)
    for i in move: current[i:i+2]=current[i+1],current[i]    
for row in range(nwires):
    if row:
        print(end="   ")
        for move in solution: print(end="\\/" if row-1 in move else "  ")
        print()
    print(row,end=" _")
    for move in solution: print(end="  " if row in move else "/\\" if row-1 in move else "__")
    print("_",target[row])