I recently ran across this problem in Codewars which boiled down to manipulating lists of lists in Python.
The objective is to show the end results of the pixels according to the rules of Conway’s Game of Life. Each list contain the same number of elements which are 1s and 0s which represent on/off pixels in the grid, or in our case Living/Dead. You are also given the number of generations to iterate through.
The very first thing is that data could be converted into NumPy arrays but for the first attempt I wanted to keep the data structure given to me. Meaning, I didn’t wanted to solve the problem “as is”.
What the GoL boils down to is that if a living cell has 2 or 3 neighbors it survives but number higher or lower than that causes it to die. The other rule is that a dead cell will revive if it has exactly 3 living neighbors. The one extra requirement is that your output must not contain outside rows or columns void of any living cells, so we basically have to crop our grid.
The image to the left shows the 3 x 3 grids. The top grid which is the input is represented by [[1,0,0], [0,1,1],[0,1,0]] and 2 generations later we return the bottom grid as [[1,0,0],[0,1,1],[1,1,0]]. The middle grid was used to monitor the progress of my output.
In order to start thinking about this correctly it was implied that the outer layers of the grid needed to be evaluated though they were not provided in the input. For example, if we are given a 3X3 array then we need to check a field of 5X5 to evaluate the states of the outmost adjacent cells.
The reverse was true that after each generation the grid would need to be pared down so the 5 x 5 grid would get reduced down to 3 x 3 for the output or for the next evaluation. I grant that in refactoring the code we may decide better about always paring down the grid for each intermediate step but including it helped keep my code symmetrical and organised.
I took the challenge on and did my best to break down the code into discrete functions and after may hours of work I came to what I could say was my best quick and dirty answer. I will use this as an opportunity to refactor my work and learn some improvements.
from preloaded import htmlize # this can help you debug your code
def create_new_array(cells : list[list[int]]):
x = len(cells[0])
y = len(cells)
new_x = x + 2
new_y = y + 2
new_cells = []
for i in range(new_y):
new_row = [0 for i in range(new_x)]
new_cells.append(new_row)
return new_cells
def inscribe_living_cells(cells):
inscribe_cells = []
for row_index, each_row in enumerate(cells):
for cell_index, each_cell in enumerate(each_row):
if each_cell == 1:
coordinates = tuple()
coordinates = (row_index,cell_index)
inscribe_cells.append(coordinates)
return inscribe_cells
def transpose_living_cells(inscribed_living_cells):
transposed_living_cells = []
for coord in inscribed_living_cells:
transposed_coord = (coord[0] + 1, coord[1] + 1)
transposed_living_cells.append(transposed_coord)
return transposed_living_cells
def transcribe_living_cells(transposed_living_cells_to_transcribe, new_cells):
new_cells
for coord in transposed_living_cells_to_transcribe:
new_cells[coord[0]][coord[1]] = 1
return new_cells
def apply_game_rules_to_new_cells(transcribed_cells,new_cells,row_index,cell_index,total):
if transcribed_cells[row_index][cell_index] == 0:
if total == 3:
new_cells[row_index][cell_index] = 1
else:
new_cells[row_index][cell_index] = 0
elif transcribed_cells[row_index][cell_index] == 1:
if total < 2:
new_cells[row_index][cell_index] = 0
elif total > 3:
new_cells[row_index][cell_index] = 0
else:
new_cells[row_index][cell_index] = 1
def evaluate_and_add_values_new_cells(transcribed_cells, new_cells):
for row_index, row in enumerate(transcribed_cells):
down_limit = len(transcribed_cells)-1
right_limit = len(row) -1
#trust limits (down, right)
for cell_index, cell in enumerate(row):
# Set directions
left = cell_index - 1
right = cell_index + 1
up = row_index - 1
down = row_index + 1
#conditional of limits (down, right)
if row_index == down_limit:
if cell_index == right_limit:
sum_list = [transcribed_cells [row_index] [left],
transcribed_cells [up] [cell_index],
transcribed_cells [up] [left]]
total = sum(sum_list)
apply_game_rules_to_new_cells(transcribed_cells,new_cells,row_index,cell_index,total)
else:
sum_list = [transcribed_cells [row_index] [left],
transcribed_cells [row_index] [right],
transcribed_cells [up] [cell_index],
transcribed_cells [up] [left],
transcribed_cells [up] [right]]
total = sum(sum_list)
apply_game_rules_to_new_cells(transcribed_cells,new_cells,row_index,cell_index,total)
elif cell_index == right_limit:
sum_list = [transcribed_cells [row_index] [left],
transcribed_cells [up] [cell_index],
transcribed_cells [down] [cell_index],
transcribed_cells [up] [left],
transcribed_cells [down] [left]]
total = sum(sum_list)
apply_game_rules_to_new_cells(transcribed_cells,new_cells,row_index,cell_index,total)
else:
sum_list = [transcribed_cells [row_index] [left],
transcribed_cells [row_index] [right],
transcribed_cells [up] [cell_index],
transcribed_cells [down] [cell_index],
transcribed_cells [up] [left],
transcribed_cells [up] [right],
transcribed_cells [down] [left],
transcribed_cells [down] [right]]
total = sum(sum_list)
apply_game_rules_to_new_cells(transcribed_cells,new_cells,row_index,cell_index,total)
def crop_new_cells(new_cells):
cropping = new_cells
first_column = [i[0] for i in cropping]
last_column = [i[-1] for i in cropping]
first_row = cropping[0]
last_row = cropping[-1]
while sum(first_column) == 0:
for row in cropping:
row.pop(0)
first_column = [i[0] for i in cropping]
while sum(last_column) == 0:
for row in cropping:
row.pop(-1)
last_column = [i[-1] for i in cropping]
while sum(first_row) == 0:
cropping.pop(0)
first_row = cropping[0]
while sum(last_row) == 0:
cropping.pop(-1)
last_row = cropping[-1]
return(cropping)
def get_generation(cells : list[list[int]], generations : int) -> list[list[int]]:
print(' ')
print(htmlize(cells))
sums = sum([sum(sublist) for sublist in cells])
if sums == 0:
cells = [[]]
return cells
elif generations == 0:
return cells
while generations > 0:
#inscribe living cells
original_living_cells = inscribe_living_cells(cells)
# create new expanded array
new_cells = create_new_array(cells)
#transpose living cells
transposed_living_cells_to_transcribe = transpose_living_cells(original_living_cells)
#transcribe living cells into new expanded array
transcribed_cells = transcribe_living_cells(transposed_living_cells_to_transcribe, new_cells)
# create new array to evaluate
new_cells = create_new_array(cells)
# get values for evaulation and resolve
evaluate_and_add_values_new_cells(transcribed_cells,new_cells)
# crop new array
crop_new_cells(new_cells)
print(' ')
print(htmlize(new_cells))
cells = new_cells
generations -= 1
return cells
Now…this is a big chunk of code. I don’t want to confess how long it took me but lets say a it was few hours later on the same day. I also assured that I follow a good organisation and did my best to keep separation of concerns to keep the code reusable. I want to use good names, following the idea that you should write code that doesn’t need commentary.
I want to refactor and reflect on other solutions. Here is a solution that I found as adequate analog to the approach I tried to take. I’m not convinced the cleverest, shortest solution is the best way to code.
def get_generation(cells, gen):
ng = Life(cells)
return Life.process(ng, gen)
class Life:
neighbor = [(x,y) for x in range(-1,2) for y in range(-1,2) if x or y]
def __init__(self, cells):
self.cells = [e[::] for e in cells]
self._forLife = lambda x ,y : int(self._express(x,y) in (2,3))
self._forDead = lambda x ,y : int(self._express(x,y)==3)
@property
def _lenY(self):
return len(self.cells[0])
@property
def core(self):
return { (x,y):c for x, e in enumerate(self.cells) for y, c in enumerate(e)}
def _express(self , xc,yc):
core = self.core
return sum(self.cells[(x+xc)][(y+yc)] for x,y in self.neighbor if core.get((x+xc,y+yc))!=None )
@classmethod
def process(cls, self, gen):
for _ in range(gen):
cls._add_field(self)
nextG = [e[::] for e in self.cells]
for (x,y),c in self.core.items():
nextG[x][y] = {0:self._forDead, 1:self._forLife}.get(c)(x,y)
self.cells = cls._del_field(nextG)
return self.cells
@classmethod
def _add_field(cls, self):
for _ in range(4):
self.cells = [list(e) for e in zip(* self.cells[::-1])]
if any( self.cells[0]): self.cells.insert(0,[0]*(self._lenY))
@staticmethod
def _del_field( field, cut = 4):
for _ in range(4):
field = [list(e) for e in zip(* field[::-1])]
while not any( field[0]): field.pop(0)
return field