Алгоритмы игры жизни HackerRank Конвея

Недавно я закончил решать интересную HackerRank задачу под названием «Игра жизни Конвея». Постановка задачи следующая:

Game of Life - игра с клеточными автоматами, разработанная британским математиком Джоном Хортоном Конвеем. Оригинальная игра - это игра с нулевым игроком. Его развитие полностью зависит от его вклада.

Игра жизни происходит на 2D-сетке. Каждая ячейка в сетке будет в одном из двух возможных состояний:

ЖИВОЙ МЕРТВОЙ Рождение или смерть клеток основывается на следующих правилах.

Клетка переключается с МЕРТВОЙ на ЖИВУЮ, если ее окружают ровно 3 живые клетки. Клетка остается живой, если ее окружают 2 или 3 живые клетки. Клетка переключается с ЖИВОЙ на МЕРТВУ, если она окружена более чем 3 живыми клетками из-за перенаселенности. Клетка переключается с ЖИВОЙ на МЕРТВУ, если она окружена менее чем двумя клетками из-за недостаточного количества населения. Каждая ячейка окружена 8 ячейками, 4 по бокам и 4 по углам. Ячейки в крайних углах имеют только 3 соседа, а ячейки в крайнем правом, левом, верхнем и нижнем углу доски имеют 5 соседних ячеек. Вышеупомянутые правила применимы и к этим ячейкам.

В этой версии Game of Life используется сетка 29x29, верхняя левая ячейка (0,0), а нижняя правая ячейка (28,28). Он индексируется как (строка, столбец), как массивы в информатике. Два игрока играют друг против друга. Что отличает эту игру от оригинала, так это то, что у клетки есть 2 состояния, когда она ЖИВАЯ. Два государства

БЕЛЫЙ ЧЕРНЫЙ Первое правило отличается.

Когда ячейка переключается с МЕРТВОЙ на ЖИВУЮ, она принимает цвет большинства из 3-х ячеек. Поскольку 3 нечетно, всегда существует большинство. Остальные правила соответствуют оригинальной версии игры. Изначально все ячейки находятся в МЕРТВОМ состоянии. Первый игрок играет БЕЛЫМ, а второй - ЧЕРНЫМ. Каждый игрок по очереди переводит одну МЕРТВУЮ ячейку в ЖИВОЕ состояние. ЖИВАЯ ячейка принимает цвет, назначенный игроку. Это продолжается до тех пор, пока каждый игрок не разместит на сетке 40 ячеек соответствующего цвета. Затем игра начинается. Победа в игре - наличие живых клеток максимального цвета в конце 500 жизненных циклов!

Формат ввода

Первый игрок представлен символом w (значение ascii 119), а второй игрок представлен символом b (значение ascii 98). Первая строка ввода представляет характер игрока. Далее следуют 29 строк. Каждая строка состоит из 29 символов без пробелов между ними. Живые ячейки представлены соответствующими символами, а мертвые ячейки представлены знаком - (значение ascii 45).

Вывод

Выходные данные - 2 целых числа, разделенных одиночными интервалами, которые указывают положение ячейки, которую нужно переключить с МЕРТВОЙ на ЖИВОЙ.

На официальном сайте проблемы можно найти образцы входных и выходных данных, а также более подробную информацию: https://www.hackerrank.com/challenges/conway

Мне было интересно, какие алгоритмы использовали другие хакеры. Я сейчас как раз в самом конце списка - любая другая перспектива была бы чрезвычайно полезной.


algorithm conways-game-of-life
person Franz Alfrendo    schedule 24.04.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Версия для двух игроков «Игры жизни» Конвея чрезвычайно интересна, и до сих пор я разработал и представил один надежный алгоритм в 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
person manan    schedule 24.04.2014
comment
Интересно, я разберусь. Спасибо за ответ! - person Franz Alfrendo; 24.04.2014