conways-game-of-life - 检测康威生命游戏中的重复

Question

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

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

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

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

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

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

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

编辑:

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

Period detected (4): exiting

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

Answer 1

Is it possible to really know when a program is simply repeating the same pattern over and over again?

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 周期。但这是最简单的解决方案，您可能会为您使用的任何编程语言找到类似的解决方案。