Skip to content

Instantly share code, notes, and snippets.

@kusano
Created March 8, 2025 16:53
Show Gist options
  • Save kusano/9203c239a250a60d7d5d5c40b6fc196a to your computer and use it in GitHub Desktop.
Save kusano/9203c239a250a60d7d5d5c40b6fc196a 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'),
}
# U/D, F/Bの状態で初期のグループ化。
G = {}
A = []
for s in S:
a = analyse(s)
if a not in A:
A += [a]
G[s] = A.index(a)
gn = len(A)
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)
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])
U2 = set()
for p in permutations(range(4)):
s2 = list(s)
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])
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)
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])
for p in permutations(range(4)):
s2 = list(s)
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])
print(s, analyse(s))
U = sorted(list(U))
U2 = sorted(list(U2))
print(f"U: {U}")
print(f"U2: {U2}")
print()
Group 0
('DX', 'DX', 'UX', 'UY', 'DY', 'UX', 'DY', 'UY') Bars+OneBar
('DX', 'DX', 'UX', 'UY', 'DY', 'UY', 'UX', 'DY') Bars+OneBar
U: [1, 15, 24, 25, 31, 32]
U2: [0, 13, 14]
Group 1
('DX', 'DX', 'DY', 'UY', 'DY', 'UX', 'UX', 'UY') Bar/Slash+Bars
('DX', 'DX', 'DY', 'UY', 'UX', 'UY', 'DY', 'UX') Bar/Slash+Bars
U: [0, 3, 4, 14, 24, 26]
U2: [1, 15, 16]
Group 2
('DX', 'DY', 'UX', 'UY', 'UY', 'UX', 'DY', 'DX') Solved+OneFace
U: [9, 10, 30]
U2: [18, 19, 20]
Group 3
('DX', 'DX', 'DY', 'UX', 'DY', 'UY', 'UX', 'UY') Bar/Slash+OneBar
U: [1, 16, 35, 36]
U2: [24, 25]
Group 4
('DX', 'DX', 'DY', 'UY', 'DY', 'UY', 'UX', 'UX') Bar/Slash+OneFace
U: [1, 4, 34]
U2: [4, 26, 27]
Group 5
('DX', 'DX', 'UX', 'UX', 'UY', 'UY', 'DY', 'DY') Solved+Solved
U: [7, 21]
U2: [5, 28]
Group 6
('DX', 'DX', 'DY', 'DY', 'UX', 'UX', 'UY', 'UY') Slashes+OneFace
U: [28, 33]
U2: [6, 29]
Group 7
('DX', 'DY', 'UX', 'UY', 'DX', 'UY', 'UX', 'DY') Bars+OneFace
U: [5, 15, 16, 28]
U2: [7, 30]
Group 8
('DX', 'DX', 'UX', 'UY', 'DY', 'DY', 'UY', 'UX') Solved+OneBar
U: [11, 34]
U2: [31, 32]
Group 9
('DX', 'DY', 'UX', 'UY', 'UX', 'UY', 'DY', 'DX') Solved+Bars
U: [2, 13, 14, 20]
U2: [9, 33]
Group 10
('DX', 'DX', 'UY', 'UY', 'DY', 'UX', 'DY', 'UX') Bars+Bars
U: [2, 18, 22, 37]
U2: [10]
Group 11
('DX', 'DX', 'DY', 'DY', 'UX', 'UY', 'UX', 'UY') Slashes+Bars
U: [8, 18, 19, 31]
U2: [11]
Group 12
('DX', 'DX', 'UX', 'UX', 'DY', 'UY', 'DY', 'UY') Bars+Solved
U: [18, 20, 26, 27]
U2: [12]
Group 13
('DX', 'DX', 'UX', 'UY', 'DY', 'UX', 'UY', 'DY') Bars+OneBar
U: [9, 24, 25, 33]
U2: [0, 14]
Group 14
('DX', 'DX', 'UX', 'UY', 'DY', 'UY', 'DY', 'UX') Bars+OneBar
U: [1, 9, 15, 33]
U2: [0, 13]
Group 15
('DX', 'DX', 'DY', 'UY', 'UX', 'UY', 'UX', 'DY') Bar/Slash+Bars
U: [0, 7, 14, 30]
U2: [1, 16]
Group 16
('DX', 'DX', 'DY', 'UY', 'DY', 'UX', 'UY', 'UX') Bar/Slash+Bars
U: [3, 7, 24, 30]
U2: [1, 15]
Group 17
('DX', 'DX', 'UY', 'UY', 'DY', 'DY', 'UX', 'UX') Solved+OneFace
U: [29, 35]
U2: [17, 21]
Group 18
('DX', 'DY', 'UX', 'UY', 'DX', 'DY', 'UX', 'UY') Solved+OneFace
U: [10, 11, 12]
U2: [2, 19, 20]
Group 19
('DX', 'DY', 'UX', 'UY', 'DY', 'DX', 'UY', 'UX') Solved+OneFace
U: [11, 30, 36]
U2: [2, 18, 20]
Group 20
('DX', 'DY', 'UX', 'UY', 'UX', 'UY', 'DX', 'DY') Solved+OneFace
U: [9, 12, 36]
U2: [2, 18, 19]
Group 21
('DX', 'DX', 'UY', 'UY', 'UX', 'UX', 'DY', 'DY') Solved+OneFace
U: [5, 35]
U2: [17, 21]
Group 22
('DX', 'DX', 'DY', 'UX', 'UY', 'UY', 'UX', 'DY') Bar/Slash+OneBar
U: [10, 34]
U2: [23, 37]
Group 23
('DX', 'DX', 'DY', 'UX', 'DY', 'UX', 'UY', 'UY') Bar/Slash+OneBar
U: [23, 24, 34]
U2: [22, 23, 37]
Group 24
('DX', 'DX', 'DY', 'UX', 'UX', 'UY', 'DY', 'UY') Bar/Slash+OneBar
('DX', 'DX', 'DY', 'UX', 'DY', 'UY', 'UY', 'UX') Bar/Slash+OneBar
U: [0, 1, 13, 16, 23, 37]
U2: [3, 24, 25]
Group 25
('DX', 'DX', 'DY', 'UX', 'UX', 'UY', 'UY', 'DY') Bar/Slash+OneBar
U: [0, 13, 35, 36]
U2: [3, 24]
Group 26
('DX', 'DX', 'DY', 'UY', 'UX', 'UX', 'DY', 'UY') Bar/Slash+OneFace
U: [1, 12]
U2: [4, 27]
Group 27
('DX', 'DX', 'DY', 'UY', 'UX', 'UX', 'UY', 'DY') Bar/Slash+OneFace
U: [12, 34]
U2: [4, 26]
Group 28
('DX', 'DX', 'UX', 'UX', 'DY', 'DY', 'UY', 'UY') Solved+Solved
U: [6, 7]
U2: [5, 28]
Group 29
('DX', 'DX', 'DY', 'DY', 'UY', 'UY', 'UX', 'UX') Slashes+OneFace
U: [17, 33]
U2: [6, 29]
Group 30
('DX', 'DY', 'UX', 'UY', 'DY', 'UX', 'UY', 'DX') Bars+OneFace
U: [2, 15, 16, 19]
U2: [7, 30]
Group 31
('DX', 'DX', 'UX', 'UY', 'DY', 'DY', 'UX', 'UY') Solved+OneBar
U: [0, 11]
U2: [8, 32]
Group 32
('DX', 'DX', 'UX', 'UY', 'UX', 'UY', 'DY', 'DY') Solved+OneBar
U: [0, 32, 34]
U2: [8, 31, 32]
Group 33
('DX', 'DY', 'UX', 'UY', 'DX', 'DY', 'UY', 'UX') Solved+Bars
U: [6, 13, 14, 29]
U2: [9, 33]
Group 34
('DX', 'DY', 'UX', 'UY', 'DX', 'UX', 'UY', 'DY') Bars+Bars
('DX', 'DY', 'UX', 'UY', 'DX', 'UY', 'DY', 'UX') Bars+Bars
U: [4, 8, 22, 23, 27, 32]
U2: [34]
Group 35
('DX', 'DY', 'UX', 'UY', 'DX', 'UX', 'DY', 'UY') Bars+Bars
U: [3, 17, 21, 25]
U2: [35, 36]
Group 36
('DX', 'DY', 'UX', 'UY', 'DY', 'UY', 'DX', 'UX') Bars+Bars
U: [3, 19, 20, 25]
U2: [35, 36]
Group 37
('DX', 'DX', 'DY', 'UX', 'UY', 'UY', 'DY', 'UX') Bar/Slash+OneBar
U: [10, 24]
U2: [22, 23]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment