# Advent of Code 2020 - Day 16

By Eric Burden | December 17, 2020

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 16 - Ticket Translation

Find the problem description HERE.

## Part One - No Money? No Ticket!

This puzzle got me right in my comfort zone: manipulating tabular data! Granted, that’s probably not the only (or even necessarily best) way to solve this puzzle, but at this point I’m frankly incapable of not wanting to use dplyr for one of these. Now’s my chance!

Also a first for me in these puzzles (I think): a closure! If you’re not familiar with closures in R, it’s what you get when you have a function that returns a function. The returned function takes the environment of the function that produced it along for the ride. In this case, each function produced by field_test_function() carries the vectors for range_one and range_two with it in its enclosing environment, which is mighty convenient.

library(stringr)
library(tidyr)
library(dplyr)
library(dequer)

test_input <- c(
"class: 1-3 or 5-7",
"row: 6-11 or 33-44",
"seat: 13-40 or 45-50",
"",
"7,1,14",
"",
"nearby tickets:",
"7,3,47",
"40,4,50",
"55,2,20",
"38,6,12"
)

# Given a line from the input for a field test (i.e., in the format of
# "class: 1-3 or 5-7"), returns a closure that accepts a number and
# returns TRUE if the number matches one of the defined ranges from the
# input and FALSE if it does not.
field_test_function <- function(line) {
nums <- as.numeric(str_extract_all(line, '\\d+', simplify = TRUE))
range_one <- nums[1]:nums[2]
range_two <- nums[3]:nums[4]

function(n) {
(n %in% range_one) | (n %in% range_two)
}
}

# Given a list of input lines input, returns an environment containing
# a list of functions for testing fields field_tests, a numeric vector
# containing the values from your ticket my_ticket, and a list containing
# the values from all the other tickets nearby_tickets
parse_input <- function(input) {
env <- new.env()             # Container environment
env$field_tests <- list() # List of functions for testing fields env$my_ticket <- numeric(0)  # Vector for 'my ticket' numbers
nearby_tickets <- stack()    # Stack to hold other ticket numbers
mode <- 'tests'              # Indicates what the for loop does with current line

# For each line in the input lines...
for (line in input) {
if (line == "") { next }  # Skip blank lines

# Set mode to parse my ticket data
if (line == 'your ticket:') { mode <- 'my ticket'; next }

# Set mode to parse numbers from other tickets
if (line == 'nearby tickets:') { mode <- 'other tickets'; next }

# The default, for the first set of input lines create a function for
# each that will test a number to see if it falls within the given ranges
if (mode == 'tests') {
name <- str_extract(line, '^[\\w\\s]+(?=:)')
env$field_tests[[name]] <- field_test_function(line) } # For 'my ticket', just get the numbers if (mode == 'my ticket') { env$my_ticket <- as.numeric(unlist(strsplit(line, ',')))
}

# For 'other tickets', get the numbers and push them onto the
# nearby_tickets stack
if (mode == 'other tickets') {
ticket_nums <- as.numeric(unlist(strsplit(line, ',')))
push(nearby_tickets, ticket_nums)
}
}

env$nearby_tickets <- as.list(nearby_tickets) # Stack to list env # Return the environment } # Given a list of vectors containing the field data from nearby tickets # nearby_tickets and a list of tests to determine whether a number satisfies # the ranges for a given field field_tests, builds and returns a data frame # where each row represents the results of testing single field in a single # ticket for a match against the rules for a named field. So, one row per test, # per field, per ticket. Includes columns that represent a unique identifier for # the ticket ticket_no, the order in which that field appears on the ticket # field_no, the name of the field being tested for field, whether the # value of that field matched the test for the named field match, and the # value of the field being examined field_val get_field_matches <- function(nearby_tickets, field_tests) { # Structure for the resulting data frame all_results <- data.frame( ticket_no = numeric(0) , field_no = numeric(0), field = character(0), match = logical(0), field_val = numeric(0) ) # For each vector in nearby_tickets... for (ticket_no in 1:length(nearby_tickets)) { # Shorthand reference to ticked field values field_vals <- nearby_tickets[[ticket_no]] # Check each field value against each field test function, convert the # results into a data frame matches <- sapply(field_tests, function(f) { f(field_vals) }) %>% as.data.frame() %>% mutate( ticket_no = ticket_no, field_no = row_number(), field_val = field_vals ) %>% pivot_longer( -c('ticket_no', 'field_no', 'field_val'), names_to = 'field', values_to = 'match' ) all_results <- bind_rows(all_results, matches) # Append to our data frame } all_results # Return the data frame } input_environment <- parse_input(real_input) # Unpack the input # Parse the input data into a data frame indicating matches against the field # test functions field_matches <- get_field_matches( input_environment$nearby_tickets,
input_environment$field_tests ) # Determine the answer: # - Group the data frame by ticket_no, field_no, and field_val # - For each group, sum the number of fields where match == TRUE # - Keep only records where no matches were found # - Extract the field_val column as a vector # - Sum the contents of the field_val column answer1 <- field_matches %>% group_by(ticket_no, field_no, field_val) %>% summarise_at('match', sum) %>% filter(match == 0) %>% pull(field_val) %>% sum()  Ah… Just look at those magrittr pipes… Lovely. Just in case you haven’t seen them before (unlikely if you’ve used R for very long), the %>%s are ‘pipe’ operators. They pass the result from their left-hand side as the first argument to the function (or expression) on their right-hand side. ## Part Two - There Can Be Only One This one took me a bit to realize that it wasn’t because I’d done something wrong that many of the fields appeared to satisfy more than one validation rule. Once I realized that was on purpose (and that initially one of the fields satisfied only a single validation rule), I was off to the races! So, identify the field(s) that satisfy only a single rule, assign that field the name of the field represented by that validation rule, remove that field name from the options, then do it again. source('exercise_1b.R') test_input <- c( "class: 0-1 or 4-19", "row: 0-5 or 8-19", "seat: 0-13 or 16-19", "", "your ticket:", "11,12,13", "", "nearby tickets:", "3,9,18", "15,1,5", "5,14,9" ) input_environment <- parse_input(real_input) # Unpack the input # Parse the input data into a data frame indicating matches against the field # test functions field_matches <- get_field_matches( input_environment$nearby_tickets,
input_environment$field_tests ) # Get a data frame containing only valid tickets: # - Group by ticket_no, field_no, and field_val # - Mark any fields containing invalid data with invalid_field = TRUE # - Group by ticket_no # - Mark any tickets containing invalid fields with exclude = TRUE # - Ungroup and remove any tickets containing invalid fields valid_ticket_data <- field_matches %>% group_by(ticket_no, field_no, field_val) %>% mutate(invalid_field = !any(match)) %>% group_by(ticket_no) %>% mutate(exclude = any(invalid_field)) %>% ungroup() %>% filter(!exclude) # Get a data frame consisting of one row per field_no, per field name where # all fields in that number matched a particular field test (for example, all # values in field_no 1 matched the 'arrival_platform' field): # - Group by field_no and field # - Identify groups where the field_no matched a particular field test every time # - Filter, keeping only those groups identify_fields <- valid_ticket_data %>% group_by(field_no, field) %>% summarise(all_matched = all(match)) %>% filter(all_matched) # Create an empty data frame with columns for field_no and field confirmed_fields <- data.frame(field_no = numeric(0), field = character(0)) # Until all records in identify_fields have been transferred to # confirmed_fields while (nrow(confirmed_fields) < length(unique(identify_fields$field))) {

# Identify fields that only match one set of field rules, sequentially. On the
# first pass, many of the field_nos will satisfy more than one field test,
# so we start by transferring the field_nos that only match one test to
# confirmed_fields:
# - Starting with identify_fields
# - Remove any records containing a field_no that has already been confirmed
# - Group by field
# - Calculate the number of records in the group as group_size
# - Filter, keeping only fields where the group_size is 1, indicating that
#   that field_no only matches that field's requirements
# - Select the field_no and field columns
newly_confirmed <- identify_fields %>%
filter(!(field_no %in% confirmed_fields$field_no)) %>% group_by(field) %>% mutate(group_size = n()) %>% filter(group_size == 1) %>% select(field_no, field) # Add newly_confirmed rows to confirmed_fields confirmed_fields <- bind_rows(confirmed_fields, newly_confirmed) } # Starting with the data frame of confirmed field names/numbers, filter the # data frame to only 'departure' fields and pull out the field_no column # as a vector departure_field_nos <- confirmed_fields %>% filter(str_detect(field, 'departure')) %>% pull(field_no) # Now that we know which field_nos (i.e., ticket vector indices) belong to # the 'departure' fields, just select those values from my_ticket and # multiply together answer2 <- prod(input_environment$my_ticket[departure_field_nos])


## Wrap-Up

This one was fun! It was a bit more code than some of the others, but it was so worth it. Plus, I got to use a bit of ‘functional programming’ with my closure (that’s my story and I’m sticking to it). I normally try not to lean too heavily on external packages for these, but I happily relied on dplyr and magrittr.

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!