<jupyter_start><jupyter_text>Conway's Game of Life - Unlimited Editition - 3 kyu[Kata Source](http://www.codewars.com/kata/52423db9add6f6fc39000354)Given a 2D array and a number of generations, compute n timesteps of Conway's Game of Life.The rules of the game are: 1. Any live cell with fewer than two live neighbours dies, as if caused by underpopulation. 2. Any live cell with more than three live neighbours dies, as if by overcrowding. 3. Any live cell with two or three live neighbours lives on to the next generation. 4. Any dead cell with exactly three live neighbours becomes a live cell.Each cell's neighborhood is the 8 cells immediately around it. The universe is infinite in both the x and y dimensions and all cells are initially dead - except for those specified in the arguments. The return value should be a 2d array cropped around all of the living cells. (If there are no living cells, then return [[]].)For illustration purposes, 0 and 1 will be represented as ░░ and ▓▓ blocks respectively. You can take advantage of the htmlize function to get a text representation of the universe: eg:<jupyter_code>from IPython.core.display import display, HTML


def htmlize(array):

    full = "▓▓"
    empty = "░░"

    s = []
    for row in array:
        for cell in row:
            s.append(full if cell else empty)
        s.append('<br/>')
    output = ''.join(s)
    display(HTML(output))


# htmlize(cells)<jupyter_output><empty_output><jupyter_text>SolutionWe need a representation of the board that we can iterate in an arbitrary order and that can be very large and sparse. A matrix or table will not do as it will contain a substential amount of zeros. We will use a set for this. We need a function to convert a table to a set.<jupyter_code>def convert_table_to_set(table):

    ni = len(table)
    nj = len(table[0])

    s = set()
    for i in range(ni):
        for j in range(nj):
            if table[i][j]:
                s.add((i, j))

    return s<jupyter_output><empty_output><jupyter_text>We also need a function to convert a set to a cropped table.<jupyter_code>def convert_set_to_table(s):

    if not s:
        mi = mj = ni = nj = 0
    else:
        min_i = min(map(lambda x: x[0], s))
        min_j = min(map(lambda x: x[1], s))
        max_i = max(map(lambda x: x[0], s))
        max_j = max(map(lambda x: x[1], s))

    range_i = max_i - min_i + 1
    range_j = max_j - min_j + 1

    table = [[False for j in range(range_j)] for i in range(range_i)]

    for (i, j) in s:
        table[i - min_i][j - min_j] = True

    return table<jupyter_output><empty_output><jupyter_text>For each generations... * We iterate over all the cells currently active and create a set containing those along with their neighbours. * We then iterate over all of those, count the neighbours that are alive, and decide whether the cell should be alive or not in the next generation.<jupyter_code>from itertools import product


def get_generation(cells, generations):

    cells = convert_table_to_set(cells)

    for n in range(generations):

        cells_neigh = set()
        cells_new = set()

        for (i, j) in cells:
            for (di, dj) in product((-1, 0, 1), (-1, 0, 1)):
                cells_neigh.add((i + di, j + dj))

        for (i, j) in cells_neigh:
            neighbours = 0
            for (di, dj) in product((-1, 0, 1), (-1, 0, 1)):
                if (i + di, j + dj) in cells and (di, dj) != (0, 0):
                    neighbours += 1

            if neighbours == 3:
                cells_new.add((i, j))
            elif neighbours == 2 and (i, j) in cells:
                cells_new.add((i, j))

        cells = cells_new

    return convert_set_to_table(cells)<jupyter_output><empty_output><jupyter_text>TestHere's the provided tests.<jupyter_code>start = [[1, 0, 0],
         [0, 1, 1],
         [1, 1, 0]]
end = [[0, 1, 0],
       [0, 0, 1],
       [1, 1, 1]]

output = get_generation(start, 1)
htmlize(output)

assert output == end<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10019890601690701, 'fraction_numerical': 0.017652909000497267, 'mean_word_length': 2.813270142180095, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '633955', 'license': 'BSD-2-Clause', 'n_tokens_mistral': 1356, 'n_tokens_neox': 1258, 'n_words': 516, 'path': "3 kyu - Conway's Game of Life - Unlimited Edition.ipynb", 'repo_name': 'vincentqb/codewars', 'size': '4022'}