This is a bit of a theoretical question. In a programming assignment, we have been told to implement the Game of Life by John Conway. As an additional task, we've been asked to modify the program so that it can detect repetitions of patterns for periods up to four generations. For example, the program should behave like this, given this specific "seed" to the game:
--------
| |
| OOO |
| |
| |
| |
--------
--------
| 0 |
| 1 |
| 0 |
| |
| |
--------
--------
| |
| O2O |
| |
| |
| |
--------
Repetition detected (2): exiting
Indicating that the program repeated itself and that the period was 2 generations long.
My question is this. Is it possible to really know when a program is simply repeating the same pattern over and over again? I've heard of the "Halting problem". Is this related to that?
Now, if it indeed is possible, how can the program that the teachers seem to be running seem to be able to detect it after just one repetition? Second, is it really reasonable to expect students of a basic programming course to write a program that detects repeating patterns in the Game of Life? I have a feeling that what they mean to say is "modify your program to exit when the same state is reached twice within a 4 generation window" which seems to me like an entirely different matter than to detect if the pattern will truly repeat itself forever.
EDIT:
Here's what the specification says: You are to modify the program to detect a repetition of a previous pattern. Your program should be able to detect repeating patterns with periods of up to four generations. When such a repetitions is discovered, the program should exit with a different message:
Period detected (4): exiting
replacing the "Finished" message, with the length of the period indicated by the number in brackets. The repeated pattern should be printed before exiting.
Is it possible to really know when a program is simply repeating the same pattern over and over again?
Conway's Game of Life is 100% deterministic, which means that no matter when you encounter a pattern, you always know exactly what the next evolution of the pattern will be. On top of this, a given input in one generation will always result in one specific output for the next generation, regardless of when that input is received.
So to find periods in the evolution of the state, all you'd have to do is detect when/if a duplicate state appears; at that moment, you know you've found a cycle. I'm going to write my example code in C++, but any language which has a "Hash Table" or similar data structure can use the same basic algorithms.
//We're expressly defining a grid as a 50x50 grid.
typedef std::array<std::array<bool, 50>, 50> Conway_Grid;
struct Conway_Hash {
size_t operator()(Conway_Grid const& grid) const {
size_t hash = 0;
for(int i = 0; i < grid.size(); i++) {for(int j = 0; j < grid[i].size(); j++) {
if(grid[i][j])
hash += (i * 50 + j);
//I make no guarantees as to the quality of this hash function...
}}
return hash;
}
};
struct Conway_Equal {
bool operator()(Conway_Grid const& g1, Conway_Grid const& g2) const {
for(int i = 0; i < grid.size(); i++) {for(int j = 0; j < grid[i].size(); j++) {
if(g1[i][j] != g2[i][j])
return false;
}}
return true;
}
};
typedef int Generation;
std::unordered_map<Conway_Grid, Generation, Conway_Hash, Conway_Equal> cache;
Conway_Grid get_next_gen(Conway_Grid const& grid) {
Conway_Grid next{};
for(int i = 1; i < grid.size() - 1; i++) {for(int j = 1; j < grid[i].size() - 1; j++) {
int neighbors = 0;
for(int x = i - 1; x <= i + 1; x++) { for(int y = j - 1; y <= j + 1; y++) {
if(x == i && y == j) continue;
if(grid[x][y]) neighbors++;
}}
if(grid[i][j] && (neighbors == 2 || neighbors == 3))
next[i][j] = true;
else if(!grid[i][j] && (neighbors == 3))
next[i][j] = true;
}}
return next;
}
int main() {
Conway_Grid grid{};//Initialized all to false
grid[20][20] = true;
grid[21][20] = true;
grid[22][20] = true;//Blinker
for(Generation gen = 0; gen < 1'000; gen++) { //We'll search a thousand generations
auto it = cache.find(grid);
if(it != cache.end()) {//"Is the grid already in the cache?"
std::cout << "Period found at generation " << gen;
std::cout << ", which was started on generation " << it->second;
std::cout << ", which means the period length is " << gen - it->second << '.' << std::endl;
break;
}
cache[grid] = gen; //"Inserts the current grid into the cache"
grid = get_next_gen(grid); //"Updates the grid to its next generation"
}
return 0;
}
Note that this code actually works for any period length, not just a length less than 4. In the above code, for a blinker (three cells in a row), we get the following result:
Period found at generation 2, which was started on generation 0, which means the period length is 2.
As a sanity check, I decided to import a Gosper Glider Gun to make sure that it worked just as well.
grid[31][21] = true;
grid[29][22] = true;
grid[31][22] = true;
grid[19][23] = true;
grid[20][23] = true;
grid[27][23] = true;
grid[28][23] = true;
grid[41][23] = true;
grid[42][23] = true;
grid[18][24] = true;
grid[22][24] = true;
grid[27][24] = true;
grid[28][24] = true;
grid[41][24] = true;
grid[42][24] = true;
grid[7][25] = true;
grid[8][25] = true;
grid[17][25] = true;
grid[23][25] = true;
grid[27][25] = true;
grid[28][25] = true;
grid[7][26] = true;
grid[8][26] = true;
grid[17][26] = true;
grid[21][26] = true;
grid[23][26] = true;
grid[24][26] = true;
grid[29][26] = true;
grid[31][26] = true;
grid[17][27] = true;
grid[23][27] = true;
grid[31][27] = true;
grid[18][28] = true;
grid[22][28] = true;
grid[19][29] = true;
grid[20][29] = true;
Gosper's Glider Gun doesn't normally have a period, since it creates an infinite number of gliders over time, and the pattern never repeats. But because the grid is bounded, and we simply erase cells on the border of the grid, this pattern will eventually create a repeating pattern, and sure enough, this program finds it:
Period found at generation 119, which was started on generation 59, which means the period length is 60.
(This is doubly good, because the period of just the gun is supposed to be 60)
Note that this is almost certainly not the best solution to this problem, as this solution saves each generated grid in memory, and for larger grids, this will both eat up RAM and CPU cycles. But it's the simplest solution, and you'll likely be able to find a similar solution for whichever programming language you're using.