Conway's Game of Life

2020年4月17日 · 1871 字 · 4 分钟 · Codewars Csharp

R.I.P John Conway.

由于近期席卷全球的新冠肺炎，John Conway 不幸染病离世。生命游戏 (Game of Life) 是其最为著名的成果。几天前我在 Codewars 上刷到了相关的题目，花了一段时间做了出来，在此写一篇文章，就当是为了纪念 Conway 吧。

题目

Given a 2D array and a number of generations, compute n timesteps of Conway’s Game of Life.

The rules of the game are:

Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
Any live cell with more than three live neighbours dies, as if by overcrowding.
Any live cell with two or three live neighbours lives on to the next generation.
Any dead cell with exactly three live neighbours becomes a live cell.

Each cell’s neighborhood is the 8 cells immediately around it (i.e. Moore Neighborhood). The universe is infinite in both the x and y dimensions and all cells are initially dead - except for those specified in the arguments. The return value should be a 2d array cropped around all of the living cells. (If there are no living cells, then return [[]].)

题目其实就是生命游戏的定义：

在一个无限大的棋盘上，我们以 1 代表存活的生命，以 0 代表死去的生命或 无。

其上的生命遵循上面的四条规则存活、死去、或是产生下一代。

思路

public static int[,] GetGeneration(int[,] cells, int generation)

可以看到函数接收了二维数组与一个整数，分别代表了其上的生命与要演化的代数。

首先我们要认识清楚，棋盘的大小是无限的，而不仅仅是接收的二维数组的大小。当然，题中也给出了计算邻居的规则，我们在处理时，要将接收到的数组扩大一圈。

新建一个长宽各自 +2 的矩形，再把目前的矩形放在其正中间，最后返回这个矩形。

public static int[,] NewBoard(int[,] cells)
{
    var hang = cells.GetLength(0);
    var lie = cells.GetLength(1);

    var newBoard = new int[hang + 2, lie + 2];

    for (int i = 0; i < hang + 2; i++)
    {
        for (int j = 0; j < lie + 2; j++)
        {
            newBoard[i, j] = 0;
        }
    }

    for (int i = 1; i < hang + 1; i++)
    {
        for (int j = 1; j < lie + 1; j++)
        {
            newBoard[i, j] = cells[i - 1, j - 1];
        }
    }

    return newBoard;
}

相应的，在返回最终的结果时，棋盘除了有生命存在的一个矩形之外，也要裁剪掉多出的全为 0 的行与列。

这里是分别从上下、左右遍历了数组，获取了其存在 1 的最外层的坐标，然后把它裁剪了下来，返回了最精简的数组。

public static int[,] cropped(int[,] cells)
{
    var hang = cells.GetLength(0);
    var lie = cells.GetLength(1);
    var (hStart, lStart, hEnd, lEnd, hLen, lLen) = (0, 0, 0, 0, 0, 0);

    for (int i = 0; i < hang; i++)
    {
        for (int j = 0; j < lie; j++)
        {
            if (cells[i, j] != 0)
            {
                hStart = i;
                i = hang;
                break;
            }
        }
    }

    for (int i = hang - 1; i >= 0; i--)
    {
        for (int j = lie - 1; j >= 0; j--)
        {
            if (cells[i, j] != 0)
            {
                hEnd = i;
                i = 0;
                break;
            }
        }
    }

    for (int i = 0; i < lie; i++)
    {
        for (int j = 0; j < hang; j++)
        {
            if (cells[j, i] != 0)
            {
                lStart = i;
                i = lie;
                break;
            }
        }
    }


    for (int i = lie - 1; i >= 0; i--)
    {
        for (int j = hang - 1; j >= 0; j--)
        {
            if (cells[j, i] != 0)
            {
                lEnd = i;
                i = 0;
                break;
            }
        }
    }

    hLen = hEnd - hStart + 1;
    lLen = lEnd - lStart + 1;

    var newCell = new int[hLen, lLen];

    for (int i = 0; i < hLen; i++)
    {
        for (int j = 0; j < lLen; j++)
        {
            newCell[i, j] = cells[hStart + i, lStart + j];
        }
    }

    return newCell;
}

确定了最先与最后的步骤，就要处理中间的过程了。

为了确定某一个坐标下的生物在下一轮中是死是活，只需要获取它有多少存活的邻居，再用给出的四条规则来判定就能得出了。

首先是获取某一特定坐标的生物有多少活着的邻居，仅需遍历它八个邻居的位置并确定是否存活即可。值得注意的是，对于最外层、邻居不足八个的生物要做特殊的处理，以防数组越界。由于我懒得确定是否越界，就用了一个邪道玩法，如果出现了数组越界的 Exception 就忽略掉它继续访问下一个地址。

public static int GetLiveNeighbors(int x, int y, int[,] ceil)
{
    var val = 0;
    int[] neighbors = { 0, 1, -1 };

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if (!(neighbors[i] == 0 && neighbors[j] == 0))
            {
                int r = (x + neighbors[i]);
                int c = (y + neighbors[j]);

                try
                {
                    if (ceil[r, c] == 1)
                    {
                        val += 1;
                    }
                }
                catch (System.Exception)
                {
                    val += 0;
                    continue;
                }
            }
        }
    }

    return val;
}

下面则是确定某一坐标下的生物在下一轮中是死是活。

var hang = cells.GetLength(0);
var lie = cells.GetLength(1);
var newGen = new int[hang + 2, lie + 2];
var biggerCells = NewBoard(cells);

for (int x = 0; x < hang + 2; x++)
{
    for (int y = 0; y < lie + 2; y++)
    {
        var n = GetLiveNeighbors(x, y, biggerCells);
        var c = biggerCells[x, y];

        newGen[x, y] = ((c == 1) && (n == 2 || n == 3) || (c == 0) && n == 3) ? 1 : 0;
    }
}

var result = cropped(newGen);

至于代数，一个递归就能解决问题了。在此不作赘述。

完整代码

using System;
using System.Linq;

public class ConwayLife
{
    public static int[,] GetGeneration(int[,] cells, int generation)
    {
        if (generation <= 0)
        {
            return cells;
        }

        var hang = cells.GetLength(0);
        var lie = cells.GetLength(1);

        var newGen = new int[hang + 2, lie + 2];

        var biggerCells = NewBoard(cells);


        for (int x = 0; x < hang + 2; x++)
        {
            for (int y = 0; y < lie + 2; y++)
            {
                var n = GetLiveNeighbors(x, y, biggerCells);
                var c = biggerCells[x, y];

                newGen[x, y] = ((c == 1) && (n == 2 || n == 3) || (c == 0) && n == 3) ? 1 : 0;
            }
        }

        var result = cropped(newGen);

        return GetGeneration(result, generation - 1);
    }

    public static int GetLiveNeighbors(int x, int y, int[,] ceil)
    {
        var val = 0;
        int[] neighbors = { 0, 1, -1 };

        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                if (!(neighbors[i] == 0 && neighbors[j] == 0))
                {
                    int r = (x + neighbors[i]);
                    int c = (y + neighbors[j]);

                    try
                    {
                        if (ceil[r, c] == 1)
                        {
                            val += 1;
                        }
                    }
                    catch (System.Exception)
                    {
                        val += 0;
                        continue;
                    }
                }
            }
        }

        return val;
    }

    public static int[,] cropped(int[,] cells)
    {
        var hang = cells.GetLength(0);
        var lie = cells.GetLength(1);
        var (hStart, lStart, hEnd, lEnd, hLen, lLen) = (0, 0, 0, 0, 0, 0);

        for (int i = 0; i < hang; i++)
        {
            for (int j = 0; j < lie; j++)
            {
                if (cells[i, j] != 0)
                {
                    hStart = i;
                    i = hang;
                    break;
                }
            }
        }

        for (int i = hang - 1; i >= 0; i--)
        {
            for (int j = lie - 1; j >= 0; j--)
            {
                if (cells[i, j] != 0)
                {
                    hEnd = i;
                    i = 0;
                    break;
                }
            }
        }

        for (int i = 0; i < lie; i++)
        {
            for (int j = 0; j < hang; j++)
            {
                if (cells[j, i] != 0)
                {
                    lStart = i;
                    i = lie;
                    break;
                }
            }
        }


        for (int i = lie - 1; i >= 0; i--)
        {
            for (int j = hang - 1; j >= 0; j--)
            {
                if (cells[j, i] != 0)
                {
                    lEnd = i;
                    i = 0;
                    break;
                }
            }
        }

        hLen = hEnd - hStart + 1;
        lLen = lEnd - lStart + 1;

        var newCell = new int[hLen, lLen];

        Console.WriteLine($"h {hLen} l {lLen}");

        for (int i = 0; i < hLen; i++)
        {
            for (int j = 0; j < lLen; j++)
            {
                newCell[i, j] = cells[hStart + i, lStart + j];
            }
        }

        return newCell;
    }

    public static int[,] NewBoard(int[,] cells)
    {
        var hang = cells.GetLength(0);
        var lie = cells.GetLength(1);

        var newBoard = new int[hang + 2, lie + 2];

        for (int i = 0; i < hang + 2; i++)
        {
            for (int j = 0; j < lie + 2; j++)
            {
                newBoard[i, j] = 0;
            }
        }

        for (int i = 1; i < hang + 1; i++)
        {
            for (int j = 1; j < lie + 1; j++)
            {
                newBoard[i, j] = cells[i - 1, j - 1];
            }
        }

        return newBoard;
    }
}

一些 powershell 脚本 Hugo 自动化 CI V2