Skip to content

Instantly share code, notes, and snippets.

@kusano
Created March 8, 2025 16:56
Show Gist options
  • Save kusano/b636e7f2a116a6c5b7bc6d59f46a7ed7 to your computer and use it in GitHub Desktop.
Save kusano/b636e7f2a116a6c5b7bc6d59f46a7ed7 to your computer and use it in GitHub Desktop.
from itertools import permutations
def normalize(s):
C = []
for ud in range(2):
if ud==0:
ud = {"U": "U", "D": "D"}
else:
ud = {"U": "D", "D": "U"}
for xy in range(2):
if xy==0:
xy = {"X": "X", "Y": "Y"}
else:
xy = {"X": "Y", "Y": "X"}
for p in permutations(range(4)):
C += [tuple([ud[s[i//4*4+p[i%4]][0]]+xy[s[i//4*4+p[i%4]][1]] for i in range(8)])]
C.sort()
return C[0]
def analyse(s):
n = 0
for i in range(4):
if (s[i][0]=="U"):
n += 1
if n==0 or n==4:
ud = "Slashes"
elif n==1 or n==3:
ud = "Bar/Slash"
else:
same = False
diff = False
for i in range(4):
if s[i][0]==s[i+4][0]:
same = True
else:
diff = True
if same and diff:
ud = "Bars"
else:
ud = "Solved"
n = 0
for i in range(4):
if (s[i][1]=="X"):
n += 1
if n==0 or n==4:
fb = "Solved"
elif n==1 or n==3:
fb = "OneBar"
else:
same = False
diff = False
for i in range(4):
if s[i][1]==s[i+4][1]:
same = True
else:
diff = True
if same and diff:
fb = "Bars"
else:
fb = "OneFace"
return f"{ud}+{fb}"
"""
S = set()
for p in permutations(("UX", "UX", "DX", "DX", "UY", "UY", "DY", "DY")):
S.add(normalize(p))
print(S)
"""
S = {
('DX', 'DY', 'UX', 'UY', 'DX', 'UX', 'UY', 'DY'),
('DX', 'DY', 'UX', 'UY', 'UY', 'UX', 'DY', 'DX'),
('DX', 'DX', 'UX', 'UY', 'DY', 'UX', 'DY', 'UY'),
('DX', 'DX', 'DY', 'UX', 'UY', 'UY', 'UX', 'DY'),
('DX', 'DX', 'DY', 'UY', 'DY', 'UX', 'UY', 'UX'),
('DX', 'DY', 'UX', 'UY', 'UX', 'UY', 'DY', 'DX'),
('DX', 'DX', 'DY', 'UX', 'DY', 'UY', 'UX', 'UY'),
('DX', 'DX', 'DY', 'UY', 'DY', 'UX', 'UX', 'UY'),
('DX', 'DX', 'DY', 'UX', 'UX', 'UY', 'DY', 'UY'),
('DX', 'DX', 'UX', 'UY', 'DY', 'UY', 'UX', 'DY'),
('DX', 'DX', 'UX', 'UY', 'DY', 'DY', 'UY', 'UX'),
('DX', 'DX', 'UX', 'UY', 'DY', 'DY', 'UX', 'UY'),
('DX', 'DX', 'UX', 'UY', 'UX', 'UY', 'DY', 'DY'),
('DX', 'DX', 'DY', 'UX', 'DY', 'UX', 'UY', 'UY'),
('DX', 'DY', 'UX', 'UY', 'DX', 'UY', 'DY', 'UX'),
('DX', 'DY', 'UX', 'UY', 'DY', 'DX', 'UY', 'UX'),
('DX', 'DX', 'UY', 'UY', 'DY', 'UX', 'DY', 'UX'),
('DX', 'DX', 'UX', 'UY', 'DY', 'UX', 'UY', 'DY'),
('DX', 'DX', 'DY', 'UY', 'DY', 'UY', 'UX', 'UX'),
('DX', 'DX', 'DY', 'DY', 'UX', 'UY', 'UX', 'UY'),
('DX', 'DX', 'UY', 'UY', 'DY', 'DY', 'UX', 'UX'),
('DX', 'DY', 'UX', 'UY', 'DY', 'UY', 'DX', 'UX'),
('DX', 'DX', 'UX', 'UX', 'DY', 'UY', 'DY', 'UY'),
('DX', 'DX', 'DY', 'UY', 'UX', 'UY', 'UX', 'DY'),
('DX', 'DX', 'DY', 'UX', 'UY', 'UY', 'DY', 'UX'),
('DX', 'DX', 'DY', 'UX', 'UX', 'UY', 'UY', 'DY'),
('DX', 'DY', 'UX', 'UY', 'UX', 'UY', 'DX', 'DY'),
('DX', 'DX', 'DY', 'DY', 'UX', 'UX', 'UY', 'UY'),
('DX', 'DY', 'UX', 'UY', 'DY', 'UX', 'UY', 'DX'),
('DX', 'DY', 'UX', 'UY', 'DX', 'UX', 'DY', 'UY'),
('DX', 'DX', 'UX', 'UY', 'DY', 'UY', 'DY', 'UX'),
('DX', 'DY', 'UX', 'UY', 'DX', 'DY', 'UY', 'UX'),
('DX', 'DX', 'UX', 'UX', 'DY', 'DY', 'UY', 'UY'),
('DX', 'DX', 'UX', 'UX', 'UY', 'UY', 'DY', 'DY'),
('DX', 'DX', 'DY', 'UY', 'UX', 'UX', 'DY', 'UY'),
('DX', 'DX', 'DY', 'DY', 'UY', 'UY', 'UX', 'UX'),
('DX', 'DX', 'UY', 'UY', 'UX', 'UX', 'DY', 'DY'),
('DX', 'DY', 'UX', 'UY', 'DX', 'UY', 'UX', 'DY'),
('DX', 'DY', 'UX', 'UY', 'DX', 'DY', 'UX', 'UY'),
('DX', 'DX', 'DY', 'UY', 'UX', 'UX', 'UY', 'DY'),
('DX', 'DX', 'DY', 'UX', 'DY', 'UY', 'UY', 'UX'),
('DX', 'DX', 'DY', 'UY', 'UX', 'UY', 'DY', 'UX'),
}
S_ = S
S = set()
for s in S_:
S.add(s+(0,))
S.add(s+(1,))
# 0c0 parity=0 かどうかで初期のグループ化。
G = {}
for s in S:
if analyse(s[:8])=="Solved+Solved" and s[8]==0:
G[s] = 0
else:
G[s] = 1
gn = 2
T = {}
while True:
up = False
G2 = {}
for g in range(gn):
U2G = {}
for s in S:
if G[s]==g:
# U, U2 それぞれについて、遷移先のグループの集合を求める。
U = set()
for p in permutations(range(4)):
s2 = list(s[:8])
s2[p[0]], s2[p[1]+4], s2[p[2]], s2[p[3]+4] = s2[p[1]+4], s2[p[2]], s2[p[3]+4], s2[p[0]]
s2 = normalize(s2)
U.add(G[s2+(1-s[8],)])
U2 = set()
for p in permutations(range(4)):
s2 = list(s[:8])
s2[p[0]], s2[p[1]] = s2[p[1]], s2[p[0]]
s2[p[2]+4], s2[p[3]+4] = s2[p[3]+4], s2[p[2]+4]
s2 = normalize(s2)
U2.add(G[s2+(s[8],)])
U = tuple(sorted(list(U)))
U2 = tuple(sorted(list(U2)))
#print(g, s, U, U2)
# 遷移先のグループが異なれば異なるグループにする。
if (U, U2) not in U2G:
if len(U2G)==0:
U2G[(U, U2)] = g
else:
U2G[(U, U2)] = gn
gn += 1
up = True
G2[s] = U2G[(U, U2)]
G = G2
if not up:
break
for g in range(gn):
print(f"Group {g}")
U = set()
U2 = set()
for s in S:
if G[s]==g:
for p in permutations(range(4)):
s2 = list(s[:8])
s2[p[0]], s2[p[1]+4], s2[p[2]], s2[p[3]+4] = s2[p[1]+4], s2[p[2]], s2[p[3]+4], s2[p[0]]
s2 = normalize(s2)
U.add(G[s2+(1-s[8],)])
for p in permutations(range(4)):
s2 = list(s[:8])
s2[p[0]], s2[p[1]] = s2[p[1]], s2[p[0]]
s2[p[2]+4], s2[p[3]+4] = s2[p[3]+4], s2[p[2]+4]
s2 = normalize(s2)
U2.add(G[s2+(s[8],)])
print(s, analyse(s[:8]))
U = sorted(list(U))
U2 = sorted(list(U2))
print(f"U: {U}")
print(f"U2: {U2}")
print()
Group 0
('DX', 'DX', 'UX', 'UX', 'UY', 'UY', 'DY', 'DY', 0) Solved+Solved
('DX', 'DX', 'UX', 'UX', 'DY', 'DY', 'UY', 'UY', 0) Solved+Solved
U: [2]
U2: [0]
Group 1
('DX', 'DX', 'DY', 'UX', 'UX', 'UY', 'UY', 'DY', 0) Bar/Slash+OneBar
('DX', 'DX', 'DY', 'UX', 'UY', 'UY', 'DY', 'UX', 0) Bar/Slash+OneBar
('DX', 'DX', 'UX', 'UY', 'DY', 'UX', 'UY', 'DY', 0) Bars+OneBar
('DX', 'DX', 'UX', 'UY', 'DY', 'DY', 'UX', 'UY', 0) Solved+OneBar
U: [5, 11]
U2: [13, 16]
Group 2
('DX', 'DX', 'DY', 'DY', 'UX', 'UX', 'UY', 'UY', 1) Slashes+OneFace
('DX', 'DY', 'UX', 'UY', 'DX', 'UY', 'UX', 'DY', 1) Bars+OneFace
('DX', 'DX', 'UY', 'UY', 'UX', 'UX', 'DY', 'DY', 1) Solved+OneFace
U: [0, 4]
U2: [2, 3]
Group 3
('DX', 'DX', 'DY', 'DY', 'UY', 'UY', 'UX', 'UX', 1) Slashes+OneFace
('DX', 'DX', 'UY', 'UY', 'DY', 'DY', 'UX', 'UX', 1) Solved+OneFace
('DX', 'DY', 'UX', 'UY', 'DY', 'UX', 'UY', 'DX', 1) Bars+OneFace
U: [4, 7]
U2: [2, 3]
Group 4
('DX', 'DY', 'UX', 'UY', 'DX', 'DY', 'UY', 'UX', 0) Solved+Bars
('DX', 'DX', 'DY', 'UY', 'DY', 'UX', 'UY', 'UX', 0) Bar/Slash+Bars
('DX', 'DY', 'UX', 'UY', 'DX', 'UX', 'DY', 'UY', 0) Bars+Bars
('DX', 'DX', 'DY', 'UY', 'UX', 'UY', 'UX', 'DY', 0) Bar/Slash+Bars
U: [2, 3, 5, 12]
U2: [4, 6]
Group 5
('DX', 'DX', 'UX', 'UY', 'DY', 'UX', 'DY', 'UY', 1) Bars+OneBar
('DX', 'DX', 'DY', 'UX', 'DY', 'UY', 'UY', 'UX', 1) Bar/Slash+OneBar
('DX', 'DX', 'UX', 'UY', 'DY', 'UX', 'UY', 'DY', 1) Bars+OneBar
('DX', 'DX', 'DY', 'UX', 'UX', 'UY', 'DY', 'UY', 1) Bar/Slash+OneBar
('DX', 'DX', 'UX', 'UY', 'DY', 'UY', 'UX', 'DY', 1) Bars+OneBar
('DX', 'DX', 'DY', 'UX', 'UX', 'UY', 'UY', 'DY', 1) Bar/Slash+OneBar
U: [1, 4, 6, 13]
U2: [5, 12]
Group 6
('DX', 'DX', 'DY', 'UY', 'UX', 'UY', 'DY', 'UX', 0) Bar/Slash+Bars
('DX', 'DY', 'UX', 'UY', 'DY', 'UY', 'DX', 'UX', 0) Bars+Bars
('DX', 'DX', 'DY', 'UY', 'DY', 'UX', 'UX', 'UY', 0) Bar/Slash+Bars
('DX', 'DY', 'UX', 'UY', 'UX', 'UY', 'DY', 'DX', 0) Solved+Bars
U: [5, 9, 12, 23]
U2: [4, 6]
Group 7
('DX', 'DY', 'UX', 'UY', 'UY', 'UX', 'DY', 'DX', 0) Solved+OneFace
('DX', 'DX', 'UY', 'UY', 'DY', 'DY', 'UX', 'UX', 0) Solved+OneFace
('DX', 'DY', 'UX', 'UY', 'DY', 'DX', 'UY', 'UX', 0) Solved+OneFace
('DX', 'DX', 'DY', 'DY', 'UY', 'UY', 'UX', 'UX', 0) Slashes+OneFace
U: [3, 11]
U2: [7, 10]
Group 8
('DX', 'DX', 'DY', 'DY', 'UX', 'UY', 'UX', 'UY', 0) Slashes+Bars
('DX', 'DY', 'UX', 'UY', 'DX', 'UX', 'UY', 'DY', 0) Bars+Bars
('DX', 'DX', 'UY', 'UY', 'DY', 'UX', 'DY', 'UX', 0) Bars+Bars
('DX', 'DY', 'UX', 'UY', 'DX', 'UY', 'DY', 'UX', 0) Bars+Bars
U: [9, 17, 21, 22]
U2: [8]
Group 9
('DX', 'DX', 'DY', 'UY', 'DY', 'UY', 'UX', 'UX', 1) Bar/Slash+OneFace
('DX', 'DY', 'UX', 'UY', 'DY', 'DX', 'UY', 'UX', 1) Solved+OneFace
('DX', 'DY', 'UX', 'UY', 'UY', 'UX', 'DY', 'DX', 1) Solved+OneFace
U: [6, 8, 19]
U2: [9, 17, 23]
Group 10
('DX', 'DX', 'DY', 'DY', 'UX', 'UX', 'UY', 'UY', 0) Slashes+OneFace
('DX', 'DY', 'UX', 'UY', 'DX', 'DY', 'UX', 'UY', 0) Solved+OneFace
('DX', 'DX', 'UY', 'UY', 'UX', 'UX', 'DY', 'DY', 0) Solved+OneFace
('DX', 'DY', 'UX', 'UY', 'UX', 'UY', 'DX', 'DY', 0) Solved+OneFace
U: [11, 18]
U2: [7, 10]
Group 11
('DX', 'DY', 'UX', 'UY', 'UX', 'UY', 'DY', 'DX', 1) Solved+Bars
('DX', 'DX', 'UY', 'UY', 'DY', 'UX', 'DY', 'UX', 1) Bars+Bars
('DX', 'DY', 'UX', 'UY', 'DX', 'UX', 'DY', 'UY', 1) Bars+Bars
('DX', 'DX', 'DY', 'DY', 'UX', 'UY', 'UX', 'UY', 1) Slashes+Bars
('DX', 'DY', 'UX', 'UY', 'DY', 'UY', 'DX', 'UX', 1) Bars+Bars
('DX', 'DY', 'UX', 'UY', 'DX', 'DY', 'UY', 'UX', 1) Solved+Bars
U: [1, 7, 10, 16]
U2: [11]
Group 12
('DX', 'DX', 'UX', 'UY', 'DY', 'UY', 'DY', 'UX', 1) Bars+OneBar
('DX', 'DX', 'DY', 'UX', 'DY', 'UY', 'UX', 'UY', 1) Bar/Slash+OneBar
U: [4, 6]
U2: [5]
Group 13
('DX', 'DX', 'DY', 'UX', 'DY', 'UX', 'UY', 'UY', 0) Bar/Slash+OneBar
('DX', 'DX', 'DY', 'UX', 'DY', 'UY', 'UY', 'UX', 0) Bar/Slash+OneBar
('DX', 'DX', 'UX', 'UY', 'DY', 'UY', 'UX', 'DY', 0) Bars+OneBar
('DX', 'DX', 'UX', 'UY', 'DY', 'UX', 'DY', 'UY', 0) Bars+OneBar
('DX', 'DX', 'DY', 'UX', 'UX', 'UY', 'DY', 'UY', 0) Bar/Slash+OneBar
('DX', 'DX', 'UX', 'UY', 'UX', 'UY', 'DY', 'DY', 0) Solved+OneBar
U: [5, 15, 22]
U2: [1, 13, 16]
Group 14
('DX', 'DX', 'DY', 'UY', 'UX', 'UX', 'DY', 'UY', 0) Bar/Slash+OneFace
('DX', 'DY', 'UX', 'UY', 'DX', 'UY', 'UX', 'DY', 0) Bars+OneFace
('DX', 'DX', 'DY', 'UY', 'UX', 'UX', 'UY', 'DY', 0) Bar/Slash+OneFace
U: [15, 18]
U2: [14, 19]
Group 15
('DX', 'DX', 'DY', 'UY', 'DY', 'UX', 'UX', 'UY', 1) Bar/Slash+Bars
('DX', 'DX', 'DY', 'UY', 'UX', 'UY', 'UX', 'DY', 1) Bar/Slash+Bars
('DX', 'DY', 'UX', 'UY', 'DX', 'UY', 'DY', 'UX', 1) Bars+Bars
('DX', 'DY', 'UX', 'UY', 'DX', 'UX', 'UY', 'DY', 1) Bars+Bars
('DX', 'DX', 'DY', 'UY', 'UX', 'UY', 'DY', 'UX', 1) Bar/Slash+Bars
('DX', 'DX', 'DY', 'UY', 'DY', 'UX', 'UY', 'UX', 1) Bar/Slash+Bars
U: [13, 14, 16, 19]
U2: [15]
Group 16
('DX', 'DX', 'UX', 'UY', 'DY', 'DY', 'UY', 'UX', 0) Solved+OneBar
('DX', 'DX', 'UX', 'UY', 'DY', 'UY', 'DY', 'UX', 0) Bars+OneBar
('DX', 'DX', 'DY', 'UX', 'DY', 'UY', 'UX', 'UY', 0) Bar/Slash+OneBar
('DX', 'DX', 'DY', 'UX', 'UY', 'UY', 'UX', 'DY', 0) Bar/Slash+OneBar
U: [11, 15]
U2: [1, 13]
Group 17
('DX', 'DX', 'DY', 'UY', 'UX', 'UX', 'UY', 'DY', 1) Bar/Slash+OneFace
('DX', 'DY', 'UX', 'UY', 'DX', 'DY', 'UX', 'UY', 1) Solved+OneFace
U: [8, 20]
U2: [9, 23]
Group 18
('DX', 'DX', 'UX', 'UX', 'DY', 'DY', 'UY', 'UY', 1) Solved+Solved
('DX', 'DX', 'UX', 'UX', 'UY', 'UY', 'DY', 'DY', 1) Solved+Solved
('DX', 'DX', 'UX', 'UX', 'DY', 'UY', 'DY', 'UY', 1) Bars+Solved
U: [10, 14]
U2: [18]
Group 19
('DX', 'DX', 'DY', 'UY', 'DY', 'UY', 'UX', 'UX', 0) Bar/Slash+OneFace
('DX', 'DY', 'UX', 'UY', 'DY', 'UX', 'UY', 'DX', 0) Bars+OneFace
U: [9, 15]
U2: [14, 19]
Group 20
('DX', 'DX', 'UX', 'UX', 'DY', 'UY', 'DY', 'UY', 0) Bars+Solved
U: [17, 23]
U2: [20]
Group 21
('DX', 'DX', 'DY', 'UX', 'UY', 'UY', 'UX', 'DY', 1) Bar/Slash+OneBar
('DX', 'DX', 'UX', 'UY', 'DY', 'DY', 'UY', 'UX', 1) Solved+OneBar
U: [8]
U2: [22]
Group 22
('DX', 'DX', 'UX', 'UY', 'DY', 'DY', 'UX', 'UY', 1) Solved+OneBar
('DX', 'DX', 'UX', 'UY', 'UX', 'UY', 'DY', 'DY', 1) Solved+OneBar
('DX', 'DX', 'DY', 'UX', 'UY', 'UY', 'DY', 'UX', 1) Bar/Slash+OneBar
('DX', 'DX', 'DY', 'UX', 'DY', 'UX', 'UY', 'UY', 1) Bar/Slash+OneBar
U: [8, 13]
U2: [21, 22]
Group 23
('DX', 'DY', 'UX', 'UY', 'UX', 'UY', 'DX', 'DY', 1) Solved+OneFace
('DX', 'DX', 'DY', 'UY', 'UX', 'UX', 'DY', 'UY', 1) Bar/Slash+OneFace
U: [6, 20]
U2: [9, 17]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment