Separating spaceships

[Alexey_Nigin]

A while ago I announced that I was working on some cool CA-related project. This is indeed the case, and the ultimate goal of this project is to create an up-to-date online interactive database of spaceships in lifelike CA. It is now in the earliest stage of development: actually, I haven't started coding yet.

Anyway, I will certainly need an algorithm that can check whether a given pattern is a single spaceship or a trivial combination of a bunch of spaceships with the same velocity. It does not need to be particularly fast or memory-efficient (though it would be great), but it needs to always work correctly. Here is what I was able to come up with:

1. Check that the pattern repeats with period p.
2. Make a 3D array A, where two dimensions represent the CA plane and the third one is time.
3. Populate A with p+1 generations of the pattern.
4. Separate A into connected components. Diagonally and triagonally connected cells are still considered connected.
5. Take any one component C. Find a cell that would be born if C was the only thing in the universe, but which isn't born due to other components.
6. Find the smallest number of other components (it will almost always be 1) that successfully prevent the birth of the cell. Unite them with C; they will be considered one component from now on.
7. Terminate when either there is only one component or there is no cell that could be born from one component but isn't born due to others.
8. If there is only one component left, the spaceship is non-trivial.

In order to verify that this algorithm always works, I offer a virtual ice cream cone (virtual chocolate or virtual vanilla only) to anyone who presents a spaceship incorrectly classified by this algorithm. I will also appreciate if you just report any flaws (or absence of flaws) in the algorithm's logic.

[calcyman]

A while ago I announced that I was working on some cool CA-related project. This is indeed the case, and the ultimate goal of this project is to create an up-to-date online interactive database of spaceships in lifelike CA. It is now in the earliest stage of development: actually, I haven't started coding yet.

Anyway, I will certainly need an algorithm that can check whether a given pattern is a single spaceship or a trivial combination of a bunch of spaceships with the same velocity. It does not need to be particularly fast or memory-efficient (though it would be great), but it needs to always work correctly. Here is what I was able to come up with:

1. Check that the pattern repeats with period p.
2. Make a 3D array A, where two dimensions represent the CA plane and the third one is time.
3. Populate A with p+1 generations of the pattern.
4. Separate A into connected components. Diagonally and triagonally connected cells are still considered connected.
5. Take any one component C. Find a cell that would be born if C was the only thing in the universe, but which isn't born due to other components.
6. Find the smallest number of other components (it will almost always be 1) that successfully prevent the birth of the cell. Unite them with C; they will be considered one component from now on.
7. Terminate when either there is only one component or there is no cell that could be born from one component but isn't born due to others.
8. If there is only one component left, the spaceship is non-trivial.

In order to verify that this algorithm always works, I offer a virtual ice cream cone (virtual chocolate or virtual vanilla only) to anyone who presents a spaceship incorrectly classified by this algorithm. I will also appreciate if you just report any flaws (or absence of flaws) in the algorithm's logic.

The step 'find the smallest number of other components' is ill-defined. It could be that there's a spaceship A which survives if either B or C or both are present, but not when B and C are simultaneously absent. If you're not that interested in speed, then you can consider all partitions of the connected components (it does take exponential time). That's essentially what I'm doing in the latest version of my pseudo-oscillator detection routine.

Also, in step 4, you need to consider connected components in the quotient space Z^3 / <(x, y, t)> where you quotient out by the 1D lattice generated by the period. Otherwise (for example) the spark from a HWSS appearing in generation 0 will be classified as its own connected component.

[Alexey_Nigin]

The step 'find the smallest number of other components' is ill-defined. It could be that there's a spaceship A which survives if either B or C or both are present, but not when B and C are simultaneously absent. If you're not that interested in speed, then you can consider all partitions of the connected components (it does take exponential time). That's essentially what I'm doing in the latest version of my pseudo-oscillator detection routine.

This is a good idea. Thinking about it, most interesting spaceships have at most two connected components (like Brain), and those with many more components are likely either HWSS-on-HWSS-on-HWSS-on-HWSS-on-... kind of thing or trivial fleets. In either of these two cases, it would not be too bad if the algorithm hit an imposed time limit before finishing.

Also, in step 4, you need to consider connected components in the quotient space Z^3 / <(x, y, t)> where you quotient out by the 1D lattice generated by the period. Otherwise (for example) the spark from a HWSS appearing in generation 0 will be classified as its own connected component.

This is indeed a full-scale error. If I understand the terms correctly, you want to make the array wrap around in the temporal direction. Doing it is a bit harder for spaceships than for oscillators, but it's not too hard.

[praosylen]

A while ago I announced that I was working on some cool CA-related project. This is indeed the case, and the ultimate goal of this project is to create an up-to-date online interactive database of spaceships in lifelike CA. It is now in the earliest stage of development: actually, I haven't started coding yet.

Anyway, I will certainly need an algorithm that can check whether a given pattern is a single spaceship or a trivial combination of a bunch of spaceships with the same velocity. It does not need to be particularly fast or memory-efficient (though it would be great), but it needs to always work correctly. Here is what I was able to come up with:

1. Check that the pattern repeats with period p.
2. Make a 3D array A, where two dimensions represent the CA plane and the third one is time.
3. Populate A with p+1 generations of the pattern.
4. Separate A into connected components. Diagonally and triagonally connected cells are still considered connected.
5. Take any one component C. Find a cell that would be born if C was the only thing in the universe, but which isn't born due to other components.
6. Find the smallest number of other components (it will almost always be 1) that successfully prevent the birth of the cell. Unite them with C; they will be considered one component from now on.
7. Terminate when either there is only one component or there is no cell that could be born from one component but isn't born due to others.
8. If there is only one component left, the spaceship is non-trivial.

In order to verify that this algorithm always works, I offer a virtual ice cream cone (virtual chocolate or virtual vanilla only) to anyone who presents a spaceship incorrectly classified by this algorithm. I will also appreciate if you just report any flaws (or absence of flaws) in the algorithm's logic.

I independently came up with a similar, yet somewhat simpler, algorithm for use in my next version of non-totalistic apgsearch, v0.3i, to possibly replace pseudo_bangbang(). My modification is to consider off cells that are overcrowded as interacting as well as on cells, similar to the current version of pseudo_bangbang() (but only when an interacting off cell and an on cell are adjacent). For my variation, I could not find any cases where steps 5-8 are necessary, but that doesn't mean that I didn't miss any. I have an incomplete Python script on another computer (it's missing the rule-generation components necessary to work for arbitrary rules, but it works fine for Life with the necessary rules present); it works for any periodic pattern, not just spaceships. I am somewhat concerned about it, however, because it will incorrectly separate combinations of reflectorless rotating oscillators that form a lower-period oscillator, as well as a hypothetical class of "reflectorless rotating spaceships".

[Alexey_Nigin]

I independently came up with a similar, yet somewhat simpler, algorithm for use in my next version of non-totalistic apgsearch, v0.3i, to possibly replace pseudo_bangbang(). My modification is to consider off cells that are overcrowded as interacting as well as on cells, similar to the current version of pseudo_bangbang() (but only when an interacting off cell and an on cell are adjacent). For my variation, I could not find any cases where steps 5-8 are necessary, but that doesn't mean that I didn't miss any. I have an incomplete Python script on another computer (it's missing the rule-generation components necessary to work for arbitrary rules, but it works fine for Life with the necessary rules present); it works for any periodic pattern, not just spaceships. I am somewhat concerned about it, however, because it will incorrectly separate combinations of reflectorless rotating oscillators that form a lower-period oscillator, as well as a hypothetical class of "reflectorless rotating spaceships".

I am not sure I understand you correctly, because it seems like it would fail to separate a lot of spaceships. Take Brain, for example: if you put two of them so that there is one vertical row of off cells between them (I don't have access to Golly now, so no RLE - sorry), there will always be at least two overcrowded cells in between.

As for reflectorless rotating oscillators / spaceships, I think it is right to separate them, even if the period then increases.

[praosylen]

I am not sure I understand you correctly, because it seems like it would fail to separate a lot of spaceships. Take Brain, for example: if you put two of them so that there is one vertical row of off cells between them (I don't have access to Golly now, so no RLE - sorry), there will always be at least two overcrowded cells in between.

Sorry, I didn't explain very well. "Overcrowded" in my above explanation should mean that there are at least 4 on neighbors, and there is at least one subset of 3 adjacent on neighbors that are kingwise-connected to each other, but not to any on neighbors outside the subset.