<jupyter_start><jupyter_text>Improving Performance of Invasion Percolation* Use sets<jupyter_code>import numpy as np
import random
def percolation(size, spread):
    """
    Simulate invasion percolation on a size x size grid with values in [1..spread],
    reporting density of final filled shape.
    """

    assert (type(size) == int) and ((size > 0) and (size % 2 == 1)), 'size must be positive odd integer'
    assert (type(spread) == int) and (spread > 0), 'spread must be non-negative integer'
    grid = make_grid(size, spread)
    boundary = make_boundary(spread)
    chosen = (int(size/2), int(size/2))
    fill(grid, chosen)
    while not on_boundary(grid, chosen):
        extend_boundary(grid, boundary, chosen)
        chosen = choose_next(grid, boundary)
        fill(grid, chosen)
    return grid, calculate_density(grid)
def make_grid(size, spread):
    """
    Create size x size grid filled with values in [1..spread].
    """
    return np.random.randint(low=1, high=spread+1, size=(size, size))
def fill(grid, loc):
    """
    Mark a cell as filled.
    """
    grid[loc] = 0
def on_boundary(grid, loc):
    """
    Is the specified cell on the boundary of the grid?
    """
    grid_x, grid_y = grid.shape
    loc_x, loc_y = loc
    return (loc_x == 0) or (loc_y == 0) or (loc_x == (grid_x -1)) or (loc_y == (grid_y -1))

def test_on_boundary():
    grid = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
    assert on_boundary(grid, (0, 0))
    assert not on_boundary(grid, (1, 1))
    assert on_boundary(grid, (2, 0))
def calculate_density(grid):
    """
    Return proportion of cells that are filled.
    """
    filled = np.sum(grid == 0)
    return filled / grid.size
def make_boundary(spread):
    """
    Create object to keep track of boundary cells.
    """
    result = []
    for i in range(spread + 1):
        result.append(set())
    return result

def test_make_boundary():
    assert make_boundary(3) == [set(), set(), set(), set()]
def extend_boundary(grid, boundary, loc):
    """
    Extend boundary with unfilled cells next to given location.
    """
    loc_x, loc_y = loc
    for (x, y) in ((loc_x-1, loc_y), (loc_x + 1, loc_y), (loc_x, loc_y-1), (loc_x, loc_y+1)):
        if grid[x, y] != 0:
            boundary[grid[x, y]].add((x, y))

def test_extend_boundary():
    grid = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
    boundary = make_boundary(9)
    extend_boundary(grid, boundary, (1, 1))
    assert boundary == [set(), set(), {(0, 1)}, set(), {(1, 0)}, set(), {(1, 2)}, set(), {(2, 1)}, set()]

test_extend_boundary()
def choose_next(grid, boundary):
    """
    Find and return coordinates of next grid cell to fill.
    """
    for val in range(len(boundary)):
        if boundary[val]:
            break
    loc = random.choice(list(boundary[val]))
    boundary[val].discard(loc)
    return loc
def is_adjacent(grid, loc):
    """
    Is the location (x, y) adjacent to a filled cell?
    """
    x, y = loc
    max_x, max_y = grid.shape
    if grid[loc] == 0:
        return False
    if (x > 0) and (grid[x-1, y] == 0):
        return True
    if (y > 0) and (grid[x, y-1] == 0):
        return True
    if (x < max_x-1) and (grid[x+1, y] == 0):
        return True
    if (y < max_y-1) and (grid[x, y+1] == 0):
        return True
    return False

def test_is_adjacent():
    grid = np.array([[0, 1, 2], [3, 4, 5], [6, 7, 8]])
    assert not is_adjacent(grid, (0, 0))
    assert is_adjacent(grid, (1, 0))
    assert is_adjacent(grid, (0, 1))
    assert not is_adjacent(grid, (1, 1))
    assert not is_adjacent(grid, (2, 0))
    assert not is_adjacent(grid, (2, 1))
    assert not is_adjacent(grid, (0, 2))
    assert not is_adjacent(grid, (1, 2))
    assert not is_adjacent(grid, (2, 2))
def test_all():
    test_on_boundary()
    test_is_adjacent()
    test_make_boundary()
test_all()
percolation(5, 5)
import timeit
timeit.timeit(stmt='percolation(21, 10)', number=200, setup='from __main__ import percolation')<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup