Day 11

Advent of Code: Worked Solutions

Setup

Import libraries:

library(tidyverse)

Read text input from file into a 1/0 matrix. “.” values are read in as NA.

input <- read_lines("../input/day11.txt") |> 
  str_split("") |> 
  map(\(x) case_match(x, "L" ~ 0, "#" ~ 1)) |> 
  reduce(rbind) |> 
  unname()

Part 1

The base R functions ‘row’ and ‘col’ generate a row/column index for every element of the supplied matrix. Create a helper function that generates an equivalent mapping for the diagonals of a matrix:

diag <- function(mtx, direction = c("up", "down")) {
  map2_int(
    rep(1:nrow(mtx), times = ncol(mtx)), 
    rep(1:ncol(mtx), each  = nrow(mtx)), 
    \(i, j) {
      if (direction == "up")
        i + j - 1
      else if (direction == "down")
        i - j + ncol(mtx)
    }
  ) |> 
    matrix(nrow(mtx), ncol(mtx))
}

Define a helper function which, for each element of our supplied matrix, counts how many adjacent seats are occupied in each direction:

counts <- function(mtx) {
  lst(
    input_rows  = row(mtx), 
    input_cols  = col(mtx), 
    input_diag1 = diag(mtx, "up"), 
    input_diag2 = diag(mtx, "down")
  ) |> 
    map(\(mapping) {
      mtx |> 
        split(mapping) |> 
        map(\(x) coalesce(x, 0)) |>
        map(\(x) lead(x, default = 0) + lag(x, default = 0)) |> 
        unsplit(mapping) |> 
        matrix(nrow(mtx), ncol(mtx))
    }) |> 
    reduce(`+`)
}

Define a helper function to iteratively adjust the seating until now changes are found, then return the number of occupied seats:

shift_seating <- function(init, limit) {
  neighbors <- counts(init)
  init |> 
    replace(init == 0 & neighbors == 0, 1) |> 
    replace(init == 1 & neighbors >= limit, 0) 
}

Loop until equilibrium & count output:

cur <- input 
nxt <- input

repeat {
  nxt <- shift_seating(cur, limit = 4)
  if (all(nxt == cur | (is.na(cur) & is.na(nxt))))
    break
  cur <- nxt
}

sum(cur, na.rm = TRUE)

Part 2

Adjust the neighbor counting functions such that rather than just looking at the adjacent seats, it look at all seats in the line of sight:

counts <- function(mtx) {
  lst(
    input_rows  = row(mtx), 
    input_cols  = col(mtx), 
    input_diag1 = diag(mtx, "up"), 
    input_diag2 = diag(mtx, "down")
  ) |> 
    map(\(mapping) {
      mtx |> 
        split(mapping) |> 
        map(\(x) {
          fwd <- x |>
            accumulate(\(x, y) coalesce(y, x), .dir = "forward") |>
            lag(default = 0) |> 
            coalesce(0)
          bwd <- x |>
            accumulate(\(x, y) coalesce(x, y), .dir = "backward") |>
            lead(default = 0) |> 
            coalesce(0)
          fwd + bwd
        }) |> 
        unsplit(mapping) |> 
        matrix(nrow(mtx), ncol(mtx))
    }) |> 
    reduce(`+`)
}

Loop until equilibrium & count output:

cur <- input 
nxt <- input

repeat {
  nxt <- shift_seating(cur, limit = 5)
  if (all(nxt == cur | (is.na(cur) & is.na(nxt))))
    break
  cur <- nxt
}

sum(cur, na.rm = TRUE)