11.md

Day 11 - Seating System - Code

Note: This problem is based off of Conway's Game of Life.

Your plane lands with plenty of time to spare. The final leg of your journey is a ferry that goes directly to the tropical island where you can finally start your vacation. As you reach the waiting area to board the ferry, you realize you're so early, nobody else has even arrived yet!

By modeling the process people use to choose (or abandon) their seat in the waiting area, you're pretty sure you can predict the best place to sit. You make a quick map of the seat layout (your puzzle input).

The seat layout fits neatly on a grid. Each position is either floor (.), an empty seat (L), or an occupied seat (#). For example, the initial seat layout might look like this:

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

Now, you just need to model the people who will be arriving shortly. Fortunately, people are entirely predictable and always follow a simple set of rules. All decisions are based on the number of occupied seats adjacent to a given seat (one of the eight positions immediately up, down, left, right, or diagonal from the seat). The following rules are applied to every seat simultaneously:

• If a seat is empty (L) and there are no occupied seats adjacent to it, the seat becomes occupied.
• If a seat is occupied (#) and four or more seats adjacent to it are also occupied, the seat becomes empty.
• Otherwise, the seat's state does not change.

Floor (.) never changes; seats don't move, and nobody sits on the floor.

After one round of these rules, every seat in the example layout becomes occupied:

#.##.##.##
#######.##
#.#.#..#..
####.##.##
#.##.##.##
#.#####.##
..#.#.....
##########
#.######.#
#.#####.##

After a second round, the seats with four or more occupied adjacent seats become empty again:

#.LL.L#.##
#LLLLLL.L#
L.L.L..L..
#LLL.LL.L#
#.LL.LL.LL
#.LLLL#.##
..L.L.....
#LLLLLLLL#
#.LLLLLL.L
#.#LLLL.##

This process continues for three more rounds:

#.##.L#.##
#L###LL.L#
L.#.#..#..
#L##.##.L#
#.##.LL.LL
#.###L#.##
..#.#.....
#L######L#
#.LL###L.L
#.#L###.##

#.#L.L#.##
#LLL#LL.L#
L.L.L..#..
#LLL.##.L#
#.LL.LL.LL
#.LL#L#.##
..L.L.....
#L#LLLL#L#
#.LLLLLL.L
#.#L#L#.##

#.#L.L#.##
#LLL#LL.L#
L.#.L..#..
#L##.##.L#
#.#L.LL.LL
#.#L#L#.##
..L.L.....
#L#L##L#L#
#.LLLLLL.L
#.#L#L#.##

At this point, something interesting happens: the chaos stabilizes and further applications of these rules cause no seats to change state! Once people stop moving around, you count 37 occupied seats.

Simulate your seating area by applying the seating rules repeatedly until no seats change state. How many seats end up occupied?

Part B

The neighbors are no longer just the 8 adjacent squares: they're 8 directions now. If for instance, on your right you have a floor, you keep looking in that direction until you find a L or a #. Your cut-off is also 5 now, instead of 4. How many seats end up occupied now?

Solution

Immutable Class

This solution doesn't really benefit from the class being immutable. It would probably be better if it was mutable, and just call evolve(). Where it was beneficial was that we could treat each grid as its own entity, and just compare two consecutive ones via an equals function.

The code isn't that interesting, but you can take a look at it here. What was interesting was how inheritance made part 2 a lot easier to write:

/** part 2 for day 11 */
class SeatingArea2 extends SeatingArea {
  // The keys and values are number representation of (x,y).
  // They are determined via "y*width + x"
  private readonly adjSeatCache: Map<number, number[]>;

  constructor(grid: string[], adjSeatCache?: Map<number, number[]>) {
    super(grid);
    this.adjSeatCache = adjSeatCache ?? new Map();
  }

  /** @override */
  protected maxNearbyOccupancy() {
    return 5;
  }

  /** @override */
  protected getAdjacentSeats(x: number, y: number) {
    // not relevant
  }

  /** @override */
  simulate() {
    const seatingArea = super.simulate();
    // allowed me to introduce a cache layer that I can pass around between
    simulation runs.
    return new SeatingArea2(seatingArea.seats, this.adjSeatCache);
  }
}

Running the simulations was also simple for part 2, due to this being available in part 1:

export function simulateUntilNoChange(ctor: typeof SeatingArea) {
  return ({ grid }: Simulation) => {
    let seatingArea = new ctor(grid);
    let nextSeatingArea = seatingArea;
    do {
      seatingArea = nextSeatingArea;
      nextSeatingArea = seatingArea.simulate();
    } while (!seatingArea.equals(nextSeatingArea));
    return seatingArea.occupiedSeatsCount();
  };
}

So running it in part 2 was simply:

export function run() {
  const sim = getSimulations()[1];
  timer.run(simulateUntilNoChange(SeatingArea2), `day 11b - ${sim.name}`, sim);
}

Convolution for Part 1

This gave me a reason to relearn all about convolution, and learned a lot of new applications of it. Great article on BetterExplained. Also see the ample notes I added under Mathematics -> Quick Notes -> Convolution.

The basic idea is:

1. Create a grid of numbers, where 0 means floor, 1 means vacant, and 2 means occupied.

2. Use the kernel below and convolve it with the grid from #1:

3. This will sum up all the nearby values. Since 2 means occupied (so summing these neighbors will result in double counting), we can subtract the convolution of the current grid with the original grid. The convolution of the original grid will just have a count of nearby non-floor seats.
4. At any cell grid[i][j], if the number of neighbors is 0, set this cell value to 2.
5. At any cell grid[i][j], if the number of neighbors exceeds 4 and cell is equal to 2, set this cell value to 1.
6. Keep a count of the previous and current count of occupied seats. If that has changed, stop running the simulation.

Here's a Python version of all of this that I found on Reddit with lots of comments and simplification:

import numpy as np
from scipy.ndimage import convolve

with open("11py.txt") as f:
    rows = []
    for x in f:
        # since we know that the input just has Ls and floors,
        # we don't have to worry about parsing # (occupied seats).
        # The below will create a grid of True (valid seat) or False (floor, not
        # valid). We'll convert this to 1s and 0s later.
        rows.append([c == "L" for c in x.strip()])

grid = np.array(rows).astype(np.int8)
originalGrid = grid.copy()
occ = (grid == 2).sum() # occupancy count
print("ORIGINAL GRID")
print(grid)
# kernel is equal to:
# 1 1 1
# 1 0 1
# 1 1 1
kernel = np.ones((3,3), dtype=np.int8)
kernel[1,1] = 0
# constant cval=0 means that at edges, make the weights 0. So at grid[0,0], the
# first row of the kernel and the first column of kernel are out of bounds, so
# they're weight are 0.
empty = convolve(originalGrid, kernel, mode="constant", cval=0)
print("EMPTY CONVOLUTION")
print(empty)

# Measurse how many neighbors each cell has. It does that by using the
# precomputed empty grid. This empty grid just tells us how many non-floor seats
# exist near each cell (since everything starts off as 'L', which is 1). And in grid, we'll
# have a "2" if it's occupied, meaning there's a neighbor next to us.
# In other words, if the grid returned from this (call it n) has n[x,y] = 4, it
# means it has 4 occupied seats near (x,y), because convolve(empty)[x,y] = 4, and
# convolve(grid)[x,y] = 8, and so subtracing 8-4 = 4. The reason empty returned
# 4 is because there are 4 non-floor seats next to it, and grid returned 8
# because there are 4 2s, where 2s represent occupied.
def get_neighbors(grid):
    return convolve(grid, kernel, mode="constant", cval=0) - empty

# 0 means floor
# 1 means vacant
# 2 means occupied
for idx in range(3): # Change this line to "while True:" to solve 11a.
    print("AT IDX " + str(idx))
    prev_occ = occ
    n = get_neighbors(grid)
    print("printing n")
    print(n)
    # if a cell has no neighbors (i.e., n[x,y] = 0), then set it to 1, because
    # it means it can become occupied. But if a cell has more than 4 neighbors,
    # set its value to -1 (n >= 4 will return true, and then the neg in front of
    # it turns it into -1). 1 - 1 will never happen because n can't equal 0 and
    # >=4 at the same time.
    u = (n == 0).astype(int) - (n >= 4).astype(int)
    print("printing delta (u)")
    print(u)
    # we want to keep the floor unchanged, so we set wherever
    # grid was to 0 (i.e., floor), to zero.
    u[grid == 0] = 0
    print("printing delta (u) again")
    print(u)
    # to each cell, we add either -1, 0 or 1.
    # -1 means it's no longer occupied, 0 means it's floor, and 1 means it's
    # occupied now. Remember each grid originally has values of either 0, 1 or
    # 2.
    grid = np.clip(grid + u, 0, 2)
    print("We added the delta (u) to grid")
    grid[grid == 0] = originalGrid[grid == 0]
    print("we updated everywhere grid was 0 to what originalGrid is equal to")
    print(grid)
    occ = (grid == 2).sum()
    if occ == prev_occ:
        break

print(occ)