day_16.Rmd

# Ticket Translation

```{r setup, include=FALSE}
knitr::opts_chunk$set(echo = TRUE)
options(crayon.enabled = NULL, # for when rendering on github actions
        scipen = 999)          # make sure we never print in scientific notation
library(tidyverse)
library(unglue)

START_TIME <- Sys.time()
```

This is my attempt to solve [Day 16](https://adventofcode.com/2020/day/16).

```{r load data}
# process the files
process_file <- function(file) {
  file %>%
    # strip windows new line carriage return charaters
    str_replace_all("\r", "") %>%
    # remove trailing whitespace
    str_trim() %>%
    # split on double new lines
    str_split("\n\n") %>%
    # get the first result (input was a single vector)
    pluck(1) %>%
    # iterate over these results, split on newlines
    map(str_split, "\n") %>%
    # iterate over the results, select just the first item from each
    # (each result from str_split will be a list of character vectors)
    map(1)
}
sample <- read_file("samples/day_16_sample.txt") %>% process_file()
actual <- read_file("inputs/day_16_input.txt") %>% process_file()
```

## Part 1

First let's build a function to process our "notes". We can return a list containing the fields we are expecting (as a
dataframe with columns for the ranges), our ticket, and the nearby tickets.

```{r part 1 process notes}
process_notes <- function(input) {
  fields <- input[[1]] %>%
    unglue_data("{field}: {a}-{b} or {c}-{d}", convert = TRUE)
  
  my_ticket <- as.numeric(str_split(input[[2]][[2]], ",")[[1]])
  nearby_tickets <- map(str_split(input[[3]][-1], ","), as.numeric)
  
  list(fields = fields,
       my_ticket = my_ticket,
       nearby_tickets = nearby_tickets)
}
```

We can now process our `sample` and `actual` data.

```{r process data}
psample <- process_notes(sample)
pactual <- process_notes(actual)

psample
```

Now, we need to check if a value is valid. We can build a simple function to do this that will take a value and the
fields dataset. It will return `TRUE` if the value is valid for one of the fields and `FALSE` otherwise.

```{r part 1 value_is_valid}
value_is_valid <- function(value, fields) {
  any(
    fields$a <= value & value <= fields$b,
    fields$c <= value & value <= fields$d
  )
}
```

We now can take the `nearby_tickets`, flatten the nested list to a single numeric vector and discard any value that is
not valid.

```{r part 1 function}
part_1 <- function(input) {
  input$nearby_tickets %>%
    flatten_dbl() %>%
    discard(value_is_valid, fields = input$fields) %>%
    sum()
}
```

We can test with our sample data:

```{r part 1 sample test}
part_1(psample) == 71
```

And we can run with our actual data:

```{r part 1 actual}
part_1(pactual)
```

## Part 2

We have a different sample for part 2:

```{r part 2 new sample}
psample_2 <- str_trim("
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
") %>%
  process_file() %>%
  process_notes()
```

For part 2 we can use `{dplyr}` to find the possible fields that a value could take at a position, then we can loop
over the possible fields reducing the rows in the table by finding a field that is the only candidate for a position,
then removing that field from other positions.

This assumes that there will always be just 1 possible candidate at each point.

```{r part 2 function}
part_2 <- function(input) {
  valid_tickets <- input$nearby_tickets %>%
    keep(~all(map_lgl(.x, value_is_valid, fields = input$fields)))
  
  possible_fields <- data.frame(value = flatten_dbl(valid_tickets),
                                pos = 1:nrow(input$fields)) %>%
    mutate(fields = map(value, function(.x) {
      input$fields %>%
        filter((a <= .x & .x <=b) | (c <= .x & .x <= d)) %>%
        pull(field)
    })) %>%
    unnest_longer(col = fields) %>%
    group_by(pos) %>%
    count(fields) %>%
    filter(n == max(n))
  
  input$fields$pos <- 0
  
  while (nrow(possible_fields) > 0) {
    f <- filter(possible_fields, n() == 1)
    possible_fields <- filter(possible_fields, fields != f$fields)
    
    input$fields[input$fields$field == f$fields, "pos"] <- f$pos
  }

  input$fields %>%
    select(field, pos)
}
```

We can test our function matches the provided sample:

```{r part 2 sample}
part_2(psample_2)
```

And now we can solve the actual problem. Find the fields and their positions, the apply those positions to `my_ticket`:

```{r part 2 actual}
ps <- pactual %>%
  part_2() %>%
  filter(str_detect(field, "^departure")) %>%
  pull(pos)

prod(pactual$my_ticket[ps])
```

---

*Elapsed Time: `r round(Sys.time() - START_TIME, 3)`s*