首页 文章

HackerRank Conway的生命游戏算法

提问于
浏览
0

我最近完成了解决题为"Conway's Game Of Life."的有趣 HackerRank 问题 . 问题陈述如下:

Game of Life是由英国数学家John Horton Conway设计的细胞自动机游戏 . 原始游戏是零玩家游戏 . 它的演变完全取决于它的输入 . 生命游戏发生在2D网格上 . 网格中的每个单元格将处于两种可能状态之一,ALIVE DEAD单元格的出生或死亡基于以下规则 . 如果细胞由3个活细胞完全包围,则细胞从DEAD切换到ALIVE . 如果细胞被2或3个活细胞包围,它仍然存活 . 如果由于人口过多而被3个以上的活细胞包围,则细胞从ALIVE切换到DEAD . 如果由于人口不足而被小于2个单元包围,则单元从ALIVE切换到DEAD . 每个细胞被8个细胞包围,其侧面4个,角落4个 . 极端角落的单元只有3个邻居,并且板的最右侧,左侧,顶部和底部的单元具有5个相邻单元 . 上述规则也适用于这些细胞 . 这个版本的生命游戏取代了29x29网格,左上角的单元格是(0,0),右下角的单元格是(28,28) . 它被编入索引为(行,列),就像计算机科学中的数组一样 . 两名球员互相对抗 . 这个游戏与原版的不同之处在于,当ALIVE时,一个单元格有2个状态 . 两个州是白色黑色第一个规则不同 . 当单元格从DEAD切换到ALIVE时,它会呈现3个单元格中大部分单元格的颜色 . 由于3是奇数,因此多数总是存在 . 其余规则遵循游戏的原始版本 . 最初,所有细胞都处于DEAD状态 . 第一个玩家玩白色,第二个玩家玩黑色 . 每个玩家轮流将一个DEAD单元切换到ALIVE状态 . ALIVE单元格采用分配给播放器的颜色 . 这种情况一直持续到每个玩家在网格上放置了40个相应颜色的单元格 . 然后比赛开始了 . 在500个生命周期结束时最大颜色的活细胞赢得了游戏!输入格式第一个玩家用字符w(ascii值119)表示,第二个玩家用字符b(ascii值98)表示 . 输入的第一行代表玩家的角色 . 接下来是29行 . 每行有29个字符,它们之间没有任何空格 . 活细胞由它们各自的特征表示,死细胞用 - (ascii值45)表示 . 输出输出是2个单行间隔整数,表示需要从DEAD切换到ALIVE的单元格的位置 .

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

我想知道其他黑客使用的算法 . 我现在正好在列表的底部 - 任何其他视角都非常有用 .

1 回答

  • 0

    Conway的生命游戏的两个玩家版本非常有趣,到目前为止,我已经开发并向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
    

相关问题