Created
August 18, 2018 14:07
-
-
Save hynekcer/98776d7486fd42336a95c272b2844671 to your computer and use it in GitHub Desktop.
Max estimated number of states of Rubik's Cube after N quarter-turn moves (Czech)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
Horní odhad počtu stavů Rubikovy kostky po N tazích typu čtvrt-obrátka | |
# https://sciencemag.cz/umela-inteligence-se-sama-naucila-slozit-rubikovu-kostku/#post-3981572954 | |
Počty stavů po daném počtu tahů v jedné ze tří rovin | |
O: - 0 | |
1: L l R r 4 | |
2: LL LR Lr lR lr RR 6 | |
3: LLR LLr LRR lRR 4 | |
4: LLRR 1 | |
celkem 4 * 4 - 1 možných nových stavů | |
""" | |
# počty stavů při po sobě jdoucích rotacích okolo jedné osy | |
mul = [0, 4, 6, 4, 1] | |
N = 20 | |
NN = N + 1 | |
# st[pocet_ruznych_po_sobe_jdoucich_os_rotace][pocet_kroku] | |
# prázdné pole [0..20][0..20] | |
st = [[0 for j in range(NN)] for i in range(NN)] | |
st[0][0] = 1 | |
for i in range(N): | |
for j in range(NN): | |
for k in range(len(mul)): | |
if j + k <= N: | |
# na začátku vyberu kteroukoli ze tří os, při změně se volí ze dvou os | |
st[i + 1][j + k] += st[i][j] * mul[k] * (2 if i > 0 else 3) | |
# tisk výsledků | |
for row in st: | |
print(row) | |
ss = 0 | |
print() | |
last_s = 1. | |
for j in range(NN): | |
xs = sum(st[i][j] for i in range(NN)) | |
ss += xs | |
print(xs, ss, ss / last_s) | |
last_s = ss | |
print() | |
print(float(ss)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment