Problem:


7 パズル

7 パズルは 8 つの正方形のカードとこれらのカードがぴたりと収まる枠で構成されています。それぞれのカードには、互いに区別できるように 0, 1, 2, ..., 7 と番号がつけられています。枠には、縦に 2 個、横に 4 個のカードを並べることができます。

7 パズルを始めるときには、まず枠にすべてのカードを入れます。枠のなかで 0 のカードだけは、上下左右に隣接するカードと位置を交換することができます。たとえば、枠の状態が図(a) のときに、0 のカードの右に隣接した、7 のカードと位置を交換すれば、図(b) の状態になります。あるいは、図(a) の状態から 0 のカードの下に隣接した 2 のカードと位置を交換すれば図(c) の状態になります。図(a) の状態で 0 のカードと上下左右に隣接するカードは 7 と 2 のカードだけなので、これ以外の位置の入れ替えは許されません。

ゲームの目的は、カードをきれいに整列して図(d) の状態にすることです。最初の状態を入力とし、カードをきれいに整列するまでに、必要な最小手数を出力するプログラムを作成してください。ただし、入力されたカードの状態からは図(d) の状態に移ることは可能であるとします。

   入力データは、1 行に 8 つの数字が空白区切りで与えられます。これらは、最初の状態のカードの並びを表します。例えば、図(a) の数字表現は0 7 3 4 2 5 1 6 に、図(c) は 2 7 3 4 0 5 1 6 となります。

図(a) 0 7 3 4 2 5 1 6 の場合
図(b) 7 0 3 4 2 5 1 6 の場合

図(c) 2 7 3 4 0 5 1 6 の場合
図(d) 0 1 2 3 4 5 6 7 (最終状態)

Input

上記形式で複数のパズルが与えられます。入力の最後まで処理してください。
与えられるパズルの数は 1,000 以下です。

Output

各パズルについて、最終状態へ移行する最小手数を１行に出力してください。

Sample Input

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0

Output for the Sample Input

0
1
28



Sample input:
0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


Sample output:
0
1
28

Submission status: Accepted

Solution code:
from __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input

X=4
Y=2
i=0
m={}
prev={}
v=[]
for i in range(X*Y): v.append(str(i))
m[''.join(v)]=[0,0]
prev[''.join(v)]=[''.join(v),None]
q=[v]
while len(q)>0:
    v=q.pop(0)
    coor=m[''.join(v)][0]
    x=coor%X
    y=coor//X
    depth=m[''.join(v)][1]
    nextstr=''.join(v)
    if 0<x:
        v[coor],v[coor-1]=v[coor-1],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor-1,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'R']
        v[coor],v[coor-1]=v[coor-1],v[coor]
    if x<X-1:
        v[coor],v[coor+1]=v[coor+1],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor+1,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'L']
        v[coor],v[coor+1]=v[coor+1],v[coor]
    if 0<y:
        v[coor],v[coor-X]=v[coor-X],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor-X,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'D']
        v[coor],v[coor-X]=v[coor-X],v[coor]
    if y<Y-1:
        v[coor],v[coor+X]=v[coor+X],v[coor]
        if ''.join(v) not in m:
            m[''.join(v)]=[coor+X,depth+1]
            q.append(v[:])
            prev[''.join(v)]=[nextstr,'U']
        v[coor],v[coor+X]=v[coor+X],v[coor]

try:
    while True:
        v=raw_input().split()
        print(m[''.join(v)][1])
except EOFError:
    pass

Submission status: Accepted

Solution code:
from __future__ import division
import sys
if sys.version_info[0]>=3: raw_input=input

X=4
Y=2
i=0
m={}
prev={}
v=[]
for i in range(X*Y): v.append(str(i))
m[''.join(v)]=[0,0]
prev[''.join(v)]=[''.join(v),None]
q=[v]
while len(q)>0:
	v=q.pop(0)
	coor=m[''.join(v)][0]
	x=coor%X
	y=coor//X
	depth=m[''.join(v)][1]
	nextstr=''.join(v)
	if 0<x:
		v[coor],v[coor-1]=v[coor-1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-1,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'R']
		v[coor],v[coor-1]=v[coor-1],v[coor]
	if x<X-1:
		v[coor],v[coor+1]=v[coor+1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+1,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'L']
		v[coor],v[coor+1]=v[coor+1],v[coor]
	if 0<y:
		v[coor],v[coor-X]=v[coor-X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-X,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'D']
		v[coor],v[coor-X]=v[coor-X],v[coor]
	if y<Y-1:
		v[coor],v[coor+X]=v[coor+X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+X,depth+1]
			q.append(v[:])
			prev[''.join(v)]=[nextstr,'U']
		v[coor],v[coor+X]=v[coor+X],v[coor]

try:
	while True:
		v=raw_input().split()
		print(m[''.join(v)][1])
except EOFError:
	pass

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

def to_key(A):
    return ''.join(map(str, A))

def register(A, cnt, i, j):
    B = A[:]
    B[i], B[j] = B[j], B[i]
    key = to_key(B)
    if key not in M:
        Q.append((B, cnt + 1))

# prepare
A = [0, 1, 2, 3, 4, 5, 6, 7]
M = {}
Q = [(A, 0)]

while Q:
    A, cnt = Q.pop(0)
    key = to_key(A)
    M[key] = cnt

    idx = A.index(0)
    if idx == 0:
        register(A, cnt, idx, 1)
        register(A, cnt, idx, 4)
    elif idx == 1:
        register(A, cnt, idx, 0)
        register(A, cnt, idx, 2)
        register(A, cnt, idx, 5)
    elif idx == 2:
        register(A, cnt, idx, 1)
        register(A, cnt, idx, 3)
        register(A, cnt, idx, 6)
    elif idx == 3:
        register(A, cnt, idx, 2)
        register(A, cnt, idx, 7)
    elif idx == 4:
        register(A, cnt, idx, 0)
        register(A, cnt, idx, 5)
    elif idx == 5:
        register(A, cnt, idx, 1)
        register(A, cnt, idx, 4)
        register(A, cnt, idx, 6)
    elif idx == 6:
        register(A, cnt, idx, 2)
        register(A, cnt, idx, 5)
        register(A, cnt, idx, 7)
    elif idx == 7:
        register(A, cnt, idx, 3)
        register(A, cnt, idx, 6)


for s in sys.stdin:
    A = list(map(int, s.split()))
    key = to_key(A)
    print(M[key])

Submission status: Accepted

Solution code:
results = {"01234567": 0}


def main():
    while True:
        try:
            tmp = input().replace(' ', '')
            print(results[tmp])
        except EOFError:
            break


def swap(field, a, b):
    tmp = list(field)
    tmp[b], tmp[a] = tmp[a], tmp[b]
    return "".join(tmp)


def convert_matrix_index(index):
    return index % 4, int(index / 4)


def convert_array_index(x, y):
    return x + y * 4


def bfs(results):
    q = [["01234567", 0]]

    while len(q) is not 0:
        field, res = q.pop(0)
        x, y = convert_matrix_index(field.find('0'))
        for dx, dy in zip([0, 0, -1, 1], [1, -1, 0, 0]):
            nx = x + dx
            ny = y + dy
            if nx < 0 or ny < 0 or nx >= 4 or ny >= 2:
                continue

            next_field = swap(field, convert_array_index(x, y), convert_array_index(nx, ny))
            if next_field not in results:
                results[next_field] = res + 1
                q.append([next_field, res + 1])

    return results


if __name__ == '__main__':
    results = bfs(results)
    main()

Submission status: Accepted

Solution code:
from collections import deque
import copy

swap = [[1, 4], [0, 2, 5], [1, 3, 6], [2, 7], [0, 5], [1, 4, 6], [2, 5, 7], [3, 6]]


def bfs():
    ia = list(range(8))
    count = {str(ia): 0}
    que = deque()
    que.append((ia, 0))
    while len(que) != 0:
        state, cnt = que.popleft()
        # pos:0?????????
        pos = state.index(0)
        swap_target = swap[pos]
        for i in swap_target:
            tmp_state = copy.copy(state)
            tmp_state[i], tmp_state[pos] = tmp_state[pos], tmp_state[i]
            if str(tmp_state) not in count:
                count[str(tmp_state)] = cnt + 1
                que.append((tmp_state, cnt + 1))
    return count


if __name__ == '__main__':
    count = bfs()
    while True:
        try:
            prob = list(map(int, input().split()))
            print(count[str(prob)])
        except:
            break

Submission status: Accepted

Solution code:
import bisect as bs

def fun(f,i,sw):
    ret=[]
    for s in sw:
        ii,ss=min(i,s),max(i,s)
        ret.append( f[:ii]+f[ss]+f[ii+1:ss]+f[ii]+f[ss+1:])
    return ret

def exist(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bs.bisect_left(a, x)
    try:
        if i != len(a) and a[i] == x:
            return 1
    except:
        return 0

swaplist=[[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[4,6,1],[5,7,2],[6,3]]
A={}
A[1234567]=0
ks=[1234567]
F=["01234567"]
n=0
while len(F)!=0:
    NF=[]
    n+=1
    for f in F:
        i=f.index('0')
        sw=swaplist[i]
        for g in fun(f,i,sw):
            ig=int(g)
            if not exist(ks,ig):
                A[ig]=n
                bs.insort(ks,ig)
                NF.append(g)
    F=NF[:]
while(1):
    try:
        print A[int("".join(raw_input().split()))]
    except:
        break

Submission status: Accepted

Solution code:
from collections import deque

dic = {}
dic[(0,1,2,3,4,5,6,7)] = 0


swap_dic = {0:(1, 4), 1:(0, 2, 5), 2:(1, 3, 6), 3:(2, 7),
            4:(0, 5), 5:(1, 4, 6), 6:(2, 5, 7), 7:(3, 6)}

def swap(puz, i, j):
  new = [k for k in puz]
  new[i], new[j] = new[j], new[i]
  return tuple(new)

que = deque()
que.append((0, (0,1,2,3,4,5,6,7)))
while que:
  score, puz = que.popleft()
  score += 1
  z_ind = puz.index(0)

  for swap_ind in swap_dic[z_ind]:
    new_puz = swap(puz, z_ind, swap_ind)
    if not new_puz in dic:
      dic[new_puz] = score
      que.append((score, new_puz))

while True:
  try:
    print(dic[tuple(map(int, input().split()))])
  except EOFError:
    break

Submission status: Accepted

Solution code:
# AOJ 0121 Seven Puzzle 
# Python 2017.6.23 bal4u

def swap(state, x, y):
	s = list(copy.deepcopy(state))
	s[x], s[y] = s[y], s[x]
	return tuple(s)
	
from collections import deque
import copy
MAGIC = 37
move = ((1,4), (0,2,5), (1,3,6), (2,7), (0,5), (1,4,6), (2,5,7), (3,6))

Q = deque()
Q.append(((0,1,2,3,4,5,6,7), 0))
hash = {}
hash[(0,1,2,3,4,5,6,7)] = 0
while Q:
	state, x = Q.popleft()
	step = hash[state]+1
	if step > MAGIC: continue
	for y in move[x]:
		nstate = swap(state, x, y)
		if nstate not in hash: nstep = 100
		else: nstep = hash[nstate]
		if step < nstep:
			Q.append((nstate, y))
			hash[nstate] = step

while 1:
	try: state = tuple(map(int, input().split()))
	except: break
	print(hash[state])

Submission status: Accepted

Solution code:
# AOJ 0121 Seven Puzzle 
# Python 2017.6.23 bal4u

def swap(state, x, y):
	s = list(state)
	s[x], s[y] = s[y], s[x]
	return tuple(s)
	
from collections import deque
MAGIC = 37
move = ((1,4), (0,2,5), (1,3,6), (2,7), (0,5), (1,4,6), (2,5,7), (3,6))

Q = deque()
Q.append(((0,1,2,3,4,5,6,7), 0))
hash = {}
hash[(0,1,2,3,4,5,6,7)] = 0
while Q:
	state, x = Q.popleft()
	step = hash[state]+1
	if step > MAGIC: continue
	for y in move[x]:
		nstate = swap(state, x, y)
		if nstate not in hash: nstep = 100
		else: nstep = hash[nstate]
		if step < nstep:
			Q.append((nstate, y))
			hash[nstate] = step

while 1:
	try: state = tuple(map(int, input().split()))
	except: break
	print(hash[state])

Submission status: Accepted

Solution code:
from collections import defaultdict
d=(1,-1,4,-4)

def solve():
    que=["01234567"]
    while que!=[]:
        v=que[0]
        del que[0]
        pos=v.index("0")
        for i in range(4):
            idx2=pos+d[i]
            if idx2<0 or idx2>7:
                continue
            if (pos==3 and d[i]==1) or (pos==4 and d[i]==-1):
                continue
            u=list(v)
            u[pos],u[pos+d[i]]=u[pos+d[i]],u[pos]
            u="".join(u)
            if res[u]==0:
                que.append(u)
                res[u]=res[v]+1
res=defaultdict(int)
res["01234567"]=1
solve()
while True:
    try:
        s=raw_input().split()
    except EOFError:
        break
    s="".join(s)
    print res[s]-1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#与えられるパズルの数は1000以下です
from heapq import heappush,heappop
MOVE = [[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[1,4,6],[2,5,7],[3,6]]
ans = {"01234567":0}
def swap(field,a,b):
    tmp = list(field)
    tmp[a],tmp[b] = tmp[b],tmp[a]
    return "".join(tmp)

def BFS():
    global ans
    q = [[0,"01234567"]]
    while len(q) != 0:
        g, field = q.pop(0)
        a = field.find("0")
        for b in MOVE[a]:
            tmp = swap(field,a,b)
            if not tmp in ans:
                ans[tmp] = g+1
                q.append([g+1,tmp])

BFS()
while True:
    try:
        print ans[raw_input().replace(" ","")]
    except:
        break

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#与えられるパズルの数は1000以下です
MOVE = [[1,4],[0,2,5],[1,3,6],[2,7],[0,5],[1,4,6],[2,5,7],[3,6]]
ans = {"01234567":0}
def swap(field,a,b):
    tmp = list(field)
    tmp[a],tmp[b] = tmp[b],tmp[a]
    return "".join(tmp)

def BFS():
    global ans
    q = [[0,"01234567"]]
    while len(q) != 0:
        g, field = q.pop(0)
        a = field.find("0")
        for b in MOVE[a]:
            tmp = swap(field,a,b)
            if not tmp in ans:
                ans[tmp] = g+1
                q.append([g+1,tmp])

BFS()
while True:
    try:
        print ans[raw_input().replace(" ","")]
    except:
        break

Submission status: Accepted

Solution code:
X=4
Y=2
i=0
m={}
v=[]
for i in range(X*Y): v.append(str(i))
m[''.join(v)]=[0,0]
q=[v]
while len(q)>0:
	v=q.pop(0)
	coor=m[''.join(v)][0]
	x=coor%X
	y=coor/X
	depth=m[''.join(v)][1]
	if 0<x:
		v[coor],v[coor-1]=v[coor-1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-1,depth+1]
			q.append(v[:])
		v[coor],v[coor-1]=v[coor-1],v[coor]
	if x<X-1:
		v[coor],v[coor+1]=v[coor+1],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+1,depth+1]
			q.append(v[:])
		v[coor],v[coor+1]=v[coor+1],v[coor]
	if 0<y:
		v[coor],v[coor-X]=v[coor-X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor-X,depth+1]
			q.append(v[:])
		v[coor],v[coor-X]=v[coor-X],v[coor]
	if y<Y-1:
		v[coor],v[coor+X]=v[coor+X],v[coor]
		if ''.join(v) not in m:
			m[''.join(v)]=[coor+X,depth+1]
			q.append(v[:])
		v[coor],v[coor+X]=v[coor+X],v[coor]
try:
	while True:
		v=raw_input().rstrip().split()
		print(m[''.join(v)][1])
except EOFError:
	pass

Submission status: Accepted

Solution code:
def to_xyi(str, target):
  index = 0
  for s in list(str):
    if target == int(s):
      x = index%4
      if index < 4:
        y = 0
      else:
        y = 1
      return (x, y, index)
    index += 1

def zero_swap(str, mx, my):
  zx, zy, zi = to_xyi(str, 0)

  for index in range(len(list(str))):
    sx, sy, si = to_xyi(str, index)
    if (zx + mx) == sx and (zy + my) == sy:
      nstr = []
      for s in list(str):
        if s == str[zi]:
          nstr.append(str[si])
        elif s == str[si]:
          nstr.append(str[zi])
        else:
          nstr.append(s)
      return ''.join(nstr)

rules = (
  (lambda x, y : x <= 2, lambda str : zero_swap(str,  1,  0)),
  (lambda x, y : y == 0, lambda str : zero_swap(str,  0,  1)),
  (lambda x, y : x >= 1, lambda str : zero_swap(str, -1,  0)),
  (lambda x, y : y == 1, lambda str : zero_swap(str,  0, -1)),
)

goal = '01234567'

move_num = {goal: 0}
queue = [goal]

while True:
  if len(queue) == 0: break
  search_map = queue.pop(0)

  for can_move, move in rules:
    x, y, i = to_xyi(search_map, 0)
    if not can_move(x, y): continue
    next_map = move(search_map)
    if move_num.has_key(next_map): continue
    move_num[next_map] = move_num[search_map] + 1
    queue.append(next_map)

import sys
for s in sys.stdin:
  s = s.replace(' ', '').rstrip()
  print move_num[s]

Submission status: Accepted

Solution code:
MOVE = [[1, 4], [0, 2, 5], [1, 3, 6], [2, 7], [0, 5], [1, 4, 6], [2, 5, 7], [3, 6]]
answers = {"01234567": 0}

def swap(field, a, b):
  tmp = list(field)
  tmp[a], tmp[b] = tmp[b], tmp[a]
  return "".join(tmp)

def breadth_first_search(answers):
  q = [[0, "01234567"]]

  while len(q) != 0:
    g, field = q.pop(0)
    a = field.find("0")

    for b in MOVE[a]:
      tmp = swap(field, a, b)

      if not tmp in answers:
        answers[tmp] = g+1
        q.append([g+1, tmp])

  return answers

answers = breadth_first_search(answers)

while True:
  try:
    print answers[raw_input().replace(" ", "")]
  except:
    break

Submission status: Accepted

Solution code:
import itertools
import collections
INF = 10 ** 9

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    p = collections.defaultdict(int)
    q = collections.defaultdict(list)
    for i, v in enumerate(itertools.permutations(range(8))):
        p[v] = i
        q[i] = list(v)

    dist = [INF] * (40325)
    dist[0] = 0
    que = collections.deque()
    que.append(0)

    def change(i, j, l):
        d = dist[p[tuple(l)]]
        l[i], l[j] = l[j], l[i]
        if dist[p[tuple(l)]] == INF:
            dist[p[tuple(l)]] = d + 1
            que.append(p[tuple(l)])
        l[i], l[j] = l[j], l[i]
        return

    while que:
        v = que.popleft()
        ll = q[v]
        i = ll.index(0)

        if i in {0, 4}: change(i, i+1, ll)
        elif i in {3, 7}: change(i-1, i, ll)
        else:
            change(i, i+1, ll)
            change(i-1, i, ll)
        change(i, (i+4)%8, ll)

    while True:
        try:
            A = ZZ()
            print(dist[p[tuple(A)]])
        except:
            break

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# AOJ 0121

from collections import deque

score = {}
score[tuple(range(8))] = 0
queue = deque()
queue.append(tuple(range(8)))
move = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5), (1, 4, 6), (2, 5, 7), (3, 6))
while queue:
    puz = queue.popleft()
    pos = puz.index(0)
    for npos in move[pos]:
        npuz = list(puz)
        npuz[pos], npuz[npos] = npuz[npos], 0
        npuz = tuple(npuz)
        if npuz not in score:
            queue.append(npuz)
            score[npuz] = score[puz] + 1

while True:
    try:
        puzzle = tuple(map(int, input().split()))
        print(score[puzzle])
    except EOFError:
        break

Submission status: Accepted

Solution code:
from collections import deque
from itertools import permutations
from itertools import combinations

puz = [0,1,2,3,4,5,6,7]
puzper = list(permutations(puz))
dic = {}

for i in range(40320):
    dic[puzper[i]] = -1

queue = deque([(0,1,2,3,4,5,6,7)])

dic[(0,1,2,3,4,5,6,7)] = 0
while queue:
    a = queue.popleft()
    poszero = a.index(0)
    yy = (poszero) // 4
    xx = (poszero) % 4
    dydx = [[1,0],[-1,0],[0,1],[0,-1]]
    for j,k in dydx:
        newy,newx = yy+j,xx+k
        if (0 <= newy <2) and (0 <= newx < 4):
            newp = newy*4 + newx
            lisa = list(a)
            lisa[poszero],lisa[newp] = lisa[newp],lisa[poszero]
            newper = tuple(lisa)
            if (dic[newper] == -1):
                dic[newper] = dic[a] + 1
                queue.append(newper)

while True:
    try:
        inp = list(map(int, input().split()))
        print(dic[tuple(inp)])
    except:
        break

Submission status: Runtime Error

Solution code:
import sys
memo = {}
sys.setrecursionlimit(40320)
def swap(state, a, b):
    state[a], state[b] = state[b], state[a]
def dfs(state, pos, c):
    key = "".join(map(str, state))
    if memo.has_key(key):
        return memo[key]
    memo[key] = c
    if pos!=0 and pos!=4:
        swap(state, pos-1, pos)
        dfs(state, pos-1, c+1)
        swap(state, pos-1, pos)
    if pos!=3 and pos!=7:
        swap(state, pos+1, pos)
        dfs(state, pos+1, c+1)
        swap(state, pos+1, pos)
    if pos<4:
        swap(state, pos+4, pos)
        dfs(state, pos+4, c+1)
        swap(state, pos+4, pos)
    else:
        swap(state, pos-4, pos)
        dfs(state, pos-4, c+1)
        swap(state, pos-4, pos)
    return c

dfs(range(8), 0, 0)
while True:
    try:
        state = raw_input().replace(" ","")
        print memo[state]
    except IOError:
        break

Submission status: Runtime Error

Solution code:
import sys
memo = {}
sys.setrecursionlimit(40320)
def swap(state, a, b):
    state[a], state[b] = state[b], state[a]
def dfs(state, pos, c):
    key = "".join(map(str, state))
    if memo.has_key(key):
        return memo[key]
    memo[key] = c
    if pos!=0 and pos!=4:
        swap(state, pos-1, pos)
        dfs(state, pos-1, c+1)
        swap(state, pos-1, pos)
    if pos!=3 and pos!=7:
        swap(state, pos+1, pos)
        dfs(state, pos+1, c+1)
        swap(state, pos+1, pos)
    if pos<4:
        swap(state, pos+4, pos)
        dfs(state, pos+4, c+1)
        swap(state, pos+4, pos)
    else:
        swap(state, pos-4, pos)
        dfs(state, pos-4, c+1)
        swap(state, pos-4, pos)
    return c

dfs(range(8), 0, 0)
while True:
    try:
        state = raw_input().replace(" ","")
        print memo[state]
    except KeyError:
        pass
    except IOError:
        break

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#// left rotate
def rotate1L(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate2L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[2],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate3L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[2],seq[3],seq[7],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
#// right rotate
def rotate1R(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[4],seq[1],seq[5]
	return tuple(seq)
def rotate2R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[6],seq[5]
	return tuple(seq)
def rotate3R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[3],seq[7],seq[6],seq[5]
	return tuple(seq)

def gen_new(seq,d):
	yield rotate1L(seq),d+4
	yield rotate2L(seq),d+6
	yield rotate3L(seq),d+8
	yield rotate1R(seq),d+4
	yield rotate2R(seq),d+6
	yield rotate3R(seq),d+8

from collections import defaultdict
step = defaultdict(int)
def init_step():
	global step
	seq = tuple(list(range(8)))
	current = set()
	current.add(seq)
	step[seq]=0
	while len(current)!=0:
		candidate = set()
		for s in current:
			for ss,d in gen_new(s,step[s]):
				if ss not in step:
					candidate.add(ss)
					step[ss]=d
					continue
				if d < step[ss]:
					step[ss]=d
					candidate.add(ss)
		current = candidate

def solve(seq):
	init_step = 0
	# let CACHE[0]==0 and calculate init step
	zero_position = seq.index(0)
	col,row = zero_position%4,zero_position//4
	if row==1:
		init_step += 1
		seq[col],seq[col+4]=seq[col+4],seq[col]
	while col!=0:
		init_step += 1
		seq[col],seq[col-1]=seq[col-1],seq[col]
		col -= 1
	global step
	return step[tuple(seq)]+init_step


def main():
	init_step()
	line = input().strip()
	while line!='':
		seq = list(map(int,line.split(' ')))
		print(solve(seq))
		line = input().strip()

if __name__=='__main__':
	main()

"""

/*

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


0
1
28
*/

"""

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#// left rotate
def rotate1L(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate2L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[2],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate3L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[2],seq[3],seq[7],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
#// right rotate
def rotate1R(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[4],seq[1],seq[5]
	return tuple(seq)
def rotate2R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[6],seq[5]
	return tuple(seq)
def rotate3R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[3],seq[7],seq[6],seq[5]
	return tuple(seq)

def gen_new(seq,d):
	yield rotate1L(seq),d+4
	yield rotate2L(seq),d+6
	yield rotate3L(seq),d+8
	yield rotate1R(seq),d+4
	yield rotate2R(seq),d+6
	yield rotate3R(seq),d+8

from collections import defaultdict
step = defaultdict(int)
def init_step():
	global step
	seq = tuple(list(range(8)))
	current = set()
	current.add(seq)
	step[seq]=0
	while len(current)!=0:
		candidate = set()
		for s in current:
			for ss,d in gen_new(s,step[s]):
				if ss not in step:
					candidate.add(ss)
					step[ss]=d
					continue
				if d < step[ss]:
					step[ss]=d
					candidate.add(ss)
		current = candidate

def solve(seq):
	global step
	init_step = 0
	# let CACHE[0]==0 and calculate init step
	zero_position = seq.index(0)
	col,row = zero_position%4,zero_position//4
	if row==1:
		init_step += 1
		seq[col],seq[col+4]=seq[col+4],seq[col]
	while col!=0:
		init_step += 1
		seq[col],seq[col-1]=seq[col-1],seq[col]
		col -= 1
	return step[tuple(seq)]+init_step


def main():
	init_step()
	line = input().strip()
	while line!='':
		seq = list(map(int,line.split(' ')))
		print(solve(seq))
		line = input().strip()

if __name__=='__main__':
	main()

"""

/*

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


0
1
28
*/

"""

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def rotate1L(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate2L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[2],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate3L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[2],seq[3],seq[7],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate1R(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[4],seq[1],seq[5]
	return tuple(seq)
def rotate2R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[6],seq[5]
	return tuple(seq)
def rotate3R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[3],seq[7],seq[6],seq[5]
	return tuple(seq)

def gen_new(seq,d):
	yield rotate1L(seq),d+4
	yield rotate2L(seq),d+6
	yield rotate3L(seq),d+8
	yield rotate1R(seq),d+4
	yield rotate2R(seq),d+6
	yield rotate3R(seq),d+8

from collections import defaultdict
step = defaultdict(int)
def init_step():
	global step
	seq = tuple(list(range(8)))
	current = set()
	current.add(seq)
	step[seq]=0
	while len(current)!=0:
		candidate = set()
		for s in current:
			for ss,d in gen_new(s,step[s]):
				if ss not in step:
					candidate.add(ss)
					step[ss]=d
					continue
				if d < step[ss]:
					step[ss]=d
					candidate.add(ss)
		current = candidate

def solve(seq):
	global step

	init_step = 0
	# let CACHE[0]==0 and calculate initilizing step size
	zero_position = seq.index(0)
	col,row = zero_position%4,zero_position//4
	if row==1:
		init_step += 1
		seq[col],seq[col+4]=seq[col+4],seq[col]
	while col!=0:
		init_step += 1
		seq[col],seq[col-1]=seq[col-1],seq[col]
		col -= 1
	return step[tuple(seq)]+init_step


def main():
	init_step()
	line = input().strip()
	while line!='':
		seq = list(map(int,line.split(' ')))
		print(solve(seq))
		line = input().strip()

if __name__=='__main__':
	main()

"""

/*

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


0
1
28
*/

"""

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def rotate1L(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate2L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[2],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate3L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[2],seq[3],seq[7],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate1R(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[4],seq[1],seq[5]
	return tuple(seq)
def rotate2R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[6],seq[5]
	return tuple(seq)
def rotate3R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[3],seq[7],seq[6],seq[5]
	return tuple(seq)

def gen_new(seq,d):
	yield rotate1L(seq),d+4
	yield rotate2L(seq),d+6
	yield rotate3L(seq),d+8
	yield rotate1R(seq),d+4
	yield rotate2R(seq),d+6
	yield rotate3R(seq),d+8

from collections import defaultdict
step = defaultdict(int)
def init_step():
	global step
	"""
	seq = tuple(list(range(8)))
	current = set()
	current.add(seq)
	step[seq]=0
	while len(current)!=0:
		candidate = set()
		for s in current:
			for ss,d in gen_new(s,step[s]):
				if ss not in step:
					candidate.add(ss)
					step[ss]=d
					continue
				if d < step[ss]:
					step[ss]=d
					candidate.add(ss)
		current = candidate
	"""

def solve(seq):
	global step

	init_step = 0
	# let CACHE[0]==0 and calculate initilizing step size
	zero_position = seq.index(0)
	col,row = zero_position%4,zero_position//4
	if row==1:
		init_step += 1
		seq[col],seq[col+4]=seq[col+4],seq[col]
	while col!=0:
		init_step += 1
		seq[col],seq[col-1]=seq[col-1],seq[col]
		col -= 1
	return step[tuple(seq)]+init_step


def main():
	init_step()
	line = input().strip()
	while line!='':
		seq = list(map(int,line.split(' ')))
		print(solve(seq))
		line = input().strip()

if __name__=='__main__':
	main()

"""

/*

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


0
1
28
*/

"""

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

def rotate1L(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate2L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[2],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate3L(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[2],seq[3],seq[7],seq[6],seq[5],seq[4],seq[1]
	return tuple(seq)
def rotate1R(seq):
	seq = list(seq)
	seq[1],seq[5],seq[4]=seq[4],seq[1],seq[5]
	return tuple(seq)
def rotate2R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[6],seq[5]
	return tuple(seq)
def rotate3R(seq):
	seq = list(seq)
	seq[1],seq[2],seq[3],seq[7],seq[6],seq[5],seq[4]=seq[4],seq[1],seq[2],seq[3],seq[7],seq[6],seq[5]
	return tuple(seq)

def gen_new(seq,d):
	yield rotate1L(seq),d+4
	yield rotate2L(seq),d+6
	yield rotate3L(seq),d+8
	yield rotate1R(seq),d+4
	yield rotate2R(seq),d+6
	yield rotate3R(seq),d+8

from collections import defaultdict
step = defaultdict(int)
def init_step():
	global step
	"""
	seq = tuple(list(range(8)))
	current = set()
	current.add(seq)
	step[seq]=0
	while len(current)!=0:
		candidate = set()
		for s in current:
			for ss,d in gen_new(s,step[s]):
				if ss not in step:
					candidate.add(ss)
					step[ss]=d
					continue
				if d < step[ss]:
					step[ss]=d
					candidate.add(ss)
		current = candidate
	"""

def solve(seq):
	"""
	global step

	init_step = 0
	# let CACHE[0]==0 and calculate initilizing step size
	zero_position = seq.index(0)
	col,row = zero_position%4,zero_position//4
	if row==1:
		init_step += 1
		seq[col],seq[col+4]=seq[col+4],seq[col]
	while col!=0:
		init_step += 1
		seq[col],seq[col-1]=seq[col-1],seq[col]
		col -= 1
	return step[tuple(seq)]+init_step
	"""
	return 0


def main():
	init_step()
	line = input().strip()
	while line!='':
		seq = list(map(int,line.split(' ')))
		print(solve(seq))
		line = input().strip()

if __name__=='__main__':
	main()

"""

/*

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0


0
1
28
*/

"""