Many thanks to Clive Fraser for creating this problem!
This is a simplified version of John Horton Conway's Game of Life. It runs on a single string of cells which is joined end to end in order to form a continuous loop. This means that every cell in the string has exactly two neighbouring cells. Cells may or may not contain organisms.
In order to determine the status of a cell in the next generation we need to know whether or not it contains an
organism and how many organisms are contained within the neighbouring two cells. Note that a single cell can
contain at most one organism. So the two cells neighbouring any particular cell can contain either 0, 1 or 2
organisms between them. The rules for creating the next generation are as follows.
1 organism in the two neighbouring cells will result in the birth of a new
organism in this cell.0 or 2 organisms in the two neighbouring cells will remain empty in the next
generation.0 or 2
organisms in the two neighbouring cells.1 organism in the two neighbouring cells.If we use . (dot) to represent an empty cell and X to represent a cell containing an organism, then a string
of 8 cells containing 4 organisms could be represented by ...XXX.X The next generation of these cells
would be X.X.X..X
If we number the cells from 1 to 8 we can describe the generation process as follows. Cell 1 is empty and
has 1 neighbouring organism (from the 8th cell) so we have a birth in cell 1. Cell 2 is empty and has
no neighbouring organisms, so there is no change. Cell 3 is empty and has 1 neighbouring organism, so we have
a birth in this cell. Cell 4 contains an organism and has 1 neighbouring organism, so the organism in cell
4 will die. Cell 5 contains an organism and has 2 neighbouring organisms, so this organism survives.
Cell 6 contains an organism and has 1 neighbouring organism so this organism will die. Cell 7 is empty and
has 2 neighbouring organisms, so nothing changes. Cell 8 contains an organism and has no neighbouring
organisms (remember to count cell 1) so this organism survives.
In this problem you will be given the current state of the cells in the string and are asked to find the
previous generation of the cells. However, there are often several different configurations which will all give
rise to an identical second generation. Because of this you are asked to give the lexicographically smallest of
the possible previous generations. (This is the one that comes first in alphabetical order. (Note that '.' < 'X')
Sometimes there is no possible previous generation for a given configuration of cells. We will represent this
situation with the digit 0 in the answer. Such patterns are called Garden of Eden
in game-of-life's terminology.
Input/Output description: The first line of the input data will contain a single integer N, the number of
cell strings to process. N lines will follow. Each line contains a single string of cells. Find the lexicographically smallest possible PREVIOUS
generation, or give the answer 0 if there is no such string. Combine all answers, separated by spaces, into a single long string.
Example:
input:
4
X.X.X..X
..X.XX....X
X.X..XX.XX...XX..X.
.X...XXXXX.....X.X.XX
answer:
...XXX.X ...XXXX.XX. .XXX.X...X.XX..XX.. 0