检测康威人生游戏中的重复
Detecting repetitions in Conway's game of life
这是一个有点理论性的问题。在一项编程任务中，我们被告知要实现 John Conway 的生命游戏。作为一项附加任务，我们被要求修改程序，以便它可以检测最多四代周期的模式重复。例如，程序应该像这样，给定这个特定的 "seed" 游戏：
--------
| |
| OOO |
| |
| |
| |
--------
--------
| 0 |
| 1 |
| 0 |
| |
| |
--------
--------
| |
| O2O |
| |
| |
| |
--------
Repetition detected (2): exiting
说明程序重复了自己，周期是2代。
我的问题是这样的。是否有可能真正知道程序何时只是一遍又一遍地重复相同的模式？我听说过 "Halting problem"。这跟那个有关系吗？
现在，如果确实可以的话，老师们似乎运行的程序怎么可能只重复一次就检测出来呢？其次，期望基础编程课程的学生编写检测生命游戏中重复模式的程序真的合理吗？我有一种感觉，他们的意思是 "modify your program to exit when the same state is reached twice within a 4 generation window"，在我看来，这与检测模式是否会永远重复自己完全不同。
编辑：
规范是这样说的：
您将修改程序以检测先前模式的重复。您的程序应该能够检测最多四代周期的重复模式。当发现这样的重复时，程序应该退出并显示不同的消息：
Period detected (4): exiting
替换 "Finished" 消息，用括号中的数字表示的时间长度。退出前应打印重复的图案。
Is it possible to really know when a program is simply repeating the same pattern over and over again?
Conway 的生命游戏是 100% 确定性的，也就是说无论你什么时候遇到一个模式，你总是清楚地知道这个模式的下一次演化会是什么。最重要的是，无论何时收到该输入，一代中的给定输入将始终为下一代产生一个特定的输出。
因此，要找到状态演变的时期，您所要做的就是检测 when/if 出现重复状态；在那一刻，你知道你找到了一个循环。我打算用 C++ 编写我的示例代码，但是任何具有 "Hash Table" 或类似数据结构的语言都可以使用相同的基本算法。
//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;
}
请注意，此代码实际上适用于 任何 周期长度，而不仅仅是小于 4 的长度。在上面的代码中，对于信号灯（连续三个单元格），我们得到以下结果：
Period found at generation 2, which was started on generation 0, which means the period length is 2.
作为完整性检查，我决定导入一把 Gosper 滑翔机枪以确保它同样有效。
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 的滑翔机枪通常没有周期，因为它会随着时间的推移创造无限数量的滑翔机，而且模式永远不会重复。但是因为网格是有界的，我们只是擦除网格边界上的单元格，这个图案最终会创建一个重复的图案，果然，这个程序找到了它：
Period found at generation 119, which was started on generation 59, which means the period length is 60.
（这个加倍好，因为刚枪的周期应该是60）
请注意，这几乎肯定不是此问题的最佳解决方案，因为此解决方案会将每个生成的网格保存在内存中，对于较大的网格，这都会占用 RAM和 CPU 周期。但这是最简单的解决方案，无论您使用哪种编程语言，您都可能会找到类似的解决方案。
这是一个有点理论性的问题。在一项编程任务中，我们被告知要实现 John Conway 的生命游戏。作为一项附加任务，我们被要求修改程序，以便它可以检测最多四代周期的模式重复。例如，程序应该像这样，给定这个特定的 "seed" 游戏：
--------
| |
| OOO |
| |
| |
| |
--------
--------
| 0 |
| 1 |
| 0 |
| |
| |
--------
--------
| |
| O2O |
| |
| |
| |
--------
Repetition detected (2): exiting
说明程序重复了自己，周期是2代。
我的问题是这样的。是否有可能真正知道程序何时只是一遍又一遍地重复相同的模式？我听说过 "Halting problem"。这跟那个有关系吗？
现在，如果确实可以的话，老师们似乎运行的程序怎么可能只重复一次就检测出来呢？其次，期望基础编程课程的学生编写检测生命游戏中重复模式的程序真的合理吗？我有一种感觉，他们的意思是 "modify your program to exit when the same state is reached twice within a 4 generation window"，在我看来，这与检测模式是否会永远重复自己完全不同。
编辑：
规范是这样说的： 您将修改程序以检测先前模式的重复。您的程序应该能够检测最多四代周期的重复模式。当发现这样的重复时，程序应该退出并显示不同的消息：
Period detected (4): exiting
替换 "Finished" 消息，用括号中的数字表示的时间长度。退出前应打印重复的图案。
Is it possible to really know when a program is simply repeating the same pattern over and over again?
Conway 的生命游戏是 100% 确定性的，也就是说无论你什么时候遇到一个模式，你总是清楚地知道这个模式的下一次演化会是什么。最重要的是，无论何时收到该输入，一代中的给定输入将始终为下一代产生一个特定的输出。
因此，要找到状态演变的时期，您所要做的就是检测 when/if 出现重复状态；在那一刻，你知道你找到了一个循环。我打算用 C++ 编写我的示例代码，但是任何具有 "Hash Table" 或类似数据结构的语言都可以使用相同的基本算法。
//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;
}
请注意，此代码实际上适用于 任何 周期长度，而不仅仅是小于 4 的长度。在上面的代码中，对于信号灯（连续三个单元格），我们得到以下结果：
Period found at generation 2, which was started on generation 0, which means the period length is 2.
作为完整性检查，我决定导入一把 Gosper 滑翔机枪以确保它同样有效。
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 的滑翔机枪通常没有周期，因为它会随着时间的推移创造无限数量的滑翔机，而且模式永远不会重复。但是因为网格是有界的，我们只是擦除网格边界上的单元格，这个图案最终会创建一个重复的图案，果然，这个程序找到了它：
Period found at generation 119, which was started on generation 59, which means the period length is 60.
（这个加倍好，因为刚枪的周期应该是60）
请注意，这几乎肯定不是此问题的最佳解决方案，因为此解决方案会将每个生成的网格保存在内存中，对于较大的网格，这都会占用 RAM和 CPU 周期。但这是最简单的解决方案，无论您使用哪种编程语言，您都可能会找到类似的解决方案。