Decompose algorithms in commutator notation

[nbwzx]

Some algorithms in the Rubik's cube may not be too easy to decompose.
For example, actually D F' R U' R' D' R D U R' F R D' R' can be decomposed as D:[F' R U' R',D' R D R'], R' U S' U' S R U' R S R' S' U can be decomposed as [R' U S',U' S R S'].

Recently I made a tool to decompose algorithms in commutator notation.
You can view the website here.

It is mainly based on the following methods.
For an algorithm s in the Rubik's cube, suppose n is the length of s.
Firstly, since c a b a' b' c'=c:[a,b]=[c a c',c b c'], we only need to calculate the case when the first step and the last step of the algorithm cannot be offset.
Secondly, let i from 1 to n, j is the number of length of the i+1 th to nth string that can be offset, k from 1 to i. Let X=the first ith char of s ,Y=the (i+1)th char to the (i+j)th char of s add the (i-k)th char to the (i-1)th char of s.
Thirdly, do some post-processing to make the length of X and Y as small as possible.

Let me explain the second step with the example R' U S' U' S R U' R S R' S' U
In this example, we have i=3 by loop, X=R' U S', in U' S R U' R S R' S' U the first 3 steps and the last 3 steps can be offset, so j=1, and we have k=1 by loop, Y=U' S R S'
After checking, R' U S' U' S R U' R S R' S' U=[R' U S',U' S R S']

Another example U R S R' S' U2 R' S R S' U
We only need to decompose R S R' S' U2 R' S R S' U2 because of the first step.
In this example, we have i=4 by loop, X=R S R' S', in U2 R' S R S' U2 the first 1 step and the last 1 step can be offset, so j=1, and we have k=3 by loop,Y=U2 S R' S'
After checking, U R S R' S' U2 R' S R S' U=U:[R S R' S',U2 S R' S']=U:[R U2,U2 S R' S'] (since [a,b]=[a b',b])

Currently, the time complexity of the main parts (the second step) of this algorithm is O(n^2). It is still unknown if there is a faster algorithm or if this algorithm can detect all possible commutators. But this algorithm seems to perform well after much testing.

 

[qwr]

I did not look at the details of this algorithm, but is this a string problem like palindrome?
Some string problems can be computed quicker with appropriate prefix sum or dynamic programming methods or automata search type algorithms
if I ever get better at such string competition programming problems I'll come back and look at it. You or I may also ask on stack overflow for string algorithm ideas.

 

[nbwzx]

I did not look at the details of this algorithm, but is this a string problem like palindrome?
Some string problems can be computed quicker with appropriate prefix sum or dynamic programming methods or automata search type algorithms
if I ever get better at such string competition programming problems I'll come back and look at it. You or I may also ask on stack overflow for string algorithm ideas.

Yes you are right. Essentially it's a string problem. We can consider this problem in terms of free groups. It consists of all words that can be built from members of S, considering two words to be different unless their equality follows from the group axioms. For algorithms in the Rubik's cube, the additional restriction is that the order is 4, which means U4=identity, F4=identity, etc.

 

[abunickabhi]

Super useful tool. Thanks for the good work nbwzx!

 

[qwr]

Yes you are right. Essentially it's a string problem. We can consider this problem in terms of free groups. It consists of all words that can be built from members of S, considering two words to be different unless their equality follows from the group axioms. For algorithms in the Rubik's cube, the additional restriction is that the order is 4, which means U4=identity, F4=identity, etc.

I do not think it is necessary to consider the string problem in terms of free groups because we do not apply any reductions here (ex. we don't actually need the fact that U U = U2)
I didn't really understand your description but I assume your idea was my first thought which was using two indices i,j on string s of length n such that C = s[0:i], A = s[i:j], B = s[j:n/2]. I believe you can match all C to C' with incrementing i and all AB to A'B' with incrementing i,j with each match in constant time using a rolling hash. This gives us n^2/4 operations for the whole program without actually using any property of alg inverses. I assume this is what you proposed but I did not understand what you meant by offset in first step. You did not mention how you do string matching or how you found C (greedy? I don't think that will work) which I assume is what you mean by offset.

 

[nbwzx]

I do not think it is necessary to consider the string problem in terms of free groups because we do not apply any reductions here (ex. we don't actually need the fact that U U = U2)
I didn't really understand your description but I assume your idea was my first thought which was using two indices i,j on string s of length n such that C = s[0:i], A = s[i:j], B = s[j:n/2]. I believe you can match all C to C' with incrementing i and all AB to A'B' with incrementing i,j with each match in constant time using a rolling hash. This gives us n^2/4 operations for the whole program without actually using any property of alg inverses. I assume this is what you proposed but I did not understand what you meant by offset in first step. You did not mention how you do string matching or how you found C (greedy? I don't think that will work) which I assume is what you mean by offset.

Sorry for my vague statement. English is not my mother tongue.

U2 may mean U U, or may mean U' U' in a Rubik's cube.
U may mean U, or may mean U' U' U' in a Rubik's cube, they may be different in the decomposion.
For example, U M U M' U M' U M=[U M U,M' U U]. However it is actually U M U M' U M' U' U' U' M.

The first step is just finding the C.
For example,
for R U' D' R' U R D R' U' R U R', the first two chars (R U') and the last two chars (U R') can be offset. But the third char is D' and the third to last char is R, they cannot be offset. So C=R U'.

Actually, C doesn't matter at all. R U' D' R' U R D R' U' R U R' is R U':[D',R' U R], but it can also be decompose into [R U' D' U R,R U' R' U R U R] using c a b a' b' c'=c:[a,b]=[c a c',c b c']. C is only used to make A and B short.

Just use A = s[0:j], B = s[j:n/2] can't work in some cases. For example a b c a' b' c'=[a b,c b].

 

[qwr]

Oh I see, you actually want to do reductions (things like cancelling U U'). Then the problem becomes harder.
The reason I said you couldn't take C greedily is because in an string like C A B A' B' C', you would be taking some x from the start of A and x' from the end of B' (also the start of B). But if you allow a simple cancelling rewriting system, since it is a context-free grammar maybe efficient algorithms exist anyway. I will think about it when I am less busy.

 

[nbwzx]

Yes, reductions make this problem not very easy. Looking forward to seeing a better or improved algorithms from you.

 

[qwr]

How many moves are you willing to add to make an alg into a commutator? Is it bounded by a small number?

 

[nbwzx]

How many moves are you willing to add to make an alg into a commutator? Is it bounded by a small number?

What is your meaning of moves in this problem? Does it mean the moves of reductions? If so, I don't know the exact boundary of the reductions. But I guess that the moves of reductions won't be too long.

 

[Luke Solves Cubes]

maths

 

[nbwzx]

I have made lots of updates from Mar 2022 to now (February 2023), the main updates are as follows:
1. Rewrite the code in typescript.
2. Speed up a lot.
3. Support custom order.
4. Support decomposing algorithms in the combo of commutators.
5. Support custom sorting rules.
6. Support two output formats.
7. Beautify the website.
8. Add some tests at https://github.com/nbwzx/commutator/blob/main/test/test.ts
9. fix several bugs.
10. Other minal updates.

For details, see https://github.com/nbwzx/commutator
For core code, see https://github.com/nbwzx/commutator/blob/main/assets/dist/js/commutator.ts
The website: https://zixingwang.cn/commutator

 

[nbwzx]

I made a program to decompose algorithms in commutator notation at https://github.com/nbwzx/commutator.py, a python version of the previous one.