2020: Day 10

Setup

The original challenge

My data

Part 1

This is simply a case of ordering the adapters, prepending 0 and appending the max in the list plus three, then finding the differences.

library(dplyr)

adapters <- 
  here::here("2020", "day", "10", "input") %>%
  readLines() %>%
  as.integer()

adapter_diffs <- c(adapters, 0, max(adapters) + 3) %>% 
  sort() %>%
  diff()

sum(adapter_diffs == 1) * sum(adapter_diffs == 3)

[1] 3034

Part 2

Instead of building up sequences of adapters, we see what we can remove from the full list.

First, we check the diffs: are they just 1 and 3 or are there any 2s?

table(adapter_diffs)

adapter_diffs
 1  3 
74 41 

We can’t remove an adapter if its difference with the previous adapter is 3, otherwise the difference between the adapters on either side of it will be too big.

What about diffs of 1? It depends how many ones there are around it. We can check this using the rle() (run length encoding) function

runs <- rle(adapter_diffs)
runs

Run Length Encoding
  lengths: int [1:48] 3 2 4 2 4 2 4 1 4 2 ...
  values : num [1:48] 1 3 1 3 1 3 1 3 1 3 ...

What is the distribution of lengths of sequences of 1s?

runs_table <- table(runs$lengths) 
runs_table

 1  2  3  4 
13 14 10 11 

We have at most four diffs of 1 in a row.

We need to check that if we remove an adapter, the new differences do not exceed 3. Example sequences really helped me figure out what’s going on here:

• If the diff sequence is …, 3, 1, 3,… (e.g. adapters 1, 4, 5, 8)
  • 1 option to keep as is
  • We cannot remove any adapters
  • 1 option in total
• If the diff sequence is …, 3, 1, 1, 3,… (e.g. adapters 1, 4, 5, 6, 9)
  • 1 option to keep as is
  • 1 option to remove one adapter (e.g. the 5)
  • we cannot remove two adapters
  • 2 options total
• If the diff sequence is …, 3, 1, 1, 1, 3,… (e.g. adapters 1, 4, 5, 6, 7, 10)
  • 1 option to keep as is
  • 2 options to remove one adapter (e.g. the 5 or 6)
  • 1 options to remove two adapters (e.g. the 5 and 6)
  • We cannot remove three adapters
  • 4 options total
• If the diff sequence is …, 3, 1, 1, 1, 1, 3,… (e.g. adapters 1, 4, 5, 6, 7, 8, 11)
  • 1 option to keep as is
  • 3 options to remove one adapter (e.g. 5, 6, or 7)
  • 3 options to remove two adapters (e.g. any two of 5, 6, and 7)
  • We cannot remove three adapters
  • 7 options total

Finally, we multiply each run length of difference of 1s with the number of options we have for removing adapters, then take the product of those products.

runs_df <- tibble(lengths = runs$lengths, values = runs$values)

options <- tibble(lengths = c(1,2,3,4), options = c(1,2,4,7))

runs_df %>%
  filter(values == 1) %>%
  left_join(options, by = "lengths") %>%
  summarise(prod_options = prod(options)) %>%
  pull(prod_options) %>%
  format(scientific = FALSE) 

[1] "259172170858496"

Session info

Toggle

─ Session info ───────────────────────────────────────────────────────────────
 setting  value
 version  R version 4.3.1 (2023-06-16)
 os       macOS Sonoma 14.0
 system   aarch64, darwin20
 ui       X11
 language (EN)
 collate  en_US.UTF-8
 ctype    en_US.UTF-8
 tz       Europe/London
 date     2023-11-06
 pandoc   3.1.1 @ /Applications/RStudio.app/Contents/Resources/app/quarto/bin/tools/ (via rmarkdown)
 quarto   1.4.466 @ /usr/local/bin/quarto

─ Packages ───────────────────────────────────────────────────────────────────
 package     * version date (UTC) lib source
 dplyr       * 1.1.2   2023-04-20 [1] CRAN (R 4.3.0)
 sessioninfo * 1.2.2   2021-12-06 [1] CRAN (R 4.3.0)

 [1] /Users/ellakaye/Library/R/arm64/4.3/library
 [2] /Library/Frameworks/R.framework/Versions/4.3-arm64/Resources/library

──────────────────────────────────────────────────────────────────────────────