For Day 11, the puzzle is Conway’s Game of Life with modified rules, applied to changing seats in a restaurant. The basic idea of the game is that given an initial configuration, the world is updated according to a set of rules, either forever or until some stable state or number of iterations is reached (depending on the goal of the simulation). For part 1, the rules for the simulation are:

  • An empty with no adjacent occupied seats becomes occupied.
  • An occupied seat with four or more adjacent occupied seats becomes empty.

I used NumPy’s fancy array indexing to solve this puzzle, starting with turning the input grid (L is empty, . is a floor, and # is occupied):

L.LL.LL.LL
LLLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLLL
L.LLLLLL.L
L.LLLLL.LL

Into a NumPy array:

with open(args.input, "r") as in_file:
    grid = []
    for line in in_file:
        row = []
        for c in line.strip():
            row.append(c)
        grid.append(row)
grid = np.array(grid)
grid_orig = grid.copy()

To update the grid using the rules for part 1, I wrote a make_grid function:

def make_grid(grid, iterations):
    ret = grid.copy()

    for index, state in np.ndenumerate(grid):
        row, col = index
        adjacent = grid[
            max(row - 1, 0) : min(row + 2, grid.shape[0]),
            max(col - 1, 0) : min(col + 2, grid.shape[1]),
        ]
        occupied = np.sum(adjacent == "#") - (grid[index] == "#")
        if state == "L" and occupied == 0:
            # Empty seats become occupied if there are no adjacent occupied seats
            ret[index] = "#"
        elif state == "#" and occupied >= 4:
            ret[index] = "L"

    return ret, iterations + 1

This function iterates over each individual index in the NumPy array, yielding (row, column) tuples and the value at the index:

    for index, state in np.ndenumerate(grid):
        row, col = index

It uses NumPy array indexing to check all adjacent neighbors and count the number of occupied seats:

        adjacent = grid[
            max(row - 1, 0) : min(row + 2, grid.shape[0]),
            max(col - 1, 0) : min(col + 2, grid.shape[1]),
        ]
        occupied = np.sum(adjacent == "#") - (grid[index] == "#")

Note that the grid indexing takes care of the edge of the grid using some min/max operations and the grid shape.

Finally, each state is updated in the return array ret:

        if state == "L" and occupied == 0:
            # Empty seats become occupied if there are no adjacent occupied seats
            ret[index] = "#"
        elif state == "#" and occupied >= 4:
            ret[index] = "L"

This function also returns the number of iterations, to help keep track of how long the simulation had to run to reach a stable state. Here is a visualization of the game:

For part 2, the rules of the simulation change:

  • Instead of adjacent seats, consider the first visible seat in each direction.
  • An empty with no visible occupied seats becomes occupied.
  • An occupied seat with five or more visible occupied seats becomes empty.

To do this, I wrote a few new funcions. in_bounds is a simple bounds check, to make sure we don’t try to index outside of the array:

def in_bounds(row, col, shape):
    if row < 0 or col < 0:
        return False
    if row >= shape[0] or col >= shape[1]:
        return False
    return True

count_los is a function that counts the line-of-sight seats given a location and a delta for the row and column:

def count_los(row, col, dr, dc, grid):
    row_iter = row + dr
    col_iter = col + dc

    while in_bounds(row_iter, col_iter, grid.shape):
        if grid[row_iter, col_iter] == "#":
            return 1
        if grid[row_iter, col_iter] == "L":
            return 0
        row_iter += dr
        col_iter += dc

    return 0

make_los_grid is the line-of-sight analog to make_grid from part 1:

def make_los_grid(grid, iterations):
    ret = grid.copy()
    occ_grid = np.zeros(grid.shape)

    for index, state in np.ndenumerate(grid):
        row, col = index
        occupied = 0
        # Up
        occupied += count_los(row, col, -1, 0, grid)
        # Down
        occupied += count_los(row, col, 1, 0, grid)
        # Left
        occupied += count_los(row, col, 0, -1, grid)
        # Right
        occupied += count_los(row, col, 0, 1, grid)
        # UpRight
        occupied += count_los(row, col, -1, 1, grid)
        # DownRight
        occupied += count_los(row, col, 1, 1, grid)
        # UpLeft
        occupied += count_los(row, col, -1, -1, grid)
        # DownLeft
        occupied += count_los(row, col, 1, -1, grid)
        if grid[row, col] == "L" and occupied == 0:
            ret[row, col] = "#"
        elif grid[row, col] == "#" and occupied >= 5:
            ret[row, col] = "L"
        if grid[row, col] == "L" or grid[row, col] == "#":
            occ_grid[index] = occupied

    return ret, iterations + 1, occ_grid

Other than the changed rules, the simulation for part 2 is identical to part 1:

    states_p2 = []
    grid = grid_orig.copy()
    if args.visualize:
        states_p2.append(GameState(grid.copy(), 0))
    new_grid, iterations, occ = make_los_grid(grid, 0)
    if args.visualize:
        states_p2.append(GameState(new_grid.copy(), iterations))
    while np.any(new_grid != grid):
        grid = new_grid.copy()
        new_grid, iterations, occ = make_los_grid(grid, iterations)
        if args.visualize:
            states_p2.append(GameState(new_grid.copy(), iterations))
    p2 = np.sum(new_grid == "#")

Visualization of part 2: