День 15: Списки | Игра Жизни

Я пытаюсь принять участие в 30-дневном соревновании по программированию на Python, и в этой статье я буду играть в игру жизни.

Правила:

1. Любая живая клетка, имеющая менее двух живых соседей, умирает, как будто из-за недостаточной численности населения.
2. Любая живая клетка с двумя или тремя живыми соседями продолжает жить до следующего поколения.
3. Любая живая клетка, имеющая более трех живых соседей, умирает, как будто от перенаселения.
4. Любая мертвая клетка, имеющая ровно три живых соседа, становится живой клеткой, как бы путем размножения.

Реализацию Игры Жизни вы можете найти в предыдущей статье:

Проблема:

Решение (неоптимальное):

def game_of_life(board):
    def count_neighbors(x, y):
        count = 0
        for i in range(-1, 2):
            for j in range(-1, 2):
                if i == 0 and j == 0:
                    continue
                nx, ny = x + i, y + j
                if 0 <= nx < len(board) and 0 <= ny < len(board[0]) and board[nx][ny] in (1, -1):
                    count += 1
        return count

    for i in range(len(board)):
        for j in range(len(board[0])):
            neighbors = count_neighbors(i, j)
            if board[i][j] == 1 and (neighbors < 2 or neighbors > 3):
                board[i][j] = -1
            elif board[i][j] == 0 and neighbors == 3:
                board[i][j] = 2

    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] == -1:
                board[i][j] = 0
            elif board[i][j] == 2:
                board[i][j] = 1


############################# OOP as well: #################################

class Solution(object):
    def __init__(self):
        self.board = []

    def count_neighbors(self, x, y):
        count = 0
        for i in range(-1, 2):
            for j in range(-1, 2):
                if i == 0 and j == 0:
                    continue
                nx, ny = x + i, y + j
                if 0 <= nx < len(self.board) and 0 <= ny < len(self.board[0]) and self.board[nx][ny] in (1, -1):
                    count += 1
        return count

    def gameOfLife(self, board):
        self.board = board
        for i in range(len(self.board)):
            for j in range(len(self.board[0])):
                neighbors = self.count_neighbors(i, j)
                if self.board[i][j] == 1 and (neighbors < 2 or neighbors > 3):
                    self.board[i][j] = -1
                elif self.board[i][j] == 0 and neighbors == 3:
                    self.board[i][j] = 2

        for i in range(len(self.board)):
            for j in range(len(self.board[0])):
                if self.board[i][j] == -1:
                    self.board[i][j] = 0
                elif self.board[i][j] == 2:
                    self.board[i][j] = 1

Объяснение:

1. Мы определяем вспомогательную функцию count_neighbors(x, y), которая принимает индексы строк и столбцов ячейки и возвращает количество живых соседей.
2. Мы перебираем строки и столбцы доски.
3. Для каждой ячейки мы подсчитываем живых соседей с помощью функции count_neighbors().
4. Мы применяем правила Игры Жизни, используя операторы if и elif. Чтобы избежать изменения исходной доски, мы помечаем ячейки, которые должны стать мертвыми, цифрой -1, а ячейки, которые должны стать живыми, — цифрой 2.
5. Мы снова проходим по доске, чтобы обновить ячейки до их нового состояния.

Вывод:

Этот подход эффективен, поскольку ему нужно всего лишь дважды пройти по доске: один раз для расчета нового состояния на основе соседей, а затем еще раз для обновления ячеек.

Отмечая ячейки знаками -1 и 2 вместо прямого изменения их состояния, мы избегаем изменения состояния доски в процессе применения правил. Это помогает гарантировать, что правила применяются правильно и одновременно к каждой ячейке.

Решение (оптимальное):

class Solution(object):
    def __init__(self):
        self.board = []

    def count_neighbors(self, x, y):
        directions = [(i, j) for i in range(-1, 2) for j in range(-1, 2) if i != 0 or j != 0]
        count = 0
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(self.board) and 0 <= ny < len(self.board[0]) and self.board[nx][ny] in (1, -1):
                count += 1
        return count

    def gameOfLife(self, board):
        self.board = board
        next_board = [[0] * len(self.board[0]) for _ in range(len(self.board))]

        for i in range(len(self.board)):
            for j in range(len(self.board[0])):
                neighbors = self.count_neighbors(i, j)
                if self.board[i][j] == 1 and (neighbors == 2 or neighbors == 3):
                    next_board[i][j] = 1
                elif self.board[i][j] == 0 and neighbors == 3:
                    next_board[i][j] = 1

        self.board[:] = next_board

Объяснение:

1. Мы обновили метод count_neighbors, используя понимание списка для создания переменной directions. Это упрощает код и делает его более читабельным.
2. Вместо того, чтобы дважды перебирать плату, мы создаем новую next_board с теми же размерами, что и исходная плата. Затем мы заполняем новое состояние непосредственно на этой новой доске на основе исходной доски. Это устраняет необходимость отмечать ячейки значениями -1 и 2 и выполнять двойную итерацию.
3. После расчета следующего состояния мы обновляем исходную плату на месте, используя назначение среза self.board[:] = next_board.

Заключение:

Оптимизированный код становится более кратким, а одиночный цикл сокращает количество итераций. Однако за это приходится платить увеличением использования памяти из-за создания файла next_board. Это компромисс между сложностью времени и сложностью пространства.

Лучшее решение:

class Solution(object):
    def __init__(self):
        self.board = []

    def gameOfLifeInfinite(self, live):
        ctr = collections.Counter((I, J)
                              for i, j in live
                              for I in range(i-1, i+2)
                              for J in range(j-1, j+2)
                              if I != i or J != j)
        return {ij
            for ij in ctr
            if ctr[ij] == 3 or ctr[ij] == 2 and ij in live}
    
    def gameOfLife(self, board):
        live = {(i, j) for i, row in enumerate(board) for j, live in enumerate(row) if live}
        live = self.gameOfLifeInfinite(live)
        for i, row in enumerate(board):
            for j in range(len(row)):
                row[j] = int((i, j) in live)

Дополнительные ресурсы:

Как игра жизни использовалась для создания искусства, довольно интересно!

Спасибо за чтение и за вашу поддержку.

Если что-то неясно или у вас возникли трудности, свяжитесь с нами через Medium или LinkedIn.