HackerRank Conway 的生命游戏算法

Question

我最近解决了名为“康威的生命游戏”的有趣的

HackerRank

问题。问题陈述如下：

生命游戏是由英国数学家约翰·霍顿·康威设计的细胞自动机游戏。原版游戏是零玩家 游戏。它的演变完全取决于它的输入。

生命游戏发生在 2D 网格上。网格中的每个单元格将 在两种可能状态之一中，

ALIVE DEAD 细胞的诞生或死亡基于以下因素 规则。

如果一个单元格恰好被 3 包围，它就会从 DEAD 状态切换到 ALIVE 状态 活细胞。如果一个细胞被 2 或 3 个活细胞包围，那么它仍然活着 细胞。如果一个细胞周围有 由于人口过多，活细胞数量超过 3 个。 A单元开关 如果周围的细胞少于 2 个，则从“活着”变为“死亡” 因为人口少。每个单元周围有 8 个单元，其中 4 个位于 它的侧面和角上有 4 个。最角落的细胞只有 3 个邻居以及最右、最左、最上、最下的单元格 棋盘有 5 个相邻单元格。上述规则 也适用于这些细胞。

这个版本的生命游戏占据了 29x29 的网格，左上角 单元格为 (0,0)，右下单元格为 (28,28)。它的索引为 （行，列）就像计算机科学中的数组。两名玩家对战 彼此。这个游戏与原版的不同之处在于，一个细胞 当它处于活动状态时有 2 个状态。这两个状态是

白色 黑色 第一条规则不同。

当一个细胞从“死亡”状态转变为“活着”状态时，它呈现出以下颜色： 3 个单元格中的大多数。由于 3 是奇数，所以多数总是存在。 其余规则遵循游戏原始版本。最初， 所有细胞都处于死亡状态。第一个玩家下白棋，然后 第二位玩家玩黑棋。每个玩家轮流切换一个 DEAD 细胞进入 ALIVE 状态。 ALIVE 单元格采用分配给 玩家。如此下去，直到每个玩家都放置了 40 个单元格。 网格上的相应颜色。然后游戏开始。活细胞 500 个生命周期结束时颜色最大的人获胜！

输入格式

第一个玩家由字符 w（ascii 值 119）表示， 第二个玩家由字符 b（ascii 值 98）表示。 输入的第一行代表玩家的角色。 29 接下来是几行。每行有 29 个字符，行与行之间没有空格 他们。活细胞由它们各自的字符表示， 死亡细胞用 -（ascii 值 45）表示。

输出

输出是 2 个单倍行距整数，表示 需要从 DEAD 切换到 ALIVE 的单元格。

官方问题站点上有示例输入和示例输出以及更多详细信息：https://www.hackerrank.com/challenges/conway

我想知道其他黑客使用什么算法。我现在就在列表的底部 - 任何其他观点都会非常有用。

Answer 1

康威生命游戏的两人版本非常有趣，到目前为止，我已经开发了一种可靠的算法并将其提交给 HackerRank（我的分数为 41.656）。

我写的程序试图在全盘设置对角线作为障碍，阻止对手部署常规策略，同时为我提供更多的复制和全盘展开的空间。

下面是我的实现（Python）：

#!/usr/bin/python
# Conway's game of life - set up diagonals across the board
BOARD_SIZE = 28;

#get the next move, 
def nextMove(player, board):
    b = [] #append to b
    for s in board:
        b.append(list(s))
    
    #check up left (rows) 
    for r in range(0, BOARD_SIZE, 2):
        if (b[BOARD_SIZE - r][BOARD_SIZE] == "-"):
            return BOARD_SIZE - r, BOARD_SIZE
        else:
            row, col= diagUL(b, BOARD_SIZE - r, BOARD_SIZE)
            if (row!= -1):
                return row, col
    
    #check up left (cols)
    for c in range(0, BOARD_SIZE, 2):
        if (b[BOARD_SIZE][BOARD_SIZE - c] == "-"):
            return BOARD_SIZE, BOARD_SIZE - c
        else:
            row, col= diagUL(b, BOARD_SIZE, BOARD_SIZE - c)
            if (row!= -1):
                return row, col
    
    #check up right (rows) 
    for r in range(0, BOARD_SIZE, 2):
        if (b[r][BOARD_SIZE] == "-"):
            return r, BOARD_SIZE
        else:
            row, col= diagUR(b, r, BOARD_SIZE)
            if (row!= -1):
                return row, col
    
    #check up right (cols)
    for c in range(0, BOARD_SIZE, 2):
        if (b[0][BOARD_SIZE - c] == "-"):
            return 0, BOARD_SIZE - c
        else:
            row, col= diagUR(b, 0, BOARD_SIZE - c)
            if (row!= -1):
                return row, col

#gets the diagonals (up right and up left) 
def diagUL(bd, r, c):
    if (r == 0 or c == 0):
        return -1, -1
    elif (bd[r - 1][c - 1] == "-"):
        return r - 1, c - 1
    else:
        return diagUL(bd, r - 1, c - 1)

def diagUR(bd, r, c):
    if (r == BOARD_SIZE or c == 0):
        return -1, -1
    elif (bd[r + 1][c - 1] == "-"):
        return r + 1, c - 1
    else:
        return diagUL(bd, x + 1, y - 1)

#i/o
player = raw_input()
board = []
for row in xrange(0, 29):
    board.append(raw_input())
a,b = nextMove(player, board)
print a,b

Answer 2

BOARD_SIZE = 28；

#采取下一步行动， def nextMove(玩家, 棋盘): b = [] #追加到b 对于板中的 s： b.append(列表)

#check up left (rows) 
for r in range(0, BOARD_SIZE, 2):
    if (b[BOARD_SIZE - r][BOARD_SIZE] == "-"):
        return BOARD_SIZE - r, BOARD_SIZE
    else:
        row, col= diagUL(b, BOARD_SIZE - r, BOARD_SIZE)
        if (row!= -1):
            return row, col

#check up left (cols)
for c in range(0, BOARD_SIZE, 2):
    if (b[BOARD_SIZE][BOARD_SIZE - c] == "-"):
        return BOARD_SIZE, BOARD_SIZE - c
    else:
        row, col= diagUL(b, BOARD_SIZE, BOARD_SIZE - c)
        if (row!= -1):
            return row, col

#check up right (rows) 
for r in range(0, BOARD_SIZE, 2):
    if (b[r][BOARD_SIZE] == "-"):
        return r, BOARD_SIZE
    if (b[r][BOARD_SIZE] == "-"):
        return r, BOARD_SIZE
    else:
        row, col= diagUR(b, r, BOARD_SIZE)
        if (row!= -1):
            return row, col

#check up right (cols)
for c in range(0, BOARD_SIZE, 2):
    if (b[0][BOARD_SIZE - c] == "-"):
        return 0, BOARD_SIZE - c
    else:
        row, col= diagUR(b, 0, BOARD_SIZE - c)
        if (row!= -1):
            return row, col

#获取对角线（右上和左上） def diagUL(bd, r, c): 如果（r == 0 或 c == 0）： 返回-1,-1 elif (bd[r - 1][c - 1] == "-"): 返回 r - 1, c - 1 别的： 返回 diagUL(bd, r - 1, c - 1)

def diagUR(bd, r, c): 如果（r == BOARD_SIZE 或 c == 0）： 返回-1,-1 elif (bd[r + 1][c - 1] == "-"): 返回 r + 1, c - 1 别的： 返回 diagUL(bd, x + 1, y - 1)