Decompose an algorithm in commutator notation

[nbwzx]

I made a tool to decompose an algorithm in commutator notation these days. It is written in javascript here.

Many 3-cycle and 5-cycle algorithms in a Rubik's cube can be decomposed into commutators.

For example, input U' R U R2 D' R2 U' R' U R2 D R2
It will output:
[U' R U,R2 D' R2]
[U':[R,U R2 D' R2 U']]
[R2:[R2 U' R U R2,D']]

Also, it can decompose an algorithm in the addition of commutators.

For example, input R U' S U2 S R' S2 R U' R'
It will output:
[R U':[S,U2][U2:[S2,R']]]
and other 25 results.

For a cuber, especially a blind-solving cuber, these expressions can make us understand algorithm structure better.

Twizzle is really a comprehensive website, so I want to add this tool to the "Alg Tools" part.

What do you think of this idea?

[rokicki]

In my tests this looks pretty good! Can you let us know what your real name is, and maybe some background? (I like to know who I am working with.)

…

-tom

On Tue, May 10, 2022 at 3:36 AM nbwzx ***@***.***> wrote: I made a tool <https://nbwzx.github.io/commutator> to decompose an algorithm in commutator notation these days. It is written in javascript here <https://github.com/nbwzx/commutator/blob/main/assets/dist/js/cube.js>. Many 3-cycle and 5-cycle algorithms in a Rubik's cube can be decomposed into commutators. For example, input U' R U R2 D' R2 U' R' U R2 D R2 It will output: [U' R U,R2 D' R2] [U':[R,U R2 D' R2 U']] [R2:[R2 U' R U R2,D']] Also, it can decompose an algorithm in the addition of commutators. For example, input R U' S U2 S R' S2 R U' R' It will output: [R U':[S,U2][U2:[S2,R']]] and other 25 results. For a cuber, especially a blind-solving cuber, these expressions can make us understand algorithm structure better. Twizzle <https://alpha.twizzle.net/> is really a comprehensive website, so I want to add this tool to the "Alg Tools" part. What do you think of this idea? — Reply to this email directly, view it on GitHub <#185>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAMOLS4JPGFAHQJ344ETDU3VJI32LANCNFSM5VRECWYQ> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

-- - https://cube20.org/ <http://cube20.org/> - https://golly.sf.net/ <http://golly.sf.net/> - https://experiments.cubing.net/ -

[nbwzx]

Sure, you can know more about me in my personal website.

[lgarron]

Thanks for offering! I was playing around with your site a while back, and it it can certainly produce some useful results.

So, I'd love to see this functionality in Twizzle.

I'd have two main requests:

1. Would you be able to rewrite the implementation using the Alg class? https://js.cubing.net/cubing/alg/ This is important for codebase maintainability, and would also be a great way to exercise the current Alg functionality. I'd be happy to pair on this, and to talk about adding new features to cubing/alg if we find they're needed to support the kinds of calculations in the code.
2. Would you be able to handle bigger cubes or arbitrary puzzles, given a way to calculate the order of any given move? (e.g. "R" has order 5 when working with Megaminx.)

If 2. is too tricky, we can always enable the functionality for only a certain subset of puzzles. (It's alright if it doesn't work for all cases and puzzles, since we're still in alpha.)

[nbwzx]

Thanks. This site is now faster and more powerful than it was in March.

1. Alg class provides many features like invert and simplify, I think that using these features can make my code simpler and compatible. I will see the usage of the alg class and rewrite my code.

2. Bigger cubes or arbitrary puzzles have their specific notations. For example, Megaminx has WCA notations like R++ and D--. It is not as easy as simply changing the order from 4 to 5 in the code. I hope I can make this someday.

[lgarron]

• Alg class provides many features like invert and simplify, I think that using these features can make my code simpler and compatible. I will see the usage of the alg class and rewrite my code.

Good to hear! Let me know how you get on.

• Bigger cubes or arbitrary puzzles have their specific notations. For example, Megaminx has WCA notations like R++ and D--. It is not as easy as simply changing the order from 4 to 5 in the code. I hope I can make this someday.

Fortunately, we have an abstraction that will let you mostly ignore that. But we can worry about this later.

[nbwzx]

I tried using the alg class and I think some of the features need to be added for commutator.

1. For an algorithm r U' R' U M U' R U R', the commutator is R:[M',U' R' U]. To do this, we need to convert r to basic moves R M' during preprocessing first (see here). But this doesn't seem to exist in the code of the alg class.

2. Conversely, on the output I want to write r:[U' R' U,M] if it is R M':[U' R' U,M]. (see here)

3. For an algorithm R' E R U2 R' E' R U2, the commutator is [R' E R,U2]. However, when expanded, it is actually R' E R U2 R' E' R U2'. I saw the corresponding explanation here. But for a Rubik's cube of order 4, we do need U2=U2'. Also, we need to change U3 to U'.

4. I would like the method simplify to support swapping for same-level steps. For example, R M R can be simplified to R2 M (see here), U D' E U' can be simplified to D' E. (see here)

[lgarron]

@nbwcx: Those sound pretty specific to 3x3x3. Do you think you'd be able to write your own functions to provide that functionality until we're ready to generalize to bigger puzzles?
In particular, 4. can probably be generalized to a puzzle-agnostic canonicalization algorithm in the future.

[nbwzx]

My own functions in commutator provide these, but the code in the alg class doesn't seem to provide these functions specifically to 3x3x3. So I faced these problems in rewriting the code about commutator using the alg class. The most studied commutator is for 3x3x3 Rubik's cube with order 4. I am thinking about whether the order can be used as a parameter in alg class, like simplify("R U3",4)=R U' and simplify("R U3",3)=R.

On the other hand, I am thinking about generalizing my code to a puzzle-agnostic canonicalization algorithm these days. Actually, I have already finished the cases for free groups. (see site here and code here)

[rokicki]

Remember, for some puzzles, the order of different moves might be different. I'm impressed that your algorithm is extracting both commutators and conjugations in O(n^2). I'd be happy to give up some generality (i.e., being able to slice and dice the various slice moves vs face moves) in order to get it integrated well. (Note that on the 4x4x4 we have moves such as R, r, 2R, M, and even potentially 3r so generalizing the slicing and dicing of moves might be a bit challenging.)

…

-tom

On Thu, May 12, 2022 at 5:32 AM nbwzx ***@***.***> wrote: My own functions in commutator provide these, but the code in the alg class doesn't seem to provide these functions specifically to 3x3x3. So I faced these problems in rewriting the code about commutator using the alg class. The most studied commutator is for 3x3x3 Rubik's cube with order 4. I am thinking about whether the order can be used as a parameter in alg class, like simplify("R U3",4)=R U' and simplify("R U3",3)=R. On the other hand, I am thinking about generalizing my code to a puzzle-agnostic canonicalization algorithm these days. Actually, I have already finished the cases for free groups. (see site here <https://nbwzx.github.io/commutator/free.html> and code here <https://github.com/nbwzx/commutator/blob/main/assets/dist/js/free.js>) — Reply to this email directly, view it on GitHub <#185 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAMOLSYUHRXOA7VYGMBT2ALVJT26JANCNFSM5VRECWYQ> . You are receiving this because you commented.Message ID: <cubing/cubing. ***@***.***>

-- - https://cube20.org/ <http://cube20.org/> - https://golly.sf.net/ <http://golly.sf.net/> - https://experiments.cubing.net/ -

[nbwzx]

Thanks for offering! I was playing around with your site a while back, and it it can certainly produce some useful results.

So, I'd love to see this functionality in Twizzle.

I'd have two main requests:

1. Would you be able to rewrite the implementation using the Alg class? https://js.cubing.net/cubing/alg/ This is important for codebase maintainability, and would also be a great way to exercise the current Alg functionality. I'd be happy to pair on this, and to talk about adding new features to cubing/alg if we find they're needed to support the kinds of calculations in the code.
2. Would you be able to handle bigger cubes or arbitrary puzzles, given a way to calculate the order of any given move? (e.g. "R" has order 5 when working with Megaminx.)

If 2. is too tricky, we can always enable the functionality for only a certain subset of puzzles. (It's alright if it doesn't work for all cases and puzzles, since we're still in alpha.)

Now, I have generalized my algorithm to cases of any given order (See site and source code) (i.e. the request 2)
For example, input: a b4 c b a' b2' c' b3' (a puzzle-agnostic canonicalization algorithm)
The output is as follows for different orders:

order	commutator
1	Empty input.
2	[a c,b a]
3	[a b,c b']
4	a:[c b,a' b']
5	[a b,b2' c b2]
6 or more	[a b,b3 c b2]

You can check it by expanding.

[nbwzx]

I tried to contact @lgarron , but no response. I just want to talk in more detail about commutators so that we can get on this enhancement.

[lgarron]

I tried to contact @lgarron , but no response. I just want to talk in more detail about commutators so that we can get on this enhancement.

Apologies, email is kind of an inconsistent way to reach me right now. 😬

Unfortunately, it would take me quite some work to see how we could integrate your algorithms into our code, since your implementation is still heavily based on algorithms as strings. I'm definitely interested, but I don't think I could promise to invest time particularly soon. 😕

[nbwzx]

Actually, I convert string to array first and the main part is based on array. For example, [[ 'R', 1 ], [ 'U', 1 ], [ 'R', -1 ], [ 'U', -1 ]] for R U R' U'. Array is better to handle than string.

[nbwzx]

And I have integrate my algorithms into https://blddb.net. It is not difficult to import and use.

[nbwzx]

I have rewrote commutator in typescript. See here.