Matthew Cook 20 Sep 98 I have finally determined that it does not take exponential time to distinguish a still-life from a pseudo-still-life, for the standard definition where the islands must be partitionable into exactly two stable proper subsets. It takes only linear time, plus O(n^2) where n is the number of instances of the following rare type of pathology: . O O . O O . . O O . O O . . . . . . . . O . O O O . O O O . O . O O "Lock" The algorithm is a bit complicated, though: 1. Find the Islands. 2. Build Infrastructure: Bridges, Aquaducts, and Locks. Build bridges on cells that touch two islands, at least one of which at three points: A A A A A . A . B . | . A \ . . / . etc. B B B . . B . A A A bridge cell acts like a land cell, connecting islands as one, and separating water cells. Build aquaducts on cells having 4 live neighbors, that touch 3 or 4 islands: A . B A A . A . A A . B . + . . + . . + . . + . C . D B . C B . C C . A An aquaduct connects the water on opposite sides of it, without connecting the crossing canals to each other, or connecting any islands. (In the second case shown, one of the canals dead-ends after passing through the aquaduct.) Build locks on cells touching three islands, one of which at three points: A . B .} {. C C C A lock consists of two gates, only one of which may be open at a time. A closed gate connects its two islands like a bridge, while an open gate connects its two waterways. Note how a lock necessarily disconnects the A.C canal from the B.C canal (when labeled as shown), since at least one of the gates must be closed. 3. Find the Seas. A sea is a connected body of water (empty cells), given that the infrastructure has been installed, and all locks have both gates closed. (A sea that borders only one island is really a lake and can be ignored.) Now we can begin to see what the main idea is for this algorithm: If we can find a cycle through the seas, then if we draw this cycle, and do an even-odd fill of it, then we can put islands from the filled region into one set, and islands from the unfilled region into the other set, and both sets will be stable. (A lock is not allowed to change its state as you draw the cycle!) Furthermore, if there is a partitioning of the islands into two stable sets, then we can close lock gates between islands of the same set, leaving the rest of the gates open, and we will see that if we color seas touching islands from both sets red, then there must be a cycle through the red seas (possibly several). So the possibility of partitioning the islands into two stable sets is equivalent to the possibility of finding a cycle through the seas. From now on, we will only talk about finding a cycle through the seas, leaving talk of sets of islands to the canaries. If any sea is not simply connected (this can be determined by refusing to make "connections" as one "grows" the sea), then there is a trivial cycle within that sea alone, and we are done. The one exception is the outermost sea, so one should in effect consider all of the outermost sea cells to be like one single sea cell when growing that sea. 4. List the locks in terms of their seas. <<verbose mode off>> 5. Convert to form where each sea touches only two locks. 6. Find a sea that meets both locks at a side, call it X. (There must be such a sea by the pigeonhole principle.) 7. Remove X. 8. Find a cut edge (if none, go to step 6), call it Y. 9. Call the two remaining components com1 and com2. Put X back in. Short-circuit com2 by deleting it and connecting X and Y. 10. Recursion: Is there a cycle in this smaller set of seas? If not, any cycle must be in com2 alone: Throw out com1 and go to step 6. If so, does it use the short-circuit? If it doesn't use the short, we are done. So we found a cycle through com1 that uses the short. 11. Put com2 back in and delete com1. (X and Y are still shorted to each other.) 12. Recursion: Is there a cycle in this smaller set of seas? If not, any cycle must be in com1 alone: Throw out com2 and go to step 6. If so, does it use the short-circuit? If it doesn't use the short, we are done. So we found a cycle through com2 that uses the short. 13. Merge the cycles found in steps 10 and 12 to make one long cycle that doesn't cross the short. We are done.