Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def move(P):
    for i in range(4):
        for j in range(4):
            if P[i][j] == 0:
                r,c = i,j
    if not r == 0:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        yield tmp
    if not r == 3:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        yield tmp
    if not c == 0:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        yield tmp
    if not c == 3:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        yield tmp

def dpkey(P):
    tmp = ""
    for i in P:
        for j in i:
            tmp += str(j) + " "
    return tmp

A = [[int(i) for i in input().split()] for _ in range(4)]
dp = {dpkey(A) : 1}
d = deque([(A,0)])
c = 0
flag = True
while(flag):
    tmp,c = d.pop()
    for i in move(tmp):
        key = dpkey(i)
        if key == "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ":
            ans = c + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,c+1))
if dpkey(A) == "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def move(P):
    for i in range(4):
        for j in range(4):
            if P[i][j] == 0:
                r,c = i,j
    if not r == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        yield tmp
    if not r == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        yield tmp
    if not c == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        yield tmp
    if not c == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        yield tmp

def dpkey(P):
    tmp = ""
    for i in P:
        for j in i:
            tmp += str(j) + " "
    return tmp
 
A = [[int(i) for i in input().split()] for _ in range(4)]
dp = {dpkey(A) : 1}
d = deque([(A,0)])
c = 0
flag = True
while(flag):
    tmp,c = d.pop()
    for i in move(tmp):
        key = dpkey(i)
        if key == "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ":
            ans = c + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,c+1))
if dpkey(A) == "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import deque
def move(P):
    for i in range(4):
        for j in range(4):
            if P[i][j] == 0:
                r,c = i,j
    if not r == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        yield tmp
    if not r == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        yield tmp
    if not c == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        yield tmp
    if not c == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        yield tmp

A = [[int(i) for i in input().split()] for _ in range(4)]
dp = {dpkey(A) : 1}
d = deque([(A,0)])
c = 0
flag = True
while(flag):
    tmp,c = d.pop()
    for i in move(tmp):
        key = str(i)
        if key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = c + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,c+1))
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import deque
def move(P):
    for i in range(4):
        for j in range(4):
            if P[i][j] == 0:
                r,c = i,j
    if not r == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        yield tmp
    if not r == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        yield tmp
    if not c == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        yield tmp
    if not c == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        yield tmp

A = [[int(i) for i in input().split()] for _ in range(4)]
dp = {dpkey(A) : 1}
d = deque([(A,0)])
c = 0
flag = True
while(flag):
    tmp,c = d.pop()
    for i in move(tmp):
        key = str(i)
        if key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = c + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,c+1))
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def move(P):
    for i in range(4):
        for j in range(4):
            if P[i][j] == 0:
                r,c = i,j
    if not r == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        yield tmp
    if not r == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        yield tmp
    if not c == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        yield tmp
    if not c == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        yield tmp

A = [[int(i) for i in input().split()] for _ in range(4)]
dp = {str(A) : 1}
d = deque([(A,0)])
c = 0
flag = True
while(flag):
    tmp,c = d.pop()
    for i in move(tmp):
        key = str(i)
        if key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = c + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,c+1))
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def move(P,r,c):
    if not r == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        tmpr = r - 1
        yield tmp,tmpr,c
    if not r == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        tmpr = r + 1
        yield tmp,tmpr,c
    if not c == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        tmpc = c - 1
        yield tmp,r,tmpc
    if not c == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        tmpc = c + 1
        yield tmp,r,tmpc

A = [[int(i) for i in input().split()] for _ in range(4)]
for i in range(4):
        for j in range(4):
            if A[i][j] == 0:
                r,c = i,j
dp = {str(A) : 1}
d = deque([(A,0,r,c)])
flag = True
while(flag):
    tmp,count,r,c = d.pop()
    for i,j,k in move(tmp,r,c):
        key = str(i)
        if key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = count + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,count+1,j,k))
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def move(P,r,c):
    global dp
    if not r == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        if not str(tmp) in dp:
            tmpr = r - 1
            yield tmp,tmpr,c
    if not r == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        if not str(tmp) in dp:
            tmpr = r + 1
            yield tmp,tmpr,c
    if not c == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        if not str(tmp) in dp:
            tmpc = c - 1
            yield tmp,r,tmpc
    if not c == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        if not str(tmp) in dp:
            tmpc = c + 1
            yield tmp,r,tmpc

A = [[int(i) for i in input().split()] for _ in range(4)]
for i in range(4):
        for j in range(4):
            if A[i][j] == 0:
                r,c = i,j
dp = {str(A) : 1}
d = deque([(A,0,r,c)])
while(True):
    tmp,count,r,c = d.pop()
    if str(tmp) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
        ans = count
        break
    for i,j,k in move(tmp,r,c):
        dp[str(i)] = 1
        d.appendleft((i,count+1,j,k))
        
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def move(P,r,c):
    if r > 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        tmpr = r - 1
        yield tmp,tmpr,c
    if r < 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        tmpr = r + 1
        yield tmp,tmpr,c
    if c > 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        tmpc = c - 1
        yield tmp,r,tmpc
    if c < 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        tmpc = c + 1
        yield tmp,r,tmpc

A = [[int(i) for i in input().split()] for _ in range(4)]
for i in range(4):
        for j in range(4):
            if A[i][j] == 0:
                r,c = i,j
dp = {str(A) : 1}
d = deque([(A,0,r,c)])
flag = True
while(flag):
    tmp,count,r,c = d.pop()
    for i,j,k in move(tmp,r,c):
        key = str(i)
        if key in dp:
            continue
        elif key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            d.appendleft((i,count+1,j,k))
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import copy
def move(P,r,c):
    if r > 0:
        tmp = copy.deepcopy(P)
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        tmpr = r - 1
        yield tmp,tmpr,c
    if r < 3:
        tmp = copy.deepcopy(P)
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        tmpr = r + 1
        yield tmp,tmpr,c
    if c > 0:
        tmp = copy.deepcopy(P)
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        tmpc = c - 1
        yield tmp,r,tmpc
    if c < 3:
        tmp = copy.deepcopy(P)
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        tmpc = c + 1
        yield tmp,r,tmpc

A = [[int(i) for i in input().split()] for _ in range(4)]
for i in range(4):
        for j in range(4):
            if A[i][j] == 0:
                r,c = i,j
dp = {str(A) : 1}
d = deque([(A,0,r,c)])
flag = True
while(flag):
    tmp,count,r,c = d.pop()
    for i,j,k in move(tmp,r,c):
        key = str(i)
        if key in dp:
            continue
        elif key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            d.appendleft((i,count+1,j,k))
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def move(P,r,c):
    if r > 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        tmpr = r - 1
        yield tmp,tmpr,c
    if r < 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        tmpr = r + 1
        yield tmp,tmpr,c
    if c > 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        tmpc = c - 1
        yield tmp,r,tmpc
    if c < 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        tmpc = c + 1
        yield tmp,r,tmpc

A = [[int(i) for i in input().split()] for _ in range(4)]
for i in range(4):
        for j in range(4):
            if A[i][j] == 0:
                r,c = i,j
dp = {str(A) : 1}
d = deque([(A,0,r,c)])
flag = True
t = 0
while(flag):
    tmp,count,r,c = d.pop()
    for i,j,k in move(tmp,r,c):
        key = str(i)
        if key in dp:
            continue
        elif key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            d.appendleft((i,count+1,j,k))
            t+=1
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
d = deque([(A,0,A.index(0))])
flag = True
while(flag):
    tmp,count,p = d.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            d.appendleft((i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
ans = 46
while(len(h)>0):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            if count+1<ans:
                ans = count + 1
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+1 < ans:
                heapq.heappush(h,(mht,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
ans = 46
while(len(h)>0):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            if count+1<ans:
                ans = count + 1
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+1 < ans:
                heapq.heappush(h,(mht+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
ans = 46
while(len(h)>0):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            if count+1<ans:
                ans = count + 1
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
ans = 46
while(len(h)>0):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            if count+1<ans:
                ans = count + 1
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
ans = 46
while(len(h)>0):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            if count+1<ans:
                ans = count + 1
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht*2+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(i)
            heapq.heappush(h,(mht+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(i)
            heapq.heappush(h,(mht+count*2,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < 46:
                heapq.heappush(h,(mht+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
d = deque([(A,0,A.index(0))])
e = deque([(B,0,15)])
flag = True
while(flag):
    tmp,count,p = d.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
            else:
                continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = (1,count+1)
            d.appendleft((i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
            else:
                continue
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
d = deque([(A,0,A.index(0))])
e = deque([(B,0,15)])
flag = True
while(flag):
    tmp,count,p = d.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
            else:
                continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = (1,count+1)
            d.appendleft((i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
            else:
                continue
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
ans = 46
while(len(h)>0):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            if count+1<ans:
                ans = count + 1
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(len(h)>0):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(len(h)>0):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = dp[key][1] + count + 1
                break
            else:
                continue
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(len(h)>0 and flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import deque
def move(P):

    if not r == 0:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        yield tmp
    if not r == 3:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        yield tmp
    if not c == 0:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        yield tmp
    if not c == 3:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        yield tmp

def check(A):
    for i,j in enumerate(A):
        for k,l in A:
            if not i*4+k == l:
                return False
    return True
        
A = [[int(i) for i in input().split()] for _ in range(4)]
for i in range(4):
    for j in range(4):
        if P[i][j] == 0:
            r,c = i,j
dp = {"" : 1}
d = deque([(A,0,"",(r,c))])
c = 0
flag = True
while(flag):
    tmp,c = d.pop()
    for i in move(tmp):
        key = dpkey(i)
        if key == "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ":
            ans = c + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,c+1))
if dpkey(A) == "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def move(P,r,c):
    if r > 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        tmpr = r - 1
        yield tmp,tmpr,c
    if r < 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        tmpr = r + 1
        yield tmp,tmpr,c
    if c > 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        tmpc = c - 1
        yield tmp,r,tmpc
    if c < 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        tmpc = c + 1
        yield tmp,r,tmpc

A = [[int(i) for i in input().split()] for _ in range(4)]
for i in range(4):
        for j in range(4):
            if A[i][j] == 0:
                r,c = i,j
dp = {str(A) : 1}
d = deque([(A,0,r,c)])
flag = True
t = 0
while(flag):
    tmp,count,r,c = d.pop()
    for i,j,k in move(tmp,r,c):
        key = str(i)
        if key in dp:
            continue
        elif key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            d.appendleft((i,count+1,j,k))
            t+=1
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
d = deque([(A,0,A.index(0))])
flag = True
while(flag):
    tmp,count,p = d.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            if count < 45:
                d.appendleft((i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < 46:
                heapq.heappush(h,(mht+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
ans = 46
while(len(h)>0):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            if count+1<ans:
                ans = count + 1
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Runtime Error):
#双方向　両方 deque
from collections import deque

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1,str(B) : 2}
d = deque([(A,0,A.index(0))])
e = deque([(B,0,15)])
flag = True
while(flag):
    tmp,count,p = d.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
            else:
                continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = (1,count+1)
            d.appendleft((i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
            else:
                continue
        else:
            dp[key] == (2,count+1)
            e.appendleft((i,countL+))
            
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
d = deque([(A,0,A.index(0))])
e = deque([(B,0,15)])
flag = True
while(flag):
    tmp,count,p = d.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
            else:
                continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = (1,count+1)
            d.appendleft((i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
            else:
                continue
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))
            
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(len(h)>0 and flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(len(h)>0 and flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
ans = 46
while(len(h)>0 and len(e)>0):
    _,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht//2 < ans:
                heapq.heappush(e,(mht+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][2]
                flag = False
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(len(h)>0 and flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
#A = []
B = [int(i)%16 for i in range(1,17)]
#for i in range(4):
#        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht+count*5,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht+count*5,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (2,count+1)
            e.appendleft((i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht

A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
d = deque([(A,0,A.index(0))])
e = deque([(B,0,15)])
flag = True
while(flag):
    tmp,count,p = d.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
            else:
                continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            if evaluate(B,i) + count < 46:
                dp[key] = (1,count+1)
                d.appendleft((i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
            else:
                continue
        else:
            if evaluate(A,i) + count < 46:
                dp[key] = (2,count+1)
                e.appendleft((i,count+1,j))
            
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht

A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
d = deque([(A,0,A.index(0))])
e = deque([(B,0,15)])
flag = True
while(flag):
    tmp,count,p = d.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
#        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
#            ans = count + 1
#            flag = False
        else:
            if evaluate(B,i) + count < 46:
                dp[key] = (1,count+1)
                d.appendleft((i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            if evaluate(A,i) + count < 46:
                dp[key] = (2,count+1)
                e.appendleft((i,count+1,j))
            
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht

A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
d = deque([(A,0,A.index(0))])
e = deque([(B,0,15)])
ans = 46
while(len(d)>0 and len(e)>0):
    tmp,count,p = d.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpans = count + 1 + dp[key][1]
                if tmpans < ans:
                    ans = tmpans
        else:
            if evaluate(B,i)//2 + count < ans:
                dp[key] = (1,count+1)
                d.append((i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpans = count + 1 + dp[key][1]
                if tmpans < ans:
                    ans = tmpans
        else:
            if evaluate(A,i)//2 + count < 46:
                dp[key] = (2,count+1)
                e.append((i,count+1,j))
            
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < 46:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < 46:
                heapq.heappush(h,(mht+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < 46:
                heapq.heappush(h,(mht*7//6+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < 46:
                heapq.heappush(h,(mht*16//15+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
flag = True
sw = False
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < 46:
                heapq.heappush(h,(mht+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
flag = True
sw = False
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht < 46:
                heapq.heappush(h,(mht+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht//2 < ans:
                heapq.heappush(e,(mht+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A,B),A,0,A.index(0))]
heapq.heapify(h)
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(B,i)
            if count+mht*14//13 < 46:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)


Fixed submission:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)