In a prior notebook we remarked on the surprising fact that if any sequence of moves is applied to a solved Rubik's Cube, eventually the cube will cycle through a fixed number of positions and will return to the solved state. How many times the sequence must be applied ranges from 1 to tens of thousands. In this notebook, we investigate the number of times different sequences must be applied to reach the solved state again.
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
import json, os, re
from pprint import pprint
%matplotlib inline
We start by analyzing sequences that are 2 moves long.
As a reminder of the notation:
Start by loading the results from the cycle count program for sequences of 2 moves:
with open('sequence2.json','r') as f:
s2 = json.load(f)
print("Sequence\tCross Cycle Count\tCenter Cycle Count\tTotal Cycle Count")
for seq in s2:
print("%s \t\t %-6d \t\t %-6d \t\t %-6d"%(seq,*s2[seq]))
fig = plt.figure(figsize=(12,4))
ax1, ax2 = [fig.add_subplot(1,2,i+1) for i in range(2)]
for seq in s2:
ax1.plot([0,1], [s2[seq][0], s2[seq][2]], 'o-')
ax2.plot([0,1], [s2[seq][1], s2[seq][2]], 'o-')
ax1.set_title("Cross Cycle Count vs Total Cycle Count")
ax2.set_title("Center Cycle Count vs Total Cycle Count")
plt.show()
In calculating these rotations, we eliminated duplicate rotations, so we also include the get_rotations()
method to get those duplicate rotations back:
from rotations import get_rotations
The get_rotations()
method allows us to pass in a sequence of moves that starts with U, 2U, or Uw, and get back five additional sequences starting with D, B, F, L, R. For example:
print("Rotations of %s:"%(list(s2.keys())[0]))
print(get_rotations(list(s2.keys())[0]))
The dictionary s2
contains the main quantity of interest: we have a set of 2-move sequences, and the corresponding number of times the sequence must be applied to a solved cube to return the cube back to its solved state.
Now, we know that when applying a sequence of moves repeatedly to a solved cube, the cube will eventually return to the solved state. However, in between, the cube will also pass through a number of intermediate states, some more solved than others.
While we were repeatedly applying the sequence to the cube, we were also counting the number of cycles between the cube's crosses and centers returning to a solved state. This information is also contained in the dictionary s2
.
unique_rotations = list(s2.keys())
crosses = {}
centers = {}
cycles = {}
for rot in unique_rotations:
val = s2[rot]
crosses[rot] = val[0]
centers[rot] = val[1]
cycles[rot] = val[2]
Start by printing the number of unique 2 sequences that we have (note that these are all sequences that begin with U, 2U, or Uw):
print("Number of rotationally unique 2-sequences: %d"%( len(crosses.keys())) )
We count the number of unique values of the cross cycle counts and center cycle counts, in addition to the number of unique total cycle counts:
print("Number of unique crosses cycle counts: %d"%( len(set(crosses.values()))) )
print("Number of unique center cycle counts: %d"%( len(set(centers.values()))) )
print("Number of unique cycle counts: %d"%( len(set(cycles.values()))) )
We can also count the number of unique triplets: (cross cycles, center cycles, total cycles)
values = list(s2.values())
values_as_strings = [' '.join([str(v) for v in val]) for val in values]
print("Number of unique crosses-centers-cycles tuples: %d"%( len(set(values_as_strings))) )
We have a set of rotationally unique 2-move sequences, but we're interested in all 2-move sequences. Our next step is to count the number of rotational variations a particular 2-move sequence has. This uses the get_rotations()
method we imported above:
for rot in unique_rotations:
print("For sequence %s, number of rotations is %d"%(rot,len(get_rotations(rot))))
print(get_rotations(rot))
print("")
Notice that sequences with 6 rotations are sequences in which the order of the moves are independent - that is, each move in the sequence either modifies a completely independent face (such as U D or Uw D or D 2U) or each move in the sequence modifies the same face (such as Uw U or U U or 2U U).
The sequences with 24 rotations are sequences that modify two different faces in such a way that the moves are not independent, and the order of the moves mattters.
seq6 = []
seq24 = []
for rot in unique_rotations:
if(len(get_rotations(rot))==6):
seq6.append(rot)
else:
seq24.append(rot)
print("2-move sequences with 6 rotational variants: %d"%(len(seq6)))
print("2-move sequences with 24 rotational variants: %d"%(len(seq24)))
Here, the number of 2-move sequences that have 6 rotational variants outnumber the 2-move sequences that have 24 rotational variants. We will see this balance change as the sequences get longer - longer sequences result in many more sequences that mix faces together, so there are many more sequences with 24 rotational variants.
If we have a sequence of moves that modify separate faces, we are bound to have a sequence with a maximum cycle length of 4. That's exactly what we see: for sequences applying rotations to faces independently, the total cycle length is bound to be 2 or 4.
print([s2[seq][2] for seq in seq6])
The number of times the sequence needs to be applied gets longer once the faces become mixed up:
print([s2[seq][2] for seq in seq24])
Let's investigate the relationship between the sequences that have similar cycle lengths.
We can see that, of the sequences that mix faces, the sequences with the shortest cycle lengths involve one face layer and one second-layer:
def seq_cycle_len(n):
print([seq for seq in s2.keys() if s2[seq][2]==n])
seq_cycle_len(20)
Sequences that involve two face layers and one second-layer are the next shortest:
seq_cycle_len(80)
And longest are sequences involving two face layers and another face layer.
seq_cycle_len(240)
240/20
240/80
The two sequences that have unique cycle counts, but cycle counts that are related by a factor of 10, are also similar. Of the two sequences, the longer involves one-layer turns, while the shorter involves two double-layer turns.
seq_cycle_len(105)
seq_cycle_len(15)
Last is the sequence involving two second-layer turns:
seq_cycle_len(28)
Let's move on to 3-move sequences and see how much of these rules hold for those.
with open('sequence3.json','r') as f:
s3 = json.load(f)
print(len(s3.keys()))
unique_rotations3 = list(s3.keys())
crosses = {}
centers = {}
cycles = {}
for rot in unique_rotations3:
val = s3[rot]
crosses[rot] = val[0]
centers[rot] = val[1]
cycles[rot] = val[2]
print("Number of rotationally unique 3-cycles: %d"%( len(unique_rotations3)) )
print("Number of unique crosses cycle counts: %d"%( len(set(crosses.values()))) )
print("Number of unique center cycle counts: %d"%( len(set(centers.values()))) )
print("Number of unique cycle counts: %d"%( len(set(cycles.values()))) )
values = list(s3.values())
values_as_strings = [' '.join([str(v) for v in val]) for val in values]
print("Number of unique crosses-centers-cycles tuples: %d"%( len(set(values_as_strings))) )
fig = plt.figure(figsize=(12,4))
ax1, ax2 = [fig.add_subplot(1,2,i+1) for i in range(2)]
for seq in s3:
ax1.plot([0,1], [s3[seq][0], s3[seq][2]], 'o-', alpha=0.5)
ax2.plot([0,1], [s3[seq][1], s3[seq][2]], 'o-', alpha=0.5)
ax1.set_title("Cross Cycle Count vs Total Cycle Count")
ax2.set_title("Center Cycle Count vs Total Cycle Count")
plt.show()
Now let's count the number of duplicate rotations we have for each sequence.
nrots = set()
for rot in unique_rotations3:
nrots.add( len(get_rotations(rot)) )
print(nrots)
seq6 = []
seq24 = []
for rot in unique_rotations3:
if(len(get_rotations(rot))==6):
seq6.append(rot)
else:
seq24.append(rot)
print("2-move sequences with 6 rotational variants: %d"%(len(seq6)))
print("2-move sequences with 24 rotational variants: %d"%(len(seq24)))
print(seq6[0:10])
print(seq24[0:10])
Just like the 2-move sequqences, we see that all of the 3-move sequences that have only 6 rotations are composed entirely moves of opposite faces (U and D, B and F, or L and R). The number of 3-move sequences that have 6 rotational variations is only 1/3 of all sequences. Recall the number of 2-move sequences that had 6 rotational variations was 2/3 of all sequences.
As we saw before, sequences that rotate the same or independent faces must, by definition, take only 2 or 4 total rotations. We see this if we examine the total number of sequences that bring a solved cube back to its solved state, for 3-move sequences. If the sequence has 6 rotational variations, it is bound to have a cycle length of 2 or 4:
seq6lengths = [s3[seq][2] for seq in seq6]
seq6lengths = sorted(list(set(seq6lengths)))
print(seq6lengths)
Meanwhile, cycle lengths for sequences that mix faces in their rotations have a much wider range of sequence lengths:
seq24lengths = [s3[seq][2] for seq in seq24]
seq24lengths = sorted(list(set(seq24lengths)))
print(seq24lengths)
def factor(n):
fact=[1,n]
check=2
rootn=np.sqrt(n)
while check<rootn:
if n%check==0:
fact.append(check)
fact.append(n//check)
check+=1
if rootn==check:
fact.append(check)
fact.sort()
return fact
from sympy.ntheory import factorint
print("Sequence Degree\t\tPrime Factorization of Degree")
for m in seq24lengths:
factors = factorint(m)
factorpows = ["%d^%d"%(i, factors[i]) if factors[i]>1 else "%d"%(i) for i in factors.keys()]
print("%d \t\t\t%s"%( m, '*'.join(factorpows) ))
If we examine the cycle lengths and find numbers that are paired by being factors or multiples of one another, we find some curious patterns.
Take, for example, the pair 1155 and 15, which are related through the number 77:
1155/15
Now if we look at the sequences that have cycle lengths of 1155 and 15, we see a pattern:
def seq_cycle_len3(n):
print([seq for seq in s3.keys() if s3[seq][2]==n])
seq_cycle_len3(1155)
seq_cycle_len3(15)
The sequences with a cycle length of 1155 have one move that changes a single face layer, one move that changes a second face layer, and one move that changes two face layers at once.
The sequences with a cycle length of 15 have one move that changes a single face layer, one move that changes a second face layer, and one move that changes two face layers at once.
We can find other pairs like this, and check whether they follow the same pattern:
6270/15
seq_cycle_len3(6270)
seq_cycle_len3(15)
Again, we see that sequences with longer and shorter cycles are related: sequences with a cycle length of 6270 have a two two-layer moves and a second-layer move, while sequences with a cycle length of 15 have a two-layer move, a second-layer move, and a single-layer face move.
Finding more pairs:
factors = sorted(list(set(seq24lengths)))
for f in reversed(factors):
for f2 in reversed(factors):
if(f%f2==0 and f//f2 in factors):
print("%d / %d = %d"%(f, f2, f//f2))
840/84
seq_cycle_len3(840)
seq_cycle_len3(84)
seq_cycle_len3(10)
Sequences with a cycle length of 840 have two two-layer moves and a second-layer move, while sequences with a cycle length of 10 have three two-layer moves.
840/30
seq_cycle_len3(840)
seq_cycle_len3(30)
seq_cycle_len3(28)
120/6
seq_cycle_len3(120)
seq_cycle_len3(6)
seq_cycle_len3(20)
This happens again with sequenes of cycle length 120 and 6. We can see the shorter sequence of moves with a cycle of 6 is the sequence Uw R Uw; changing the last move from Uw to 2U changes the cycle length to 120. Sequences consisting of two or three double-layer moves and having a cycle length of 6 can be changed to a cycle length of 120 by changing one of its double-layer moves to a second-layer move.
Admittedly, this is all speculative, but it indicates that there may be some underlying system that will help us compute the cycle length for a given sequence, or relate changes in the sequence to changes in the factors of the cycle lenth.
If we look at sequences that are seemingly, but not quite, the same, we see some surprising differences as the sequence plays out.
print(s3['U R F'][2])
print(s3['U R B'][2])
We also notice the curious pattern along the way: swapping modifiers (w or 2) between the first and last moves, when the first and last moves are U and F or B, gives identical cycle lengths:
print(s3['U R Fw'][2])
print(s3['U R Bw'][2])
print(s3['Uw R F'][2])
print(s3['Uw R B'][2])
Again with a different sequence:
print(s3['U Rw Fw'][2])
print(s3['U Rw Bw'][2])
print(s3['Uw Rw F'][2])
print(s3['Uw Rw B'][2])
And another:
print(s3['U Rw 2F'][2])
print(s3['U Rw 2B'][2])
print(s3['2U Rw F'][2])
print(s3['2U Rw B'][2])
Note that all of these sequences begin with U, and some aren't included. That's because we've eliminated all of the duplicate rotations from the list of sequences, which saves a lot of space but means we have to do extra work to look up all sequences.
try:
print(s3['2U 2B F'][2])
print(s3['2U 2B B'][2])
except KeyError:
print("Error")
#pprint(sorted(list(s3.keys())))
reverse_rot = {}
for rot in unique_rotations3:
ar = get_rotations(rot)
for a in ar:
reverse_rot[a] = rot
Now we have the reverse lookup table reverse_rot
, which allows us to pass in an arbitrary location and look up the correct corresponding key in unique_rotations
that starts with U, 2U, or Uw.
def print_rev(seq):
k = reverse_rot[seq]
print(s3[k][2])
print_rev('2U 2B F')
print_rev('2U 2B B')
print_rev('D 2B F')
print_rev('D 2B B')
print_rev('L 2B F')
print_rev('L 2B B')
print_rev('F 2B F')
print_rev('F 2B B')
We also see some patterns when we reverse the face in the second sequence: the cycle lengths reverse too, depending on whether the cycle ends in F or B:
print_rev('2U 2L F')
print_rev('2U 2L B')
print_rev('2U 2R F')
print_rev('2U 2R B')
print_rev('Dw 2R F')
print_rev('Dw 2L B')
The pattern is, if you change the face the last move acts on to the opposite face (e.g., R to L), then you can also change the face that the second to last move acts on to the opposite face (e.g., U to D) and the number of cycles stays the same.
print_rev('2F 2U R')
print_rev('2F 2D L')
print_rev('2F 2U L')
print_rev('2F 2D R')
print_rev('2U Bw F')
print_rev('2U Fw B')
print_rev('2R Fw F')
print_rev('2R Bw B')
print_rev('Rw Fw F')
print_rev('Rw Bw B')
Some interesting behaviors - each characteristic we've investigated (and we could keep finding more) creates additional groups, or ways of categorizing different cubies, configurations, sequences, and cubies.
Ultimately, getting at the underlying pattern will require a way of representing the cube as an n-tuple, and abstracting the transformations of the cube and its permutations into an algebra, with operators, transofrmations, etc.
(Example: rotations are complete, because the groups that existed before are still there after.)
with open('sequence4.json','r') as f:
s4 = json.load(f)
print(len(s4.keys()))
As before, we load the total number of cycle counts, cross cycle counts, and center cycle counts, and print out the number of unique integers we see there.
unique_rotations = list(s4.keys())
crosses = {}
centers = {}
cycles = {}
for rot in unique_rotations:
val = s4[rot]
crosses[rot] = val[0]
centers[rot] = val[1]
cycles[rot] = val[2]
print("Number of rotationally unique 4-sequences: %d"%( len(unique_rotations)) )
print("")
print("Number of unique crosses cycle counts: %d"%( len(set(crosses.values()))) )
print("Number of unique center cycle counts: %d"%( len(set(centers.values()))) )
print("Number of unique cycle counts: %d"%( len(set(cycles.values()))) )
values = list(s4.values())
values_as_strings = [' '.join([str(v) for v in val]) for val in values]
print("Number of unique crosses-centers-cycles tuples: %d"%( len(set(values_as_strings))) )
fig = plt.figure(figsize=(12,4))
ax1, ax2 = [fig.add_subplot(1,2,i+1) for i in range(2)]
maxx = 500
for i, seq in enumerate(s4):
if(i>maxx):
break
ax1.plot([0,1], [s4[seq][0], s4[seq][2]], 'o-', alpha=0.5)
ax2.plot([0,1], [s4[seq][1], s4[seq][2]], 'o-', alpha=0.5)
ax1.set_title("Cross Cycle Count vs Total Cycle Count")
ax2.set_title("Center Cycle Count vs Total Cycle Count")
plt.show()
nrots = set()
for rot in unique_rotations:
nrots.add( len(get_rotations(rot)) )
print(nrots)
seq6 = []
seq24 = []
for rot in unique_rotations:
if(len(get_rotations(rot))==6):
seq6.append(rot)
else:
seq24.append(rot)
print("2-move sequences with 6 rotational variants: %d"%(len(seq6)))
print("2-move sequences with 24 rotational variants: %d"%(len(seq24)))
seq6lengths = [s4[seq][2] for seq in seq6]
seq6lengths = sorted(list(set(seq6lengths)))
print(seq6lengths)
print("Length: %d"%(len(seq6lengths)))
seq24lengths = [s4[seq][2] for seq in seq24]
seq24lengths = sorted(list(set(seq24lengths)))
print(seq24lengths)
print("Length: %d"%(len(seq24lengths)))
print("Sequence Degree\t\tPrime Factorization of Degree")
for m in seq24lengths:
factors = factorint(m)
factorpows = ["%d^%d"%(i, factors[i]) if factors[i]>1 else "%d"%(i) for i in factors.keys()]
print("%d \t\t\t%s"%( m, '*'.join(factorpows) ))
def seq_cycle_len4(n):
print([seq for seq in s4.keys() if s4[seq][2]==n])
n = 2*2*3*17
ns = '2*2*3*17'
print("%d = %s"%(n, ns))
seq_cycle_len4(n)
print("")
n = 3*5*17 # 255
ns = '3*5*17'
print("%d = %s"%(n, ns))
seq_cycle_len4(n)
print("")
n = 2*3*5*17 # 510
ns = '2*3*5*17'
print("%d = %s"%(n, ns))
seq_cycle_len4(n)
print("")
n = 2*2*3*5*17 # 1020
ns = '2*2*3*5*17'
print("%d = %s"%(n, ns))
seq_cycle_len4(n)
print("")
n = 2*2*2*2*3*5*17 # 4080
ns = '2*2*2*2*3*5*17'
print("%d = %s"%(n, ns))
seq_cycle_len4(n)
print("")
print("Sequence\t\tSequence Degree\t\tPrime Factorization of Degree")
for seq in s4:
if('R Uw R' in seq):
m = s4[seq][2]
factors = factorint(m)
factorpows = ["%d^%d"%(i, factors[i]) if factors[i]>1 else "%d"%(i) for i in factors.keys()]
print("%-20s \t%d \t\t\t%s"%( seq, m, '*'.join(factorpows) ))
print("Sequence\t\tSequence Degree\t\tPrime Factorization of Degree")
for seq in s4:
if('R U R' in seq):
m = s4[seq][2]
factors = factorint(m)
factorpows = ["%d^%d"%(i, factors[i]) if factors[i]>1 else "%d"%(i) for i in factors.keys()]
print("%-20s \t%d \t\t\t%s"%( seq, m, '*'.join(factorpows) ))
print("Sequence\t\tSequence Degree\t\tPrime Factorization of Degree")
for seq in s4:
if('Rw U R' in seq):
m = s4[seq][2]
factors = factorint(m)
factorpows = ["%d^%d"%(i, factors[i]) if factors[i]>1 else "%d"%(i) for i in factors.keys()]
print("%-20s \t%d \t\t\t%s"%( seq, m, '*'.join(factorpows) ))
print("Sequence\t\tSequence Degree\t\tPrime Factorization of Degree")
for seq in s2:
if('Uw Rw' in seq or 'U R' in seq and '2' not in seq):
m = s2[seq][2]
factors = factorint(m)
factorpows = ["%d^%d"%(i, factors[i]) if factors[i]>1 else "%d"%(i) for i in factors.keys()]
print("%-20s \t%d \t\t\t%s"%( seq, m, '*'.join(factorpows) ))
print("Sequence\t\tSequence Degree\t\tPrime Factorization of Degree")
for seq in s2:
if('U R' in seq and '2' not in seq):
m = s2[seq][2]
factors = factorint(m)
factorpows = ["%d^%d"%(i, factors[i]) if factors[i]>1 else "%d"%(i) for i in factors.keys()]
print("%-20s \t%d \t\t\t%s"%( seq, m, '*'.join(factorpows) ))
print("-"*20)
print("Sequence\t\tSequence Degree\t\tPrime Factorization of Degree")
for seq in s4:
if('U R' in seq and '2' not in seq):
m = s4[seq][2]
factors = factorint(m)
factorpows = ["%d^%d"%(i, factors[i]) if factors[i]>1 else "%d"%(i) for i in factors.keys()]
print("%-20s \t%d \t\t\t%s"%( seq, m, '*'.join(factorpows) ))