In the spirit of the holidays (and programming), I’ll be posting my solutions to the Advent of Code 2020 puzzles here, at least one day after they’re posted (no spoilers!). I’ll be implementing the solutions in R because, well, that’s what I like! What I won’t be doing is posting any of the actual answers, just the reasoning behind them.
Also, as a general convention, whenever the puzzle has downloadable input, I’m saving it in a file named input.txt.
Day 11 - Seating System
Find the problem description HERE.
Part One - Game of “Thrones”
Having observed people sitting in the ferry waiting area, in a totally not-creepy way, we have unlocked the secrets of human behavior and developed a totally dependable way to model seating preferences. We have derived a strategy strangely similar to Conway’s Game of Life… This is actually a fairly straightforward puzzle, if it does require a fair amount of code.
test_input1 <- c(
"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"
)
real_input <- readLines('input.txt')
# Helper function, given an input in the form of a list of individual lines
# from the input file, returns a matrix where each element of the matrix
# is an individual character from the input, padded with an additional
# row/column of '.' characters surrounding the original input.
get_seat_map <- function(input) {
dot_row <- rep('.', nchar(input[[1]]))
dot_col <- rep('.', length(input)+2)
lines <- strsplit(input, '')
seats <- do.call(rbind, lines)
top_padding <- rbind(dot_row, seats, dot_row)
cbind(dot_col, top_padding, dot_col)
}
# Helper function, given a row index, column index, and a matrix as produced
# by `get_seat_map()`, returns a 3x3 matrix containing the characters
# from `seat_map` surrounding the index identified by `row`,`col`. The
# central character is replaced with '@' purely because it has no meaning
# to other functions.
get_neighbors <- function(row, col, seat_map) {
neighbors <- seat_map[(row-1):(row+1), (col-1):(col+1)]
neighbors[2, 2] <- '@'
neighbors
}
# Helper function, given a row index, column index, `seat_map` matrix, and a
# maximum number of acceptable neighbors for a `seat_map` cell to have occupied,
# returns the next state for the matrix element indicated by `row`,`col` as
# defined by the game rules
advance_seat_state <- function(row, col, seat_map, max_neighbors = 4) {
neighbors <- get_neighbors(row, col, seat_map)
is_empty <- seat_map[row, col] == 'L'
is_occupied <- seat_map[row, col] == '#'
occupied_neighbors <- sum(neighbors == '#')
if (is_empty && occupied_neighbors == 0) { return('#') }
if (is_occupied && occupied_neighbors >= max_neighbors) { return('L') }
return(seat_map[row, col])
}
# Helper function, given a `seat_map` matrix and a maximum number of acceptable
# neighbors for a `seat_map` cell to have occupied according to the game rules
# (4 for the initial case), iterates over the matrix, identifies the next state
# for each element, and returns a matrix consisting of the next state for each
# matrix element
advance_seat_map <- function(seat_map, max_neighbors = 4) {
dims <- dim(seat_map)
rows <- dims[1]
cols <- dims[2]
updated_seat_matrix <- matrix(data = '.', nrow = dims[1], ncol = dims[2])
for (row in 2:rows) {
for (col in 2:cols) {
if (seat_map[row, col] != '.') {
updated_seat_matrix[row, col] <- advance_seat_state(
row, col, seat_map, max_neighbors
)
}
}
}
updated_seat_matrix
}
# Main function, given a `seat_map` and a maximum number of acceptable
# neighbors, advances the state of the `seat_map` until it either doesn't
# change between iterations or the specified number of iterations is reached
get_final_seat_map <- function(seat_map, max_neighbors = 4) {
timeout <- seq(1000)
for (t in timeout) {
cat('\r', paste0('Simulating stage:', t))
updated_seat_map <- advance_seat_map(seat_map, max_neighbors)
if (all(seat_map == updated_seat_map)) { return(seat_map) }
seat_map <- updated_seat_map
}
}
seat_map <- get_seat_map(real_input) # Parse input
final_seat_map <- get_final_seat_map(seat_map) # Process map to completion
answer1 <- sum(final_seat_map == '#') # Get answer
It’s probably not strictly necessary to use that many functions, but I feel that it helps make the code a lot more readable. I’m particularly happy with theget_neighbors() function. To make it that simple, I ‘padded’ the input with row/column of .’s surrounding the original input, allowing me to iterate through the inner part of the matrix and pull all the characters surrounding even the ‘edges’ without needing to correct for edge and corner cases. I also added (unnecessarily, turns out) a ‘timeout’ to the get_final_seat_map()function just in case there was a danger of an infinite loop.
Part Two - Won’t You Be My Neighbor?
sigh So, that get_neighbors() function whose simplicity I was so enamored with? That’s exactly the part that needs to be modified for part two. Given a new strategy for identifying neighbors, and a slightly higher tolerance for occupied neighbors, I opted to just replace the get_neighbors() function and add that mysterious support for changing max_neighbors.
# Modified helper function, given a row index, column index, and matrix of seat
# characters, return the first non-'.' character in each direction from the
# index indicated by `seat_map[row, col]`.
get_neighbors <- function(row, col, seat_map) {
dims <- dim(seat_map)
rows <- dims[1]
cols <- dims[2]
# List of steps to take in (row, col) format required to move the cursor in
# each of eight directions
directions <- list(
left = c(0, -1), up_left = c(-1, -1),
up = c(-1, 0), up_right = c(-1, 1),
right = c(0, 1), down_right = c(1, 1),
down = c(1, 0), down_left = c(1, -1)
)
# For each of eight directions, take the value of the matrix at that direction
# repeatedly, moving one step in that same direction each iteration. Continues
# until either a non-'.' character is found or the pointer hits the edge of
# the matrix.
neighbors <- vector('character', 8)
for (direction in directions) {
curr_row <- row
curr_col <- col
neighbor <- '.'
while (
neighbor == '.' &&
curr_row > 1 && curr_row < rows &&
curr_col > 1 && curr_col < cols
) {
curr_row <- curr_row + direction[1]
curr_col <- curr_col + direction[2]
neighbor <- seat_map[curr_row, curr_col]
}
# Add to the first empty spot in the neighbors vector
neighbors[min(which(neighbors == ""))] <- neighbor
}
neighbors
}
seat_map <- get_seat_map(real_input) # Parse input
final_seat_map <- get_final_seat_map(seat_map, 5) # Process map to completion
answer2 <- sum(final_seat_map == '#') # Get answer
Now we’re using a pointer-based approach to iterate in each of the eight directions until it finds a character other than ‘.’ and returns those eight characters in as the ‘neighbors’.
Wrap-Up
My only regret is that I’m too busy this close to Christmas (and with the knowledge that there will be another puzzle tomorrow) to animate this puzzle! I’ve had a lot of fun (in a couple of languages) with Conway’s Game of Life, and this was one of my favorite days so far. If I’m lucky, I’ll get a chance to update this post with some fun ASCII art.
If you found a different solution (or spotted a mistake in one of mine), please drop me a line!
Top comments (0)