HackerRank Conway的生命游戏算法

Question

我最近已经解决了名为“康威的人生游戏”的有趣的黑客问题问题陈述如下：

《生命的游戏》是一款由英国数学家约翰·霍顿·康威设计的细胞自动机游戏。最初的游戏是零人游戏。它的发展完全取决于它的投入。

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

活死人细胞的出生或死亡是基于以下规则。

如果一个细胞正好被3个活细胞包围，它就会从死细胞转换为活细胞。如果一个细胞被2或3个活细胞包围，它仍然是活的。如果一个细胞被3个以上的活细胞包围，因为细胞数量过多，它就会从活细胞变成死细胞。如果由于种群不足而被少于2个细胞包围，则细胞从活着变为死亡。每个细胞被8个细胞包围，4个在其侧面，4个在其角落。在极角的单元格只有3个相邻的单元格和在极右，左，顶部和底部的单元格有5个相邻的单元格。上述规则也适用于这些单元。

这个版本的游戏生活发生了一个29x29的网格，左上角的单元格是（0,0）和右下角的单元格是（28,28）。它像计算机科学中的数组一样被索引为（行、列）。两个球员互相比赛。这个游戏与原来的不同之处在于，一个单元格在活着时有两个状态。这两个州是

黑白第一条规则不同。

当一个单元格从死亡切换到活着时，它假设3个单元格中大多数的颜色。因为3是奇数，所以多数总是存在的。其余的规则遵循游戏的原始版本。最初，所有细胞都处于死亡状态。第一个玩家玩白色，第二个玩家玩黑色。每个玩家轮流将一个死亡细胞切换到活着状态。ALIVE单元格采用分配给玩家的颜色。这一直持续到每个玩家在网格上放置了40个各自颜色的细胞。游戏随后开始。在500个生命周期结束时颜色最大的活细胞赢得比赛！

输入格式

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

输出

输出为2个单间隔整数，表示需要从死区切换到活区的单元格位置。

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

我想知道其他黑客使用了什么算法。我现在就在列表的底部——任何其他的视角都非常有用。

Answer 1

康威《生活的游戏》的两人版非常有趣，到目前为止，我已经开发并向哈克朗克提交了一个可靠的算法（我的分数为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