Hacker News Reader

Comment by throwaway81523 | Hacker News Reader

This is neat, though it's from 2012 or maybe earlier.

I wonder if there is a single not-too-long rotation sequence that generates the whole cube group. That is, a sequence XYZ that you can perform repeatedly and have that bring you through every cube state. If not, maybe there is some other very simple algorithm that traverses all the states, instead of a zip file that uncompresses to 200MB.

View on HN

If there were a single element that generated the whole group, the group would be abelian.

I think we can go even further than that? If a single element generates the whole group, doesn't that mean the group is cyclic?

But the question here is not looking for a generator, because it would be okay if some group elements are only reached during the application of the sequence. (For the sequence to be a generator, all group elements need to be reached at the end of some full application of the sequence.)

The Hamiltonian cycle sequence from the original post is not a generator, but it visits every state. The question is: Is there a significantly shorter sequence that (when repeated) does the same?

We can give a concrete example that non-Abelian groups can satisfy this with S_3, which is the smallest non-Abelian group. Swap the first two elements; then swap the last two. Repeat three times. You get the sequence

123, 213, 231, 321, 312, 132, 123

Wikipedia (citing a book on archive.org but no page number) [1] claims the largest order of an element of the Rubik's cube group is only 1260, so the simple repetition strategy would have to have a repeated unit way too long to be practical. (It sounds like you could potentially get a longer sequence if you allow "rotating the cube" as a move vs just turning the sides, though probably not enough to matter)

The linked circuit does have a repeating pattern like this at its core, and visits entire cosets of a subgroup at a time (presumably the same way each time) so it seems like there's already a bit more structure than a random 200MB file.

https://en.wikipedia.org/wiki/Rubik%27s_Cube_group#Group_str...

A bogosort for Rubik's cubes would be excellent. Especially if someone makes a robot.

This is up there in "performance art" because the robot would take forever. Mitsubishi apparently has a robot that can do a normal cube solve in ~0.3 seconds (https://www.livescience.com/technology/robotics/this-ai-powe...), which they developed to show off their precision manufacturing. They mention one run that did 15 moves in 0.204 seconds. At that rate it works out to ~19 billion years to run through all positions.

Don’t forget leap years! What’s 18.6 billion years between friends?

I’m sure they could make it go faster but I suspect the reason the robot works at this speed is the friction in the cube only raises the temperature a few degrees before the cube settles and can cool down. And pausing for 60 milliseconds so the human eye has time to register the cube positions probably doesn’t suffice.

You could probably get it down to a billion years without reducing it to just a blur. A couple million if you point a bunch of high speed cameras at it and show the last fifty moves on screens next to the machine. Or 30 machines all showing 1/30th of the cycle.

you mean you want the algorithm that generated the 200MB explicit recipe?

wouldn't that be the very paper that's shared as article here?

No I want a much simpler algorithm, with just a few bits of state, say.

Reply on news.ycombinator.com