Demo run on a vertex graph - as if we use "fish-eye" to view through one of the sides.
Green mark "young" generation, blue are for mature and pink for old. No pre-aging in this case.
We already had a few problems related to Conway's game of Life, e.g. starting with Life is Simple. However the theme of similar "cellular automata" seems inexhaustible! In this exercise we use game with modified rules on a finite space - mainly as a manner to practice with constructing suitable data structure programmatically.
Additionally you'll see this "world" and set of rules open yet another questions which could be, perhaps, curious to research.
Rules
So the Life evolves on a dodecahedron, or rather its vertex graph. Dodecahedron has 20 vertices, each of which is linked to 3 others (by
3 edges). Organisms live on these vertices (or in other words any vertex could be either live or empty).
- Empty vertex which has exactly
1live neighbor becomes live itself (in the next generation). - Live vertex has a life limit of
3generations - i.e. if it was "born" in the generationn, it survives into generationsn+1andn+2but dies (vertex becomes empty) in generationn+3. Let's call them "young", "mature" and "old" in the examples below. - Optional "pre-aging" rule: live vertex with
3neighbors becomes empty in the next generation (even if it was not "old" enough).
For better diversity of our research we shall study cases with "pre-aging" rule enabled or disabled.
As an example, consider the case with only one live vertex in initital configuration. All initial vertices are "young". Pre-aging is enabled in this example.
On the 1-st step it begets 3 children in all its neighboring vertices, itself turns "mature" (e.g. young=3, mature=1).
On the 2-nd step initial vertex goes vacant, and 6 new vertices goes alive (young=6, mature=3).
On the 3-rd step even 6 more vertices are "born", all others "age" naturally (young=6, mature=6, old=3).
On the 4-th step only 6 previously "young" organisms survive (mature=6).
On the 5-th step they turn "old" but beget 6 new vertices (young=6, old=6).
On the 6-th step situation of the step 4 repeats but with different configuration.
On the 7-th step situation of the step 5 is repeated but with young and old vertices swapped.
On the 8-th step here comes exact reproduction of the step 4.
So in this case we encounter a "periodic" behavior with period of 4.
Problem statement
Given several initial configurations we want to calculate the outcome, which is expected to be of two cases:
- either configuration dies completely
- or it enters "loop" with some period
So the answer should tell either at which step all vertices become vacant, or at which step we find exact repetition of some previous step.
To specify initial configuration we introduce certain numbering of the vertices, shown at the picture.
This also could be described verbally as
follows. Enumerate vertices of one "face" from 0 to 4 in order (say, clockwise). Next for each i-th of them find the remaining
non-enumerated neighbor and enumerate them with i*2+5 (e.g. neighbor of 0 is 5, neighbor of 1 is 7 and so on). At last enumerate
vertices lying "betwen" those lately enumerated. The one neighboring 5 and 7 should become 6, the next between 7 and 9 becomes 8 and
so on, with the last between 13 and 15 getting number 14. We don't enumerate remaining vertices as for our experimental setups this subset
seems enough.
Input data: provides the number of configurations to solve in the first line. Next lines describe one configuration each, simply giving the list of the vertices which are initially live (set to "young").
Answer: should give outcomes, space-separated, in a single line. Either in form 123-x if the colony perishes on the given step - or in the
form 95-91 meaning that on the step 95 repetition of step 91 is encountered.
Example:
input data:
4
0 a
0 2 3 6
0 3 5 10 11 13
0 4 5 8 11 12 a
answer:
8-4 70-54 72-x 215-211
Additional questions to research. We see that "periodic" configurations generally have period of 4, which seemingly is caused by 3 "ages"
of the living cells. Obviously no "stationary" (or "stable") configurations may exist due to aging. But what other periods may be encountered?
I think I've seen periods of 16 and 8. Could there be configurations with "rotational" behavior, for example (for us it may look perhaps
as periodic with period being multiple of 3 or 5) - perhaps this could be achieved by some further modification of rules?