The obsession with Advent of Code is real - I’ve been looking forward to the midnight unlock for a few straight nights now, and my sleep schedule seems to be moving to accommodate.

A few problems in this set really frustrated me - as you can see from the time differences.

Statistics

## # A tibble: 5 x 6
##     day time_1   rank_1 time_2   rank_2 timediff  
##   <dbl> <chr>     <dbl> <chr>     <dbl> <drtn>    
## 1     6 00:10:04   3730 00:15:20   2587   5.3 mins
## 2     7 00:23:12   1546 01:50:18   6048  87.1 mins
## 3     8 00:34:58   7532 01:00:37   6417  25.6 mins
## 4     9 00:15:31   3951 00:34:03   4722  18.5 mins
## 5    10 00:08:09   1437 02:33:45   7065 145.6 mins

Packages used

For the most part, I’ve used tidyverse pretty darn consistently thus far.

suppressPackageStartupMessages({
  library(tidyverse)
  library(here)
  library(lubridate)
  library(slider)
})

Day Six

I was elated to crack day six in a personal best time so far: 15:20. I’ve settled into a “clean the data into a tibble” pattern before solving, and it seems to help!

The form asks a series of 26 yes-or-no questions marked a through z. All you need to do is identify the questions for which anyone in your group answers “yes”. Since your group is just you, this doesn’t take very long.

However, the person sitting next to you seems to be experiencing a language barrier and asks if you can help. For each of the people in their group, you write down the questions for which they answer “yes”, one per line. For example:

  • abcx
  • abcy
  • abcz

In this group, there are 6 questions to which anyone answered “yes”: a, b, c, x, y, and z. (Duplicate answers to the same question don’t count extra; each question counts at most once.)

— Data —

input_06 <- read_lines("https://github.com/tanho63/advent_of_code/raw/master/2020/day-06.txt")

— Cleaning —

df_surveys <- tibble(data = input_06) %>% 
  mutate(group_id = ifelse(data == "",1,0),
         group_id = cumsum(group_id) + 1) %>% 
  filter(data!="") %>% 
  mutate(passenger_id = row_number(),
         data = str_split(data,"")) %>% 
  unnest_longer(data)
head(df_surveys)
## # A tibble: 6 x 3
##   data  group_id passenger_id
##   <chr>    <dbl>        <int>
## 1 t            1            1
## 2 r            1            1
## 3 r            1            2
## 4 t            1            2
## 5 t            1            3
## 6 r            1            3

— Problem 1 — For each group, count the number of questions to which anyone answered “yes”. What is the sum of those counts?

p1 <- df_surveys %>% 
  group_by(group_id) %>% 
  summarise(count = length(unique(data))) %>% 
  summarise(sum(count))
p1
## # A tibble: 1 x 1
##   `sum(count)`
##          <int>
## 1         6310

— Problem 2 —

Now count only where everyone in the group answered ALL the same questions.

p2 <- df_surveys %>% 
  group_by(group_id) %>%
  add_count(data,name = "answer_count") %>% 
  mutate(group_count = length(unique(passenger_id))) %>% 
  ungroup() %>% 
  filter(answer_count == group_count) %>% 
  group_by(group_id) %>% 
  summarise(count = length(unique(data))) %>% 
  summarise(sum(count))
p2
## [1] 3193

New time PB of fifteen minutes is pretty satisfying!

Day Seven

The first puzzle that really had me at an absolute loss and dire frustration. Pulled out parallel processing on it in the end and that saved the day, even after a few minutes of crunching. Foreshadowing future difficulties, obviously…

— Data —

input_07 <- read_lines("https://github.com/tanho63/advent_of_code/raw/master/2020/day-07.txt")

— Cleaning —

df_rules <- tibble(input = input_07) %>% 
  separate(input,into = c("name","rule"),sep = " bags contain ") %>% 
  mutate(rule = str_split(rule,"bags|bag")) %>% 
  unnest_longer(rule)  %>% 
  mutate(rule = str_remove(rule,","),
         rule = str_remove(rule,"\\."),
         rule = str_squish(rule)) %>% 
  filter(rule != "") %>% 
  mutate(rule_qty = parse_number(rule,na = "no other"),
         rule_colour = if_else(is.na(rule_qty), 
                               NA_character_,
                               str_remove(rule,as.character(rule_qty))),
         rule_colour = str_squish(rule_colour))
head(df_rules)
## # A tibble: 6 x 4
##   name           rule               rule_qty rule_colour     
##   <chr>          <chr>                 <dbl> <chr>           
## 1 vibrant purple 3 shiny lavender          3 shiny lavender  
## 2 vibrant purple 1 mirrored gray           1 mirrored gray   
## 3 vibrant purple 4 muted bronze            4 muted bronze    
## 4 posh crimson   4 drab plum               4 drab plum       
## 5 posh crimson   5 dotted purple           5 dotted purple   
## 6 posh crimson   3 vibrant lavender        3 vibrant lavender

— Problem 1 —

How many bag colours eventually contain one shiny gold bag?

find_parents <- function(colour,df_rules){
  x <- df_rules %>% 
    filter(rule_colour == colour, rule_qty >= 1)
  
  map_dfr(x$name,find_parents,df_rules) %>% 
    bind_rows(x,.)
}

parents <- find_parents("shiny gold",df_rules)

unique(parents$name) %>% length()
## [1] 119

— Problem 2 —

How many bags are inside your shiny gold bag?

The ultimate “I’m too tired for this shit” move is to pull out parallel processing on it. Cause ugh. This ended up taking a few minutes on my machine.

library(furrr) 

plan(multiprocess)

find_children <- function(colour,df_rules){
  
  x <- df_rules %>% 
    filter(name == colour,!is.na(rule_qty))
  
  if(nrow(x)==0) return(tibble())
  
  x <- x %>% 
    mutate(rule_colour = map2(rule_colour,rule_qty,rep_len)) %>% 
    unnest_longer(rule_colour)
  
  y <- future_map_dfr(x$rule_colour,find_children,df_rules)
  
  bind_rows(x,y)
}

children <- find_children("shiny gold",df_rules)
nrow(children)
## [1] 155802

Day Eight

I thought this problem was more manageable after (because of?) day seven’s difficulties. Good practice with looping and functions, I think.

The boot code is represented as a text file with one instruction per line of text. Each instruction consists of an operation (acc, jmp, or nop) and an argument (a signed number like +4 or -20).

  • acc increases or decreases a single global value called the accumulator by the value given in the argument. For example, acc +7 would increase the accumulator by 7. The accumulator starts at 0. After an acc instruction, the instruction immediately below it is executed next.
  • jmp jumps to a new instruction relative to itself. The next instruction to execute is found using the argument as an offset from the jmp instruction; for example, jmp +2 would skip the next instruction, jmp +1 would continue to the instruction immediately below it, and jmp -20 would cause the instruction 20 lines above to be executed next.
  • nop stands for No OPeration - it does nothing. The instruction immediately below it is executed next.

This is an infinite loop: with this sequence of jumps, the program will run forever. The moment the program tries to run any instruction a second time, you know it will never terminate.

Immediately before the program would run an instruction a second time, the value in the accumulator is 5.

Run your copy of the boot code. Immediately before any instruction is executed a second time, what value is in the accumulator?

— Data —

input_08 <- read_lines("https://github.com/tanho63/advent_of_code/raw/master/2020/day-08.txt")

— Cleaning —

df_codes <- tibble(x = input_08) %>% 
  separate(x,c("instruction","qty"),sep = " ", convert = TRUE) %>% 
  mutate(instruction_id = row_number(),
         next_instruction_id = case_when(instruction == "jmp" ~ instruction_id + qty,
                                         TRUE ~ instruction_id + 1L)) %>% 
  select(instruction_id,instruction,qty,next_instruction_id)
head(df_codes)
## # A tibble: 6 x 4
##   instruction_id instruction   qty next_instruction_id
##            <int> <chr>       <int>               <int>
## 1              1 acc            17                   2
## 2              2 acc            37                   3
## 3              3 acc           -13                   4
## 4              4 jmp           173                 177
## 5              5 nop           100                   6
## 6              6 acc            -7                   7

— Problem 1: —

Immediately before any instruction is executed a second time, what value is in the accumulator?

current_id <- 1
accumulator <- 0
error_switch <- FALSE
visited_codes <- tibble()

while(!error_switch){
  
  current_instruction <- df_codes %>% 
    filter(instruction_id == current_id)
  
  visited_codes <- bind_rows(visited_codes,current_instruction)
  
  if(current_instruction$instruction == "acc") accumulator <- accumulator + current_instruction$qty
  
  current_id <- current_instruction$next_instruction_id
  
  if(current_id %in% visited_codes$instruction_id) error_switch <- TRUE

}
accumulator
## [1] 1797

— Problem 2: Fix the program —

The program has a bug where one of jmp or nop are wrong and should be the other way around, which will let the program run all of the rows. If the program exits correctly, what is the accumulator total?

First, create function for the previous problem’s accumulator.

run_accumulator <- function(df_codes){
  
  current_id <- 1
  accumulator <- 0
  error_switch <- FALSE
  visited_codes <- tibble()
  
  while(!error_switch){
    
    current_instruction <- df_codes %>% 
      filter(instruction_id == current_id)
    
    visited_codes <- bind_rows(visited_codes,current_instruction)
    
    if(current_instruction$instruction == "acc") accumulator <- accumulator + current_instruction$qty
    
    current_id <- current_instruction$next_instruction_id
    
    if(current_id == 626) error_switch <- TRUE
    if(current_id %in% visited_codes$instruction_id) error_switch <- TRUE
  }

  status <- "FAIL"
  
  if(current_id == 626) status <- "SUCCESS"
  
  return( 
    list(
      status = status, 
      accumulator = accumulator, 
      next_id = current_id)
  )
}

test_accumulator <- run_accumulator(df_codes)
test_accumulator
## # A tibble: 6 x 3
##   status  accumulator next_id
##   <chr>         <dbl>   <int>
## 1 SUCCESS        1036     626
## 2 FAIL           1818     448
## 3 FAIL           1797     606
## 4 FAIL           1797     606
## 5 FAIL           1797     606
## 6 FAIL           1797     606

Next, build function to switch jmp and nop, build list of dfs, run the accumulator on it and find the row with success.

library(furrr)

plan(multisession)

jmpnop_switcher <- function(id,df_codes){
  
  df_codes$instruction[id] <- switch(df_codes$instruction[id],
                                     "jmp" = "nop",
                                     "nop" = "jmp")
  
  df_codes <- df_codes %>% 
    mutate(next_instruction_id = case_when(instruction == "jmp" ~ instruction_id + qty,
                                           TRUE ~ instruction_id + 1L))
  
  df_codes
}

jmpnop_list <- df_codes$instruction_id[df_codes$instruction %in% c("jmp","nop")]

df_codelist <- map(jmpnop_list,jmpnop_switcher,df_codes)

x <- future_map_dfr(df_codelist,run_accumulator)
x %>% filter(status == "SUCCESS")
## # A tibble: 1 x 3
##   status  accumulator next_id
##   <chr>         <dbl>   <int>
## 1 SUCCESS        1036     626

Day Nine

This one mentioned rolling windows, which led me to think of Davis Vaughan’s slider package. That helped my process a lot!

— Description —

XMAS starts by transmitting a preamble of 25 numbers. After that, each number you receive should be the sum of any two of the 25 immediately previous numbers. The two numbers will have different values, and there might be more than one such pair.

For example, suppose your preamble consists of the numbers 1 through 25 in a random order. To be valid, the next number must be the sum of two of those numbers.

The first step of attacking the weakness in the XMAS data is to find the first number in the list (after the preamble) which is not the sum of two of the 25 numbers before it. What is the first number that does not have this property?

— Data —

input_09 <- read_lines("https://github.com/tanho63/advent_of_code/raw/master/2020/day-09.txt")

— Cleaning —

Offhand, I’m going to use Davis Vaughan’s “slider” package to create the rolling windows for each row, and hopefully that helps tackle each problem.

library(slider)

df_cipher <- tibble(num = input_09) %>% 
  mutate_all(as.numeric) %>% 
  mutate(rolling = slide(num,~.x,.before = 24, .complete = TRUE) %>% lag()) %>% 
  slice(-(1:25))
head(df_cipher)
## # A tibble: 6 x 2
##     num rolling   
##   <dbl> <list>    
## 1    30 <dbl [25]>
## 2    11 <dbl [25]>
## 3     3 <dbl [25]>
## 4    33 <dbl [25]>
## 5    78 <dbl [25]>
## 6     4 <dbl [25]>

— Problem 1 —

Find the first number which is not the sum of the two numbers before it.

problem_1 <- df_cipher %>% 
  mutate(rolling_sum = map2_lgl(rolling,num, 
                       ~ crossing(x = .x, y = .x) %>% 
                          mutate(sum = x + y,
                                 flag = sum == .y) %>% 
                         summarise(flag = any(flag)) %>% 
                         pull(flag)))
problem_1 %>% 
  filter(!rolling_sum)
## # A tibble: 1 x 3
##        num rolling    rolling_sum
##      <dbl> <list>     <lgl>      
## 1 10884537 <dbl [25]> FALSE
solution_1 <- problem_1 %>% 
  filter(!rolling_sum) %>% 
  pull(num)

— Problem 2 —

The final step in breaking the XMAS encryption relies on the invalid number you just found: you must find a contiguous set of at least two numbers in your list which sum to the invalid number from step 1.

Back to slider again, this time using a loop to iterate the size of the rolling window upward until the solution is found.

problem_2 <- df_cipher %>% 
  filter(num < solution_1) %>%
  select(num)

success <- FALSE
size <- 1

while(!success){
  size <- size + 1
  
  test_solve <- problem_2 %>% 
    mutate(rolling_sum = slide_dbl(num,sum,.complete = TRUE,.before = size - 1),
           success = rolling_sum == solution_1)
  
  success <- any(test_solve$success,na.rm = TRUE)
}

cleanup_solution <- test_solve %>% 
  slice((which(test_solve$success)-size+1):which(test_solve$success))
cleanup_solution
## # A tibble: 17 x 3
##       num rolling_sum success
##     <dbl>       <dbl> <lgl>  
##  1 408514     6419520 FALSE  
##  2 507208     6675531 FALSE  
##  3 753282     7148649 FALSE  
##  4 695857     7429404 FALSE  
##  5 570543     7628429 FALSE  
##  6 444281     7753756 FALSE  
##  7 626571     7967090 FALSE  
##  8 592643     8216758 FALSE  
##  9 500865     8374124 FALSE  
## 10 693401     8676795 FALSE  
## 11 599118     8899534 FALSE  
## 12 661929     9061257 FALSE  
## 13 814643     9507096 FALSE  
## 14 662453     9792646 FALSE  
## 15 712303    10107548 FALSE  
## 16 852795    10517218 FALSE  
## 17 788131    10884537 TRUE
min(cleanup_solution$num) + max(cleanup_solution$num)
## [1] 1261309

Day Ten

Another one for immense frustration. First problem was cracked in under eight minutes after some silly stumbling…and then the second half took me over two hours.

— Data —

input_10 <- read_lines("https://github.com/tanho63/advent_of_code/raw/master/2020/day-10.txt")

— Cleaning —

df_adapters <- tibble(adapter = input_10) %>% 
  mutate(adapter = as.numeric(adapter)) %>% 
  add_row(adapter = max(.$adapter)+3) %>% 
  arrange(adapter) %>% 
  mutate(diff = adapter - lag(adapter,default = 0))
head(df_adapters)

— Problem 1 —

Find a chain that uses all of your adapters to connect the charging outlet to your device’s built-in adapter and count the joltage differences between the charging outlet, the adapters, and your device. What is the number of 1-jolt differences multiplied by the number of 3-jolt differences?

p1 <- df_adapters %>% 
  count(diff)
p1
## # A tibble: 2 x 2
##    diff     n
##   <dbl> <int>
## 1     1    73
## 2     3    31
prod(p1$n)
## [1] 2263

— Problem 2 —

What is the total number of distinct ways you can arrange the adapters to connect the charging outlet to your device?

Back to the slider package here, I think.

library(slider)
options(scipen = 999)

Creating a table of adapters with the end at the top, and then a list of ways you could use that plug (i.e. which plugs the current plug can fit into).

p2 <- df_adapters %>%
  select(adapter) %>%
  add_row(adapter = 0) %>% 
  arrange(desc(adapter)) %>% 
  mutate(
    ways = slide(adapter,~.x,.before = 3,.after = -1),
    ways = map2(ways,adapter,~.x[.x-.y<=3]))
head(p2)
## # A tibble: 6 x 2
##   adapter ways           
##     <dbl> <chr>          
## 1     166 ""             
## 2     163 "166"          
## 3     162 "163"          
## 4     161 "163, 162"     
## 5     160 "163, 162, 161"
## 6     159 "162, 161, 160"

Beginning with the end in mind:

  • adapter 163 can plug into adapter 166 and that’s it.
  • adapter 162 can plug into 163, and so inherits the number of ways that adapter 163 can plug into 166.
  • adapter 161 can plug into either 163 or 162, and so inherits the sum of (ways adapter 163 can plug in + ways adapter 162 can plug in).
  • adapter 160 can plug into any of 163,162,161, so inherits the sum of (ways adapter 163 + ways adapter 162 + ways adapter 161) etc

Tried cumulative sums and actual recursion for a while before deciding on an external lookup table that was superassigned into.

lookup_table <- numeric()
lookup_table[[max(df_adapters$adapter)]] <- 1 # seed lookup_table for 166 as 1 path

p2 <- p2 %>% slice(-1) # remove 166, ways you can plug 166 in is blank

sum_ways <- function(ways,adapter){
  
  ways <- unlist(ways)
  
  total_ways <- sum(lookup_table[ways]) # read lookup table for each of the ways
    
  lookup_table[adapter] <<- total_ways # superassign into lookup table the total ways for this adapter
  
  return(total_ways)
}

p2_solve <- p2 %>% 
  mutate(total_ways = map2_dbl(ways,adapter,sum_ways))
tail(p2_solve)
## # A tibble: 6 x 3
##   adapter ways     total_ways
##     <dbl> <chr>         <dbl>
## 1       7 10, 9, 8    5.67e13
## 2       4 7           5.67e13
## 3       3 4           5.67e13
## 4       2 4, 3        1.13e14
## 5       1 4, 3, 2     2.27e14
## 6       0 3, 2, 1     3.97e14
max(p2_solve$total_ways)
## [1] 396857386627072