检测康威生命游戏中的重复

Question

这是一个有点理论性的问题。在编程作业中，约翰康威告诉我们要实现生命游戏。作为一项附加任务，我们被要求修改程序，以便它可以检测最多四代的模式重复。例如，给定这个特定的游戏“种子”，程序应该像这样：

 --------
|        | 
|   OOO  |  
|        | 
|        |
|        |
 --------

 --------
|    0   | 
|    1   |  
|    0   | 
|        |
|        |
 --------

 --------
|        | 
|   O2O  |  
|        | 
|        |
|        |
 --------
Repetition detected (2): exiting

表明该程序重复自身并且周期为 2 代。

我的问题是这个。是否有可能真正知道程序何时只是一遍又一遍地重复相同的模式？我听说过“停机问题”。这和那个有关吗？

现在，如果确实有可能，那么教师似乎正在运行的程序如何在重复一次后似乎能够检测到它？其次，期望基础编程课程的学生编写一个程序来检测生命游戏中的重复模式真的合理吗？我有一种感觉，他们的意思是“修改您的程序以在第 4 代窗口内两次达到相同状态时退出”，这在我看来与检测模式是否真的会永远重复完全不同.

编辑：

这是规范所说的：您将修改程序以检测先前模式的重复。您的程序应该能够检测到长达四代的重复模式。当发现这样的重复时，程序应该以不同的消息退出：

Period detected (4): exiting

用括号中的数字表示的周期长度替换“完成”消息。退出前应打印重复的图案。

Answer 1

是否有可能真正知道程序何时只是一遍又一遍地重复相同的模式？

Conway's Game of Life 是 100% 确定性的，这意味着无论您何时遇到一个模式，您总是确切地知道该模式的下一个演变将是什么。最重要的是，一代中的给定输入将始终为下一代产生一个特定的输出，无论何时收到该输入。

因此，要找到状态演变的周期，您所要做的就是检测何时/是否出现重复状态；在那一刻，你知道你找到了一个循环。我将用 C++ 编写我的示例代码，但任何具有“哈希表”或类似数据结构的语言都可以使用相同的基本算法。

//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 Glider Gun 以确保它也能正常工作。

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 的 Glider Gun 通常没有周期，因为它会随着时间的推移产生无限数量的滑翔机，而且这种模式永远不会重复。但是因为网格是有界的，我们只是简单地擦除了网格边界上的单元格，这个模式最终会创建一个重复的模式，果然，这个程序找到了它：

Period found at generation 119, which was started on generation 59, which means the period length is 60.

（这个加倍好，因为刚枪的周期应该是60）

请注意，这几乎肯定不是该问题的最佳解决方案，因为该解决方案将每个生成的网格保存在内存中，而对于较大的网格，这会占用 RAM 和 CPU 周期。但这是最简单的解决方案，您可能会为您使用的任何编程语言找到类似的解决方案。