Enumerating rotors?

[praosylen]

It occurred to me that it should be possible to enumerate all rotors fitting inside a specific box. A program could exhaustively enumerate all patterns within a (small) (M+2)x(N+2) box, taking the outer edge to be composed entirely of stator cells, and run each one until the stator is necessarily breached or the pattern has evolved into an oscillator. It would then check to ensure that the stator cells could be supported by further casing, and identify the pattern as a viable MxN rotor if so. I would roughly estimate that 4x4 and even 4x5 would be well within reach, and 4x6, 5x5, and maybe 4x7 within reach of a small-to-medium distributed search. Has this already been done, for CGoL or otherwise? Would all of these rotors have already been found with dr? I doubt that there's any surprise small p19 hiding in there, but would it still be worthwhile to try?

[velcrorex]

I don't have any great insights, but I've been thinking about this problem. I'm not entirely convinced that dr can find all such patterns. I do think 4x4 should be manageable, but I don't know how best to deal with the stator cells. Efficiency there will help speed things up tremendously. When searching for oscillators in WLS I have to have two layers of stator cells to make sure I get a valid oscillator. With only 1 layer, the inner rotor could be dependent on cells changing on the other side of a width 1 stator. I do think that this would be a worthwhile project. I hope others can lend some better insight.

[praosylen]

Here's a preliminary attempt at some code to enumerate rotors in CGoL:

btsrc.cpp

(12.71 KiB) Downloaded 294 times

The tests to ensure that the rotor can be supported without an additional oscillating frame are not yet working perfectly, but they're at least partly functional — most of the results that are outputted are correct. Currently only supports 4x4, and that can't easily be increased (a lot of things hardcoded, and the unsigned 64-bit integers used for the grid would overflow). This is more a proof of concept than anything else, really.

[praosylen]

The last line of the program's output:

Code: Select all

68719214592 patterns tested, 646607 oscillators found:
	163826 period 2
	444627 period 3
	31687 period 4
	899 period 5
	3718 period 6
	1724 period 7
	80 period 8
	20 period 10
	26 period 13

Some of these are duplicates and/or invalid rotors, so really all that this means is that there *probably* aren't any rotors of other periods that fit inside a 4x4 box. I'm working on implementing 4x5 right now.

[velcrorex]

How long did it take your program to finish checking 4x4?

[praosylen]

How long did it take your program to finish checking 4x4?

Somewhere between 5-12 hours (I can't remember when I started it) on a single core. Future versions might get slower because of the necessity of using Boost's fake unsigned 128-bit integer type, but there's probably room for optimization elsewhere.

[Kazyan]

Interesting results--what is this small p13 rotor(s)?

[praosylen]

Interesting results--what is this small p13 rotor(s)?

It's in jslife — upper left corner of the billiard table section.

[praosylen]

Here's a nice 4x5 p17 rotor:

Code: Select all

x = 10, y = 11, rule = B3/S23
bo2b2ob2o2bobo$3ob2ob2o2bobo$obobo2bobobob2o2$3ob3ob3obo3b2o$3obobobobobo3b
o$o3b3ob3ob2ob2o!

I haven't found anything else interesting at 4x5, but I haven't done any exhaustive searches yet.

[AforAmpere]

As a serious question: How do you find the casings for the outputted rotors?

[praosylen]

As a serious question: How do you find the casings for the outputted rotors?

Trial and error, mainly. Extendedlife can help — set the bushing cells to the perma-on and perma-off states, run it, then try to stabilize it from there. Sometimes they're impossible to stabilize without added oscillating support.