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:
- Check that the pattern repeats with period p.
- Make a 3D array A, where two dimensions represent the CA plane and the third one is time.
- Populate A with p+1 generations of the pattern.
- Separate A into connected components. Diagonally and triagonally connected cells are still considered connected.
- 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.
- 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.
- 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.
- If there is only one component left, the spaceship is non-trivial.