Q1(i)

State the complexity of calculate_next_grid() and explain your reasoning. Note that all operations on lists inside the loops are constant time operations, as is the call to get_neighbours(). Write your answer here:

Q1(ii)

Identify whether calculate_next_grid() has the same or different worst-case and best-case complexities; justify your conclusions. Write your answer here:

Q1(iii)

The function get_neighbours accepts similar parameters to calculate_next_grid. State the complexity of get_neighbours. Compare the complexity of the two functions and discuss your conclusions. Write your answer here:

SOURCE OF CODE:

# Note: comment blocks left out to save space def print_grid(grid: list) -> None: for row in grid: for cell in row: print('[' + cell + ']', end='') print()

def get_neighbours(grid: list, row: int, col: int) -> int: num_neighbours = 0 # above row if row > 0: # check above if col != 0: # check left above if grid[row-1][col-1] == '@': num_neighbours += 1 if grid[row-1][col] == '@': # check direcly above num_neighbours += 1 if col != len(grid[row])-1: # check right above if grid[row-1][col+1] == '@': num_neighbours += 1 if col != 0: # check left if grid[row][col-1] == '@': num_neighbours += 1 if col != len(grid[row])-1: # check right if grid[row][col+1] == '@': num_neighbours += 1 # below row if row < len(grid)-1: # check below if col != 0: # check left below if grid[row+1][col-1] == '@': num_neighbours += 1 if grid[row+1][col] == '@': # check direcly below num_neighbours += 1 if col != len(grid[row])-1: # check right below if grid[row+1][col+1] == '@': num_neighbours += 1 return num_neighbours

def calculate_next_grid(old_grid: list, num_rows: int, num_cols: int) -> list: new_grid = [] for row_index in range(num_rows): new_row = [] for col_index in range(num_cols): num_neighbours = get_neighbours(old_grid, row_index, col_index) current_cell = old_grid[row_index][col_index] if current_cell == '@': if num_neighbours == 2 or num_neighbours == 3: new_row.append('@') else: new_row.append(' ') else: if num_neighbours == 3: new_row.append('@') else: new_row.append(' ') new_grid.append(new_row) return new_grid

def make_grid(rows:int, cols:int) -> list: import random grid = [] for row in range(rows): new_row = [] for col in range(cols): chance = random.randint(0, 3) if chance == 1: new_row.append('@') else: new_row.append(' ') grid.append(new_row) return grid

def run_program(generations: int, num_rows: int, num_cols: int) -> None: grid = make_grid(num_rows, num_cols) current_generation = 0 while current_generation < generations: print('Generation', current_generation) print_grid(grid) grid = calculate_next_grid(grid, num_rows, num_cols) current_generation += 1

run_program(10, 5, 7)

OUTPUT:

Generation 0 [ ][ ][ ][ ][ ][ ][ ] [ ][ ][@][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][@][@][ ][ ] [ ][ ][@][ ][ ][@][ ] Generation 1 [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][@][ ][ ][ ] [ ][ ][ ][@][@][ ][ ] [ ][ ][ ][@][@][ ][ ] Generation 2 [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][@][@][ ][ ] [ ][ ][@][ ][ ][ ][ ] [ ][ ][ ][@][@][ ][ ] Generation 3 [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][@][ ][ ][ ] [ ][ ][@][ ][ ][ ][ ] [ ][ ][ ][@][ ][ ][ ] Generation 4 [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][@][@][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] Generation 5 [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] Generation 6 [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] Generation 7 [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] Generation 8 [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] Generation 9 [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ] [ ][ ][ ][ ][ ][ ][ ]