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 5 - Binary Boarding

Find the problem description HERE.

Part One - A Case for Scanning Things

To be clear, the premise of part one is that we are capable of (1) writing software to interface with our phone’s hardware that can capture the information on every other passenger’s boarding pass and (2) parse it with optical character recognition (I’m assuming with some nice ML models supporting that process), but we cannot keep up with a slip of paper. Nor did we have the forethought to scan our own boarding pass ahead of time. Sure, that tracks. Well, now that we’ve sideloaded our software, the only thing left is to perform the binary search that’s hinted at in Day 5’s title.

library(stringr)

# Helper function, given a vector of characters ("F" or "B"), returns the
# row number
parse_row <- function(row_vec) {
  rows <- c(0:127)
  for (v in row_vec) {
    if (v == "F") { rows <- head(rows, length(rows)/2) }  # First half
    if (v == "B") { rows <- tail(rows, length(rows)/2) }  # Second half
  }
  rows
}

# Helper function, given a vector of characters ("L" or "R"), returns the
# seat (column) number
parse_col <- function(col_vec) {
  cols <- c(0:7)
  for (v in col_vec) {
    if (v == "L") { cols <- head(cols, length(cols)/2) }  # First half
    if (v == "R") { cols <- tail(cols, length(cols)/2) }  # Second half
  }
  cols
}

# Calculates seat id # from row and seat (column)
seat_id <- function(row, col) {
  (row * 8) + col
}

# Helper function, parse a full boarding pass string into a named vector
# containing the row number, seat number (column), and seat id #
parse_pass <- function(pass_str) {
  row_vec <- str_split(substr(pass_str, 1, 7), '', simplify = T)
  col_vec <- str_split(substr(pass_str, 8, 10), '', simplify = T)
  
  row <- parse_row(row_vec)
  col <- parse_col(col_vec)
  
  c(row = row, col = col, seat_id = seat_id(row, col))
}

# Create a matrix of results with a row, col, and seat_id columns
parsed_passes <- do.call(rbind, lapply(input, parse_pass))
answer <- max(parsed_passes[,'seat_id'])  # Pick out the biggest seat_id #

That feels like a lot of helper functions, but it’s often useful to break out functionality this way, especially as you work your way through a problem like this. Having every operation split out this way definitely makes for more readable code in the end. The seat_id() function may have been a bit of overkill in this case, but in a larger program it would have given us a single place to change the formula for determining seat number if we needed to.

Part Two - One of These Things is not Like the Others

Great! We’ve violated the privacy of all our fellow passengers, now we just need to find our own seat. The “fasten seat belts” sign is on, and we’re so good at coding (one a cell phone, obviously) that it’s easier to check our array of seat ID #’s than it is to look around and find the one empty seat. Here we go!

seats_present <- sort(parsed_passes[,'seat_id'])            # All the seat_id's filled  
seats_possible <- c(min(seats_present):max(seats_present))  # All the seat_id's on the plane
answer <- setdiff(seats_possible, seats_present)  # The missing one!

It’s just that easy. Since we are clearly not in the first or last seat (by ID) according to the instructions, and since the seat ID’s are calculated in such a a way that they are sequential, we can determine the full range of possible seat ID’s by taking the integers from the smallest to the largest seat ID’s we found. Now it’s just a matter of comparing the found seat ID’s to the possible seat ID’s. Surprise! There’s one number in the list of all seat ID’s that’s not in the list of seat ID’s we scanned. Bingo!

Wrap-Up

Too many helper functions, you say? Well, Santa has his little helpers, no reason we can’t as well. Creating the row/seat/seat ID matrix was probably unnecessary, but I’ve found that being thorough on Part One typically sets you up for success on Part Two. Plus, I got to slip a do.call() in there, R’s alternative to the supremely useful argument unpacking syntax in Python. If you found a different solution (or spotted a mistake in one of mine), please drop me a line!