#!/usr/bin/pypy3
# 推荐使用pypy，建立查找表的过程远比cpython快
import random
from collections import deque
from itertools import permutations
import json
import os

# 参考资料
# https://www.jaapsch.net/puzzles/thistle.htm
# https://zhuanlan.zhihu.com/p/111623841
# https://www.zhihu.com/question/67518391
# http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=104760
# http://bbs.mf8-china.com/forum.php?mod=viewthread&tid=106671
# https://tomas.rokicki.com/cubecontest/jaap.txt

#Group  # positions      Factor
#G0=<U  D  L  R  F  B >  4.33·10^19  2,048 (2^11)
#G1=<U  D  L  R  F2 B2>  2.11·10^16  1,082,565 (12C4 ·3^7)
#G2=<U  D  L2 R2 F2 B2>  1.95·10^10  29,400 ( 8C4^2 ·2·3)
#G3=<U2 D2 L2 R2 F2 B2>  6.63·10^5   663,552 (4!^5/12)


#G4=I   1

#                           2-----------2------------1
#                           | U1(0)   U2(1)   U3(2)  |
#                           |                        |
#                           3 U4(3)   U5(4)   U6(5)  1
#                           |                        |
#                           | U7(6)   U8(7)   U9(8)  |
#  2-----------3------------3-----------0------------0-----------1------------1------------2------------2
#  | L1(36)  L2(37)  L3(38) | F1(18)  F2(19)  F3(20) | R1(9)   R2(10)  R3(11) |  B1(45)  B2(46)  B3(47) |
#  |                        |                        |                        |                         |
# 11 L4(39)  L5(40)  L6(41) 9 F4(21)  F5(22)  F6(23) 8 R4(12)  R5(13)  R6(14) 10 B4(48)  B5(49)  B6(50) 11
#  |                        |                        |                        |                         |
#  | L7(42)  L8(43)  L9(44) | F7(24)  F8(25)  F9(26) | R7(15)  R8(16)  R9(17) |  B7(51)  B8(52)  B9(53) |
#  3-----------7------------5-----------4------------4-----------5------------7------------6------------3
#                           | D1(27)  D2(28)  D3(29) |
#                           |                        |
#                           7 D4(30)  D5(31)  D6(32) 5
#                           |                        |
#                           | D7(33)  D8(34)  D9(35) |
#                           6-----------6------------7
# 用于转换两种表示方式 20个棱块角块 <---> 54个面
# [UF, UR, UB, UL,DF, DR, DB, DL, FR, FL, BR, BL] [UFR, URB, UBL, ULF, DRF, DFL, DLB, DBR]
# UUUUUUUUURRRRRRRRRFFFFFFFFFDDDDDDDDDLLLLLLLLLBBBBBBBBB
edge_to_face =(('UF', 7, 19),  ('UR', 5, 10),  ('UB', 1, 46),  ('UL', 3, 37),
               ('DF', 28, 25), ('DR', 32, 16), ('DB', 34, 52), ('DL', 30, 43),
               ('FR', 23, 12), ('FL', 21, 41), ('BR', 48, 14), ('BL', 50, 39))
corner_to_face =(('UFR', 8, 20, 9), ('URB', 2, 11, 45), ('UBL', 0, 47, 36), ('ULF', 6, 38, 18),
                ('DRF', 29, 15, 26), ('DFL', 27, 24, 44), ('DLB', 33, 42, 53), ('DBR', 35, 51, 17))
edge_index = ('UF','UR','UB','UL','DF','DR','DB','DL','FR','FL','BR','BL',
              'FU','RU','BU','LU','FD','RD','BD','LD','RF','LF','RB','LB')
corner_index = ('UFR','URB','UBL','ULF','DRF','DFL','DLB','DBR',
                'FRU','RBU','BLU','LFU','RFD','FLD','LBD','BRD',
                'RUF','BUR','LUB','FUL','FDR','LDF','BDL','RDB')
# 魔方旋转时各个块的变化
route_index=("L","L'","L2","R","R'","R2","U","U'","U2","D","D'","D2","F","F'","F2","B","B'","B2");
route_tab=(
    ((0,1,2,11,4,5,6,9,8,3,10,7),(0,0,0,0,0,0,0,0,0,0,0,0),(0,1,6,2,4,3,5,7),(0,0,2,1,0,2,1,0)),# L  0
    ((0,1,2,9,4,5,6,11,8,7,10,3),(0,0,0,0,0,0,0,0,0,0,0,0),(0,1,3,5,4,6,2,7),(0,0,2,1,0,2,1,0)),# L' 1
    ((0,1,2,7,4,5,6,3,8,11,10,9),(0,0,0,0,0,0,0,0,0,0,0,0),(0,1,5,6,4,2,3,7),(0,0,0,0,0,0,0,0)),# L2 2
    ((0,8,2,3,4,10,6,7,5,9,1,11),(0,0,0,0,0,0,0,0,0,0,0,0),(4,0,2,3,7,5,6,1),(2,1,0,0,1,0,0,2)),# R  3
    ((0,10,2,3,4,8,6,7,1,9,5,11),(0,0,0,0,0,0,0,0,0,0,0,0),(1,7,2,3,0,5,6,4),(2,1,0,0,1,0,0,2)),# R' 4
    ((0,5,2,3,4,1,6,7,10,9,8,11),(0,0,0,0,0,0,0,0,0,0,0,0),(7,4,2,3,1,5,6,0),(0,0,0,0,0,0,0,0)),# R2 5
    ((1,2,3,0,4,5,6,7,8,9,10,11),(0,0,0,0,0,0,0,0,0,0,0,0),(1,2,3,0,4,5,6,7),(0,0,0,0,0,0,0,0)),# U  6
    ((3,0,1,2,4,5,6,7,8,9,10,11),(0,0,0,0,0,0,0,0,0,0,0,0),(3,0,1,2,4,5,6,7),(0,0,0,0,0,0,0,0)),# U' 7
    ((2,3,0,1,4,5,6,7,8,9,10,11),(0,0,0,0,0,0,0,0,0,0,0,0),(2,3,0,1,4,5,6,7),(0,0,0,0,0,0,0,0)),# U2 8
    ((0,1,2,3,7,4,5,6,8,9,10,11),(0,0,0,0,0,0,0,0,0,0,0,0),(0,1,2,3,5,6,7,4),(0,0,0,0,0,0,0,0)),# D  9
    ((0,1,2,3,5,6,7,4,8,9,10,11),(0,0,0,0,0,0,0,0,0,0,0,0),(0,1,2,3,7,4,5,6),(0,0,0,0,0,0,0,0)),# D' 10
    ((0,1,2,3,6,7,4,5,8,9,10,11),(0,0,0,0,0,0,0,0,0,0,0,0),(0,1,2,3,6,7,4,5),(0,0,0,0,0,0,0,0)),# D2 11
    ((9,1,2,3,8,5,6,7,0,4,10,11),(1,0,0,0,1,0,0,0,1,1,0,0),(3,1,2,5,0,4,6,7),(1,0,0,2,2,1,0,0)),# F  12
    ((8,1,2,3,9,5,6,7,4,0,10,11),(1,0,0,0,1,0,0,0,1,1,0,0),(4,1,2,0,5,3,6,7),(1,0,0,2,2,1,0,0)),# F' 13
    ((4,1,2,3,0,5,6,7,9,8,10,11),(0,0,0,0,0,0,0,0,0,0,0,0),(5,1,2,4,3,0,6,7),(0,0,0,0,0,0,0,0)),# F2 14
    ((0,1,10,3,4,5,11,7,8,9,6,2),(0,0,1,0,0,0,1,0,0,0,1,1),(0,7,1,3,4,5,2,6),(0,2,1,0,0,0,2,1)),# B  15
    ((0,1,11,3,4,5,10,7,8,9,2,6),(0,0,1,0,0,0,1,0,0,0,1,1),(0,2,6,3,4,5,7,1),(0,2,1,0,0,0,2,1)),# B' 16
    ((0,1,6,3,4,5,2,7,8,9,11,10),(0,0,0,0,0,0,0,0,0,0,0,0),(0,6,7,3,4,5,1,2),(0,0,0,0,0,0,0,0)) # B2 17
)


class Cube():
    def __init__(self):
        self.ep = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] # 楞块位置
        self.er = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  0]  # 楞块方向
        self.cp = [0, 1, 2, 3, 4, 5, 6, 7] # 角块位置 
        self.cr = [0, 0, 0, 0, 0, 0, 0, 0] # 角块方向
        self.step = 0
        
    def dump(self):
        s = []
        for i in range(0,12):
            s.append(edge_index[self.ep[i] + 12*self.er[i]])
        for i in range(0,8):
            s.append(corner_index[self.cp[i] + 8*self.cr[i]])
        print(s)
        print(self.ep)
        print(self.er)
        print(self.cp)
        print(self.cr)
        
    
    def from_face_54(self, cube_str):
        # 54个面的表示方式，转换为棱块角块表示方式
        for i in range(0,12):
            index_a = edge_to_face[i][1]
            index_b = edge_to_face[i][2]
            tmp = edge_index.index(cube_str[index_a] + cube_str[index_b])
            self.ep[i] = tmp % 12
            self.er[i] = tmp // 12
        for i in range(0,8):
            index_a = corner_to_face[i][1]
            index_b = corner_to_face[i][2]
            index_c = corner_to_face[i][3]
            tmp = corner_index.index(cube_str[index_a] + cube_str[index_b] + cube_str[index_c])
            self.cp[i] = tmp % 8
            self.cr[i] = tmp // 8
    def to_face_54(self):
        # 转换为54个面的状态
        cube_str = [' ']*54;
        cube_str[4]  = 'U'
        cube_str[13] = 'R'
        cube_str[22] = 'F'
        cube_str[31] = 'D'
        cube_str[40] = 'L'
        cube_str[49] = 'B'
        for i in range(0,12):
            index_a = edge_to_face[i][1]
            index_b = edge_to_face[i][2]
            s = edge_index[self.ep[i] + self.er[i]*12]
            cube_str[index_a] = s[0]
            cube_str[index_b] = s[1]
        for i in range(0,8):
            index_a = corner_to_face[i][1]
            index_b = corner_to_face[i][2]
            index_c = corner_to_face[i][3]
            s = corner_index[self.cp[i] + self.cr[i]*8]
            cube_str[index_a] = s[0]
            cube_str[index_b] = s[1]
            cube_str[index_c] = s[2]
        return ''.join(cube_str)
    # 拧魔方d=0-17，或者字母表示
    def route(self, d):
        new_ep = [0]*12
        new_er = [0]*12
        new_cp = [0]*8
        new_cr = [0]*8
        if(type(d) == int):
            r = route_tab[d]
        else:
            r = route_tab[route_index.index(d)]
        for i in range(0,12):
            new_ep[i] = self.ep[r[0][i]]
            new_er[i] = self.er[r[0][i]] ^ r[1][i]
        for i in range(0,8):
            new_cp[i] = self.cp[r[2][i]]
            new_cr[i] = (self.cr[r[2][i]] + r[3][i]) % 3
        self.ep = new_ep
        self.er = new_er
        self.cp = new_cp
        self.cr = new_cr
    def route_and_new(self, d):
        new_ep = [0]*12
        new_er = [0]*12
        new_cp = [0]*8
        new_cr = [0]*8
        if(type(d) == int):
            r = route_tab[d]
        else:
            r = route_tab[route_index.index(d)]
        for i in range(0,12):
            new_ep[i] = self.ep[r[0][i]]
            new_er[i] = self.er[r[0][i]] ^ r[1][i]
        for i in range(0,8):
            new_cp[i] = self.cp[r[2][i]]
            new_cr[i] = (self.cr[r[2][i]] + r[3][i]) % 3
        c = Cube()
        c.ep = new_ep
        c.er = new_er
        c.cp = new_cp
        c.cr = new_cr
        c.step = self.step + 1
        return c
    
    # 绘制魔方
    def draw(self):
        cube_str = self.to_face_54()
        cube_map = [99, 99, 99, 0,  1,  2,  99, 99, 99, 99, 99, 99, 98,
                    99, 99, 99, 3,  4,  5,  99, 99, 99, 99, 99, 99, 98,
                    99, 99, 99, 6,  7,  8,  99, 99, 99, 99, 99, 99, 98,
                    36, 37, 38, 18, 19, 20, 9,  10, 11, 45, 46, 47, 98,
                    39, 40, 41, 21, 22, 23, 12, 13, 14, 48, 49, 50, 98,
                    42, 43, 44, 24, 25, 26, 15, 16, 17, 51, 52, 53, 98,
                    99, 99, 99, 27, 28, 29, 99, 99, 99, 99, 99, 99, 98,
                    99, 99, 99, 30, 31, 32, 99, 99, 99, 99, 99, 99, 98,
                    99, 99, 99, 33, 34, 35, 99, 99, 99, 99, 99, 99, 98]
        for x in cube_map:
            if x == 99:
                print("  ", end='')
            elif x == 98:
                print("")
            else:
                print(cube_str[x] + " ", end='')
    
    def random(self):
        for i in range(0,100):
            self.route(random.choice(("L","R","U","D","F","B","L'","R'","U'","D'","F'","B'","L2","R2","U2","D2","F2","B2")))
    def encode(self, x):
        if   x == 0:
            # G0 编码角块方向
            x = 0
            for i in range(11):
                x = x | (self.er[i] << i)
            return x
        elif x == 1:
            # G1 编码棱块方向和中间层棱块的相对位置
            # 12C4  *  3^7 = 495 * 2187 = 总的状态数量1,082,565
            # 编码角块方向
            x = 0
            for i in range(7):
                x = x*3 + self.cr[i]
            # 编码棱块位置
            global encode_table_12C4
            bin_ep = 0
            for i in range(12):
                if(self.ep[i] >= 8):
                    bin_ep = bin_ep | (1 << i)
            y = encode_table_12C4[bin_ep]
            return x * 495 + y
        elif x == 2 :
            # G2 编码角块，楞块的分轨道情况,8C4 * 8C4 * 6
            # 编码角块排列0-69
            bin_cp = 0
            for i in range(8):
                if(self.cp[i] in (1,3,4,6)):
                    bin_cp = bin_cp | (1 << i)
            encode_c = encode_table_8C4[bin_cp]
            # 编码棱块排列0-69
            bin_ep = 0
            for i in range(8):
                if(self.ep[i] & 1): # 1 3 5 7
                    bin_ep = bin_ep | (1 << i)
            encode_e = encode_table_8C4[bin_ep]
            
            # 两组位于不同轨道角块之间的关系，6种状态
            corn_group_a = [0]*4
            corn_group_b = [0]*4
            corn_group_a_index = 0
            corn_group_b_index = 0
            corn2 = [0]*4
            for i in range(8):
                if(self.cp[i] in (1,3,4,6)):
                    corn_group_a[corn_group_a_index] = self.cp[i] # 记录阴轨角顺序
                    corn_group_a_index += 1
                else:# 0 2 5 7
                    corn_group_b[corn_group_b_index] = self.cp[i] # 记录阳轨角顺序
                    corn_group_b_index += 1
            
            # encode_4P4(a)*24 + encode_4P4(b)计算结果有576种，按照能否通过
            # U2 D2 L2 R2 F2 B2互相变换，分为6组，组内可以通过U2 D2 L2 R2 F2 B2
            # 互相变换，组间只能通过U D L2 R2 F2 B2互相变换
            # 棱块排列 角块排列
            z = encode_4P4(corn_group_a)*24 + encode_4P4(corn_group_b)
            
            return z + encode_c*576 + encode_e*576*70

        elif x == 3:
            # 多了12倍
            r = encode_4P4((self.cp[1],self.cp[3],self.cp[4],self.cp[6]))
            r = 24*r + encode_4P4((self.cp[0],self.cp[2],self.cp[5],self.cp[7]))
            r = 24*r + encode_4P4((self.ep[1],self.ep[3],self.ep[5],self.ep[7]))
            r = 24*r + encode_4P4((self.ep[0],self.ep[2],self.ep[4],self.ep[6]))
            r = 24*r + encode_4P4((self.ep[8],self.ep[9],self.ep[10],self.ep[11]))
            return r

# 第1步 G0->G1。把所有的棱方向摆成一致。
# G0 查找表，记录每种状态的最短还原步骤数量

# 第2步 G1->G2。8个角的状态正确，而且中间层棱块在中间层
# G1 查找表，记录每种状态的最短还原步骤数量

# G2

# G3




def creat_table(encode_id, file_name, table_length, search):
    cube = Cube()
    visited = [-1]*table_length
    q = deque()
    q.append(cube)
    visited[cube.encode(encode_id)] = cube.step
    count = 0
    while len(q) != 0:
        count += 1
        if count%10000 == 0:
            print("%.1f%%"%(count*100/table_length))
        c = q.popleft()
        for s in search:
            c_new = c.route_and_new(s)
            code = c_new.encode(encode_id)
            if visited[code] < 0:# 如果无数据记录
                visited[code] = c_new.step
                q.append(c_new)
            elif visited[code] > c_new.step:#有数据记录，但是数据不是最优的
                print("visited[code] > c_new.step, code =", code)
                # 实测不存在这种情况
                visited[code] = c_new.step
                q.append(c_new)
               
    with open(file_name,"w") as f:
        json.dump(visited,f)
        print("write file",file_name)
    for i in range(-1,20):
        print("steps = %d, totel %d."%(i,visited.count(i)))
        
def search(encode_id, c, table, search, deep = 0):
    route = []
    #old_min_step = 99
    # 需要还原
    while True:
        # 还原好了
        min_step_root = table[c.encode(encode_id)]
        #print("min step is", min_step_root)
        if min_step_root == 0:
            return c, route
        # 没有还原好
        step_to_end = [99] * 18
        for i in search:
            cube_tmp = c.route_and_new(i)
            step_to_end[i] = table[cube_tmp.encode(encode_id)]
        #min_step = min(step_to_end)
        #index = step_to_end.index(min_step)
        #print(step_to_end, min_step, step_to_end.count(min_step))
        #print(step_to_end)
        index = step_to_end.index(min_step_root - 1)
        route.append(route_index[index])
        c = c.route_and_new(index)

        
        
        
def load_table(file):
    if not os.path.isfile(file):
        print("can not find",file)
        return None
    with open(file,'r') as f:
        load_dict = json.load(f)
    return load_dict

def load_or_create_table(x):
    if   x == 0:
        tab = load_table("G0.json")
        if tab == None:
            creat_table(0, "G0.json", 2048, (0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17))
            tab = load_table("G0.json")
        return tab
    elif x == 1:
        tab = load_table("G1.json")
        if tab == None:
            creat_table(1, "G1.json", 1082565, (0,1,2,3,4,5,6,7,8,9,10,11,14,17))
            tab = load_table("G1.json")
        return tab
    elif x == 2:
        tab = load_table("G2.json")
        if tab == None:
            creat_table(2, "G2.json", 29400 * 96, (2,5,6,7,8,9,10,11,14,17)) 
            tab = load_table("G2.json")
        return tab
    elif x == 3:
        tab = load_table("G3.json")
        if tab == None:
            creat_table(3, "G3.json", 663552 * 12, (2,5,8,11,14,17)) 
            tab = load_table("G3.json")
        return tab
        pass    
    



# 编码4个数字的全排列，例如(1, 0, 2, 3) => 6
def encode_4P4(p):
    n=0;
    for a in range(4):
        n *= 4-a;
        for b in range(a+1,4):
            if p[b] < p[a]:
                n += 1;
    return n

def create_12C4_encode_table():
    # 2 ** 12 = 4096 
    encode = 0;
    encode_table = [-1] * 4096
    for x in range(4096):
        count_one = 0;
        for i in range(12):
            if x & (1<<i):
                count_one += 1
        if count_one == 4:
            encode_table[x] = encode
            encode += 1
    #print("create_12C4_encode_table: ",encode)
    return encode_table

def create_8C4_encode_table():
    # 2 ** 8 = 256 
    encode = 0;
    encode_table = [-1] * 256
    for x in range(256):
        count_one = 0;
        for i in range(8):
            if x & (1<<i):
                count_one += 1
        if count_one == 4:
            encode_table[x] = encode
            encode += 1
    #print("create_8C4_encode_table: ",encode)
    return encode_table

# 
# encode_table_G2_576 =[
#     0,1,2,3,4,5,1,0,4,5,2,3,3,2,5,4,0,1,5,4,3,2,1,0,
#     1,0,3,2,5,4,0,1,5,4,3,2,2,3,4,5,1,0,4,5,2,3,0,1,
#     5,3,4,1,2,0,3,5,2,0,4,1,1,4,0,2,5,3,0,2,1,4,3,5,
#     3,5,1,4,0,2,5,3,0,2,1,4,4,1,2,0,3,5,2,0,4,1,5,3,
#     4,2,5,0,3,1,2,4,3,1,5,0,0,5,1,3,4,2,1,3,0,5,2,4,
#     2,4,0,5,1,3,4,2,1,3,0,5,5,0,3,1,2,4,3,1,5,0,4,2,
#     1,0,3,2,5,4,0,1,5,4,3,2,2,3,4,5,1,0,4,5,2,3,0,1,
#     0,1,2,3,4,5,1,0,4,5,2,3,3,2,5,4,0,1,5,4,3,2,1,0,
#     4,2,5,0,3,1,2,4,3,1,5,0,0,5,1,3,4,2,1,3,0,5,2,4,
#     2,4,0,5,1,3,4,2,1,3,0,5,5,0,3,1,2,4,3,1,5,0,4,2,
#     5,3,4,1,2,0,3,5,2,0,4,1,1,4,0,2,5,3,0,2,1,4,3,5,
#     3,5,1,4,0,2,5,3,0,2,1,4,4,1,2,0,3,5,2,0,4,1,5,3,
#     3,5,1,4,0,2,5,3,0,2,1,4,4,1,2,0,3,5,2,0,4,1,5,3,
#     5,3,4,1,2,0,3,5,2,0,4,1,1,4,0,2,5,3,0,2,1,4,3,5,
#     2,4,0,5,1,3,4,2,1,3,0,5,5,0,3,1,2,4,3,1,5,0,4,2,
#     4,2,5,0,3,1,2,4,3,1,5,0,0,5,1,3,4,2,1,3,0,5,2,4,
#     0,1,2,3,4,5,1,0,4,5,2,3,3,2,5,4,0,1,5,4,3,2,1,0,
#     1,0,3,2,5,4,0,1,5,4,3,2,2,3,4,5,1,0,4,5,2,3,0,1,
#     2,4,0,5,1,3,4,2,1,3,0,5,5,0,3,1,2,4,3,1,5,0,4,2,
#     4,2,5,0,3,1,2,4,3,1,5,0,0,5,1,3,4,2,1,3,0,5,2,4,
#     3,5,1,4,0,2,5,3,0,2,1,4,4,1,2,0,3,5,2,0,4,1,5,3,
#     5,3,4,1,2,0,3,5,2,0,4,1,1,4,0,2,5,3,0,2,1,4,3,5,
#     1,0,3,2,5,4,0,1,5,4,3,2,2,3,4,5,1,0,4,5,2,3,0,1,
#     0,1,2,3,4,5,1,0,4,5,2,3,3,2,5,4,0,1,5,4,3,2,1,0]


# def calc_step2_576_to_6_table():
#     corn_group_a = list(permutations((1, 3, 4, 6),4))
#     corn_group_b = list(permutations((0, 2, 5, 7),4))
#     table = [None]*576
#     table2 = [None]*576
#     for i in range(24):
#         for j in range(24):
#             a = corn_group_a[i]
#             b = corn_group_b[j]
#             index = encode_4P4(a)*24 + encode_4P4(b)
#             table[index] = [[b[0],a[0],b[1],a[1],a[2],b[2],a[3],b[3]],None]
#             
#     
#     type_code = 0
#     for i in range(576):
#         if table[i][1] == None:
#             table[i][1] = type_code
#             c = Cube();
#             c.cp = table[i][0].copy()
#             # 经过足够长时间的随机转动，有极高概率会遍历所有状态
#             # 懒得写搜索算法了，反正这代码只用一次
#             for j in range(5000):
#                 rand = random.choice(("L2","R2","U2","D2","F2","B2"))
#                 c.route(rand)
#                 a = (c.cp[1], c.cp[3], c.cp[4], c.cp[6])
#                 b = (c.cp[0], c.cp[2], c.cp[5], c.cp[7])
#                 new_index = encode_4P4(a)*24 + encode_4P4(b)
#                 table[new_index][1] = type_code
#             type_code += 1
#     # 确认结果的正确性
#     assert(type_code == 6)
#     for i in range(576):
#         table2[i] = table[i][1]
#     print(table2)           

print("init lookup table.")
encode_table_8C4 = create_8C4_encode_table()
encode_table_12C4 = create_12C4_encode_table()
tab_G0 = load_or_create_table(0)
tab_G1 = load_or_create_table(1)
tab_G2 = load_or_create_table(2)
tab_G3 = load_or_create_table(3)
def solve(x):
    c = Cube()
    c.from_face_54(x)
    #print("调整全部棱块的方向")
    c, route0 = search(0, c, tab_G0,(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17))
    #print("调整全部角块的方向，同时把中间层棱块放置到中间层")
    c, route1 = search(1, c, tab_G1,(0,1,2,3,4,5,6,7,8,9,10,11,14,17))
    #print("调整角块和棱块的相对位置，放置到各自的轨道")
    c, route2 = search(2, c, tab_G2,(2,5,6,7,8,9,10,11,14,17))
    c, route3 = search(3, c, tab_G3,(2,5,8,11,14,17))
    route = route0 + route1 + route2 + route3
    assert( c.to_face_54() == 'UUUUUUUUURRRRRRRRRFFFFFFFFFDDDDDDDDDLLLLLLLLLBBBBBBBBB' )
    return route
    
def do_test():
    num_test_case = 10000
    print("load test_case.")
    test_case = [None]*num_test_case
    with open("test_case.txt",'r') as f:
        for i in range(num_test_case):
            test_case[i] = f.readline()
    
    max_step = 0
    min_step = 99
    avg_step = 0
    for x in test_case:
        print(x)
        route = solve(x)
        print(" ".join(route))
        length = len(route)
        print("step =", length)
        max_step = max(max_step, length)
        min_step = min(min_step, length)
        avg_step += length
    avg_step = avg_step // num_test_case
    print("最大步骤数",max_step, "最小步骤数",min_step, "平均步骤数",avg_step)
    
#do_test()