My 2020 Solutions

Day 1

Part 1

input <- as.numeric(readLines("2020/01-input"))

sum2 <- function(input, target) {
  for (i in input) {
    for (j in input) {
      if (i + j == target) {
        return(i * j)
      }
    }
  }
}

sum2(input, 2020)

[1] 691771

0.01 sec elapsed

Part 2

input <- as.numeric(readLines("2020/01-input"))

sum3 <- function(input, target) {
  for (i in input) {
    for (j in input) {
      for (l in input) {
        if (i + j + l == target) {
          return(i * j * l)
        }
      }
    }
  }
}

sum3(input, 2020)

[1] 232508760

0.043 sec elapsed

Day 2

Part 1

library(purrr)
library(stringr)

input <- readLines("2020/02-input")

password_check <- function(x) {
  numbers <- as.numeric(str_extract_all(x, "[0-9]+")[[1]])
  chars <- str_extract_all(x, "[a-z]+")[[1]]

  count <- str_count(chars[2], chars[1])
  (numbers[1] <= count) & (numbers[2] >= count)
}

sum(map_lgl(input, password_check))

[1] 439

0.078 sec elapsed

Part 2

library(purrr)
library(stringr)

input <- readLines("2020/02-input")

password_check_2 <- function(x) {
  numbers <- as.numeric(str_extract_all(x, "[0-9]+")[[1]])
  chars <- str_extract_all(x, "[a-z]+")[[1]]

  loc1 <- str_sub(chars[2], numbers[1], numbers[1])
  loc2 <- str_sub(chars[2], numbers[2], numbers[2])

  sum(loc1 == chars[1], loc2 == chars[1]) == 1

}

sum(map_lgl(input, password_check_2))

[1] 584

0.063 sec elapsed

Day 3

Part 1

library(purrr)

input <- readLines("2020/03-input")

# turn input into logical matrix
mat <- strsplit(input, "") %>%
  map(~.x == "#") %>%
  reduce(rbind)

traverse <- function(mat, right, down) {
  x <- y <- 1

  height <- nrow(mat)
  width <- ncol(mat)

  # Check tree collision
  trees <- 0
  repeat {
    y <- y + down
    x <- (x + right) %% width
    x <- ifelse(x == 0, width, x)
    trees <- trees + mat[y, x]
    if (y >= height) break
  }
  trees
}

traverse(mat, 3, 1)

elt 
214 

0.017 sec elapsed

Part 2

library(purrr)

input <- readLines("2020/03-input")

# turn input into logical matrix
mat <- strsplit(input, "") %>%
  map(~.x == "#") %>%
  reduce(rbind)

traverse <- function(mat, right, down) {
  x <- y <- 1

  height <- nrow(mat)
  width <- ncol(mat)

  # Check tree collision
  trees <- 0
  repeat {
    y <- y + down
    x <- (x + right) %% width
    x <- ifelse(x == 0, width, x)
    trees <- trees + mat[y, x]
    if (y >= height) break
  }
  trees
}

prod(
  traverse(mat, 1, 1),
  traverse(mat, 3, 1),
  traverse(mat, 5, 1),
  traverse(mat, 7, 1),
  traverse(mat, 1, 2)
)

[1] 8336352024

0.016 sec elapsed

Day 4

Part 1

library(purrr)
library(stringr)
library(magrittr)

input <- readLines("2020/04-input")

passports <- str_split(paste(input, collapse = "\n"), "\n\n")[[1]]

matches <- c("byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid")

valid <- str_extract_all(passports, paste0(matches, collapse = "|")) %>%
  map_lgl(~all(matches %in% .x))

sum(valid)

[1] 182

0.013 sec elapsed

Part 2

library(purrr)
library(stringr)
library(magrittr)

input <- readLines("2020/04-input")

passports <- str_split(paste(input, collapse = "\n"), "\n\n")[[1]]

matches <- c("byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid")

valid <- str_extract_all(passports, paste0(matches, collapse = "|")) %>%
  map_lgl(~all(matches %in% .x))

create_list <- function(x) {
  x <- str_split(x, "[ \n]")[[1]]
  x_split <- str_split(x, ":")

  setNames(map(x_split, 2), map(x_split, 1))
}

password_df <- passports[valid] %>%
  map_dfr(create_list)

int <- as.integer

check_byr <- function(x) int(x) >= 1920 & int(x) <= 2002

check_iyr <- function(x) int(x) >= 2010 & int(x) <= 2020

check_eyr <- function(x) int(x) >= 2020 & int(x) <= 2030

check_hgt <- function(x) {
  value <- as.numeric(str_extract(x, "[0-9]+"))
  unit <- str_remove(x, "[0-9]+")

  if_else(
    unit %in% c("in", "cm"),
    if_else(
      unit == "in",
      value >= 59 & value <= 76,
      value >= 150 & value <= 193
    ),
    FALSE
  )
}

check_hcl <- function(x) {
  str_detect(x, "#[0-9a-f]{6}")
}

check_ecl <- function(x) {
  x %in% c("amb", "blu", "brn", "gry", "grn", "hzl", "oth")
}

check_pid <- function(x) {
  str_detect(x, "^[0-9]{9}$")
}

library(dplyr)

password_df %>%
  filter(
    check_hgt(hgt),
    check_byr(byr),
    check_hcl(hcl),
    check_ecl(ecl),
    check_pid(pid),
    check_iyr(iyr),
    check_eyr(eyr)
  ) %>%
  nrow()

[1] 109

0.093 sec elapsed

Day 5

Part 1

input <- readLines("2020/05-input")

input <- gsub(c("[FL]"), c("0"), input)
input <- gsub(c("[BR]"), c("1"), input)

id <- strtoi(input, base = 2)

max(id)

[1] 888

0.006 sec elapsed

Part 2

input <- readLines("2020/05-input")

input <- gsub(c("[FL]"), c("0"), input)
input <- gsub(c("[BR]"), c("1"), input)

id <- strtoi(input, base = 2)

setdiff(seq(min(id), max(id)), id)

[1] 522

0.007 sec elapsed

Day 6

Part 1

library(tidyverse)
library(tidytext)

answers <- read_file("2020/06-input") %>%
  tibble(input = .) %>%
  unnest_paragraphs(text, input) %>%
  rowid_to_column("group_id") %>%
  unnest_tokens(text, text) %>%
  rowid_to_column("person_id") %>%
  unnest_characters(text, text)

answers %>%
  count(group_id, text) %>%
  nrow()

[1] 6542

1.752 sec elapsed

Part 2

library(tidyverse)
library(tidytext)

answers <- read_file("2020/06-input") %>%
  tibble(input = .) %>%
  unnest_paragraphs(text, input) %>%
  rowid_to_column("group_id") %>%
  unnest_tokens(text, text) %>%
  rowid_to_column("person_id") %>%
  unnest_characters(text, text)

answers %>%
  group_by(group_id) %>%
  mutate(group_size = n_distinct(person_id)) %>%
  count(group_size, text) %>%
  filter(group_size == n) %>%
  nrow()

[1] 3299

0.103 sec elapsed

Day 7

Part 1

library(stringr)
input <- readLines("2020/07-input")

containing_bag <- function(x) {
  str_extract(str_subset(input, paste0(".+", x)), "^.+?bag")
}

used_bags <- c()

new_bags <- "shiny gold bag"

repeat {
  newer_bags <- unique(unlist(lapply(new_bags, containing_bag)))

  if (length(newer_bags) == 0) {
    used_bags <- c(used_bags, new_bags)
    break
  }

  used_bags <- c(used_bags, new_bags)

  new_bags <- setdiff(newer_bags, used_bags)
}

length(setdiff(used_bags, "shiny gold bag"))

[1] 238

5.546 sec elapsed

Part 2

library(stringr)
input <- readLines("2020/07-input")

bags <- str_extract_all(input, "(?<=[0-9] ).*?bag")
number <- str_extract_all(input, "[0-9]+")
number <- lapply(number, as.integer)
names(number) <- names(bags) <- str_extract(input, "^.+?bag")

find_size <- function(x, n) {
  contains <- bags[[x]]
  if (length(contains) == 0) return(n)
  n_bags <- map2_int(contains, number[[x]], find_size)
  sum(c(n_bags, 1L) * n)
}

find_size(x = "shiny gold bag", n = 1) - 1

[1] 82930

0.016 sec elapsed

Day 8

Part 1

input <- readLines("2020/08-input")

run <- function(input, part2 = FALSE) {
  len <- length(input)
  n_times <- integer(len)

  accumulator <- 0

  i <- 1

  repeat {
    x <- strsplit(input[i], " ")[[1]]

    n_times[i] <- n_times[i] + 1

    if (i > len) {
      return(accumulator)
    }
    if (n_times[i] == 2) {
      if (part2) {
        return(NA)
      } else {
        return(accumulator)
      }
    }

    if (x[1] == "nop") {
      i <- i + 1
    } else if (x[1] == "acc") {
      accumulator <- accumulator + readr::parse_number(x[2])
      i <- i + 1
    } else if (x[1] == "jmp") {
      i <- i + readr::parse_number(x[2])
    }
  }
}

run(input)

[1] 1654

0.224 sec elapsed

Part 2

library(stringr)

input <- readLines("2020/08-input")

run <- function(input, part2 = FALSE) {
  len <- length(input)
  n_times <- integer(len)

  accumulator <- 0

  i <- 1

  repeat {
    x <- strsplit(input[i], " ")[[1]]

    n_times[i] <- n_times[i] + 1

    if (i > len) {
      return(accumulator)
    }
    if (n_times[i] == 2) {
      if (part2) {
        return(NA)
      } else {
        return(accumulator)
      }
    }

    if (x[1] == "nop") {
      i <- i + 1
    } else if (x[1] == "acc") {
      accumulator <- accumulator + readr::parse_number(x[2])
      i <- i + 1
    } else if (x[1] == "jmp") {
      i <- i + readr::parse_number(x[2])
    }
  }
}

for (i in seq_along(input)) {
  input0 <- input
  if (str_detect(input0[i], "acc")) next

  if (str_detect(input0[i], "nop")) {
    input0[i] <- str_replace(input0[i], "nop", "jmp")
  } else {
    input0[i] <- str_replace(input0[i], "jmp", "nop")
  }

  res <- run(input0, part2 = TRUE)
  if(!is.na(res)) break
}
res

[1] 833

17.011 sec elapsed

Day 9

Part 1

input <- as.numeric(readLines("2020/09-input"))

i <- 1

repeat {
  sums <- colSums(combn(input[seq(i, i + 24)], 2))
  if(!any(input[i + 25] == sums)) break
  i <- i + 1
}

input[i + 25]

[1] 1930745883

0.162 sec elapsed

Part 2

input <- as.numeric(readLines("2020/09-input"))

i <- 1

repeat {
  sums <- colSums(combn(input[seq(i, i + 24)], 2))
  if(!any(input[i + 25] == sums)) break
  i <- i + 1
}

target <- input[i + 25]

i <- 1
step <- 1

repeat {
  res <- sum(input[seq(i, i + step)])

  if (res == target) break

  if (res > target) {
    i <- i + 1
    step <- 1
    next
  }
  step <- step + 1
}

sum(range(input[seq(i, i + step)]))

[1] 268878261

1.353 sec elapsed

Day 10

Part 1

input <- as.integer(readLines("2020/10-input"))

res <- table(diff(sort(input)))

prod(res + 1)

[1] 1984

0.002 sec elapsed

Part 2

input <- sort(as.integer(readLines("2020/10-input")))

runs <- rle(c(diff(c(0, input))))
weights <- c(1, 2, 4, 7)

options(scipen = 999)
prod(weights[runs$lengths[runs$values == 1]])

[1] 3543369523456

0.002 sec elapsed

Day 11

Part 1

input <- readLines("2020/11-input")

# turn input into logical matrix
mat <- strsplit(input, "") %>%
  reduce(rbind)

replace <- mat

repeat {
  for (i in seq_len(nrow(mat))) {
    for (j in seq_len(ncol(mat))) {
      if (mat[i, j] == ".") next

      temp_mat <- mat
      temp_mat[i, j] <- ""

      conv <- temp_mat[seq(max(i-1, 1), min(i+1, nrow(mat))),
                       seq(max(j-1, 1), min(j+1, ncol(mat)))]

      if (mat[i, j] == "L") {
        if (all(conv != "#")) {
          replace[i, j] <- "#"
        }
      }

      if (mat[i, j] == "#") {
        if (sum(conv == "#") >= 4) {
          replace[i, j] <- "L"
        }
      }
    }
  }

  if (identical(mat, replace)) break
  mat <- replace
}

sum(mat == "#")

[1] 2113

35.157 sec elapsed

Part 2

input <- readLines("2020/11-input")

# turn input into logical matrix
mat <- strsplit(input, "") %>%
  reduce(rbind)

find_neighbor <- function(mat, i, j, x, y) {
  res <- "."
  i <- i + y
  j <- j + x
  while (i > 0 & j > 0 & j <= ncol(mat) & i <= nrow(mat)) {
    value <- mat[i,j]
    if (value != ".") {
      res <- value
      break
    }
    i <- i + y
    j <- j + x
  }
  res
}

find_all_neighbors <- function(mat, i, j) {

  up <-   find_neighbor(mat, i, j, 0, -1)
  down <- find_neighbor(mat, i, j, 0, 1)
  right <- find_neighbor(mat, i, j, -1, 0)
  left <-  find_neighbor(mat, i, j, 1, 0)

  upright <- find_neighbor(mat, i, j, 1, -1)
  upleft <- find_neighbor(mat, i, j, -1, -1)
  downright <- find_neighbor(mat, i, j, 1, 1)
  downleft <- find_neighbor(mat, i, j, -1, 1)

  c(up, down, right, left, upright, upleft, downright, downleft)
}

replace <- mat

repeat {
  for (i in seq_len(nrow(mat))) {
    for (j in seq_len(ncol(mat))) {
      if (mat[i, j] == ".") next

      conv <- find_all_neighbors(mat, i, j)


      if (mat[i, j] == "L") {
        if (all(conv != "#")) {
          replace[i, j] <- "#"
        }
      }

      if (mat[i, j] == "#") {
        if (sum(conv == "#") >= 5) {
          replace[i, j] <- "L"
        }
      }
    }
  }

  if (identical(mat, replace)) break

  mat <- replace
}

sum(mat == "#")

[1] 1865

18.343 sec elapsed

Day 12

Part 1

input <- readLines("2020/12-input")

ship <- c(0, 0)
direction <- c(1, 0)

rotate <- function(x, phi) {
  c(x[1] * cos(phi * pi / 180) - x[2] * sin(phi * pi / 180),
    x[1] * sin(phi * pi / 180) + x[2] * cos(phi * pi / 180))
}

for (i in input) {
  value <- as.numeric(str_extract(i, "[0-9]+"))
  switch(
    substr(i, 1, 1),
    N = {ship[2] <- ship[2] + value},
    S = {ship[2] <- ship[2] - value},
    E = {ship[1] <- ship[1] + value},
    W = {ship[1] <- ship[1] - value},
    L = {direction <- rotate(direction, value)},
    R = { direction <- rotate(direction, -value)},
    F = {ship <- ship + direction * value}
  )
}

sum(abs(ship))

[1] 1496

0.033 sec elapsed

Part 2

input <- readLines("2020/12-input")

ship <- c(0, 0)

waypoint <- c(10, 1)

rotate <- function(x, phi) {
  c(x[1] * cos(phi * pi / 180) - x[2] * sin(phi * pi / 180),
    x[1] * sin(phi * pi / 180) + x[2] * cos(phi * pi / 180))
}

for (i in input) {
  value <- as.numeric(str_extract(i, "[0-9]+"))

  switch(
    substr(i, 1, 1),
    N = {waypoint[2] <- waypoint[2] + value},
    S = {waypoint[2] <- waypoint[2] - value},
    E = {waypoint[1] <- waypoint[1] + value},
    W = {waypoint[1] <- waypoint[1] - value},
    L = {waypoint <- rotate(waypoint, value)},
    R = {waypoint <- rotate(waypoint, -value)},
    F = {ship <- ship + waypoint * value}
  )
}

sum(abs(ship))

[1] 63843

0.024 sec elapsed

Day 13

Part 1

input <- readLines("2020/13-input")

target <- as.integer(input[1])
ids <- as.integer(str_extract_all(input[2], "[0-9]+")[[1]])

time_past <- ceiling(target / ids) * ids
which_min <- min(time_past) == time_past

(time_past[which_min] - target) * ids[which_min]

[1] 2845

0.002 sec elapsed

Part 2

input <- readLines("2020/13-input")

ids <- as.numeric(str_split(input[2], ",")[[1]])
offset <- seq_along(ids) - 1
offset <- offset[!is.na(ids)]
ids <- ids[!is.na(ids)]

timestamp <- 1
step <- 1

for (i in seq_along(ids)) {
  repeat {
    if ((timestamp + offset[i]) %% ids[i] == 0) break
    timestamp <- timestamp + step
  }

  step <- prod(ids[seq_len(i)])
}

options(scipen = 999)
timestamp

[1] 487905974205117

0.007 sec elapsed

Day 14

Part 1

library(stringr)

input <- readLines("2020/14-input")

intTo36 <- function(x) {
  as.character(c(rep(0, 4), rev(as.integer(intToBits(x)))))
}

`[<-.memory` <- function(x, i, value) {
  res <- intTo36(value)
  res[mask != "X"] <- mask[mask != "X"]
  x[[i]] <- res
  x
}

mem <- list()
attr(mem, "class") <- "memory"

for (line in input) {
  if (grepl("^mask", line)) {
    mask <- strsplit(str_extract(line, "[X0-9]+"), "")[[1]]
    next
  }
  eval(parse(text = line))
}

options(scipen = 999)
sum(map_dbl(mem, ~ sum(as.numeric(.x) * (2 ^ seq(35, 0)))))

[1] 15514035145260

0.831 sec elapsed

Part 2

Day 15

Part 1

input <- c(16,1,0,18,12,14,19)

res <- rep(-1, 2020)
res[seq_along(input)] <- input
for (i in 8:2020) {
  if (sum(res == res[i- 1]) == 1) {
    res[i] <- 0
  } else {
    last_calls <- which(res == res[i- 1])
    res[i] <- last_calls[length(last_calls)] - last_calls[length(last_calls) - 1]
  }
}
rev(res)[1]

[1] 929

0.056 sec elapsed

Part 2

Day 16

Part 1

library(tidyverse)
input <- readLines("2020/16-input")
breaks <- which(input == "")

valid_values <- input[seq(1, min(breaks) - 1)] %>%
  str_extract_all("[0-9]+") %>%
  map(as.numeric) %>%
  map(~ c(seq(.x[1], .x[2]), seq(.x[3], .x[4])))

tickets <- read.csv("2020/16-input", header = FALSE,
                    skip = which(input == "nearby tickets:"))

all_valid_values <- unlist(valid_values)

check_value <- function(x, ref) {
  map_dbl(x, ~ ifelse(.x %in% ref, NA, .x))
}

wrong <- apply(tickets, 2, check_value, all_valid_values)

sum(wrong, na.rm = TRUE)

[1] 20060

0.359 sec elapsed

Part 2

library(tidyverse)
input <- readLines("2020/16-input")
breaks <- which(input == "")

valid_values <- input[seq(1, min(breaks) - 1)] %>%
  str_extract_all("[0-9]+") %>%
  map(as.numeric) %>%
  map(~ c(seq(.x[1], .x[2]), seq(.x[3], .x[4])))

tickets <- read.csv("2020/16-input", header = FALSE,
                    skip = which(input == "nearby tickets:"))

all_valid_values <- unlist(valid_values)

check_value <- function(x, ref) {
  map_dbl(x, ~ ifelse(.x %in% ref, NA, .x))
}

wrong <- apply(tickets, 2, check_value, all_valid_values)

valid_ticket <- tickets[rowSums(!is.na(wrong)) == 0, ]

can_be <- function(x) {
  which(map_lgl(valid_values, ~all(x %in% .x)))
}

pos <- numeric(length(valid_values))

candidates <- map(valid_ticket, can_be)

repeat {
  variable_ind <- which(lengths(candidates) == 1)
  if(length(variable_ind) == 0) break

  ref_ind <- candidates[[variable_ind]]

  pos[variable_ind] <- ref_ind

  candidates <- map(candidates, setdiff, ref_ind)
}

my_ticket <- as.numeric(str_split(input[min(breaks) + 2], ",")[[1]])

fields <- input[seq(1, min(breaks) - 1)] %>%
  str_detect("^departure")

options(scipen = 999)
prod(my_ticket[fields[pos]])

[1] 2843534243843

0.249 sec elapsed

Day 17

Part 1

library(dplyr)
library(tidyr)

input <- readLines("2020/17-input")

start <- tibble(
  x = rep(seq(7, 14), 8),
  y = rev(rep(seq(7, 14), each = 8)),
  z = 10,
  state = strsplit(input, "") %>% unlist()
)

space <- expand_grid(x = seq(1, 20), y = seq(1, 20), z = seq(1, 20)) %>%
  left_join(start, by = c("x", "y", "z")) %>%
  mutate(state = if_else(is.na(state), ".", state)) %>%
  mutate(row = row_number())

find_neighbors <- function(dat) {
  space %>%
    filter(abs(x - dat$x) <= 1, abs(y - dat$y) <= 1, abs(z - dat$z) <= 1,
           !(x == dat$x & y == dat$y & z == dat$z)) %>%
    pull(row)
}

all_neighbors <- map(seq_len(nrow(space)), ~find_neighbors(space[.x, ]))

next_state <- function(x, nbs) {
  if (x == "#") {
    if (sum(nbs == "#") %in% c(2, 3)) {
      return("#")
    } else {
      return(".")
    }
  } else {
    if (sum(nbs == "#") == 3) {
      return("#")
    } else {
      return(".")
    }
  }
}

for(iter in 1:6) {
  all_neighbors_states <- map(all_neighbors, ~ space$state[.x])
  space$state <- map2_chr(space$state, all_neighbors_states, next_state)
}

sum(space$state == "#")

[1] 280

18.453 sec elapsed

Part 2

library(dplyr)
library(tidyr)
input <- readLines("2020/17-input")


start <- tibble(
  x = rep(seq(7, 14), 8),
  y = rev(rep(seq(7, 14), each = 8)),
  z = 0,
  w = 0,
  state = strsplit(input, "") %>% unlist()
)

space <- expand_grid(x = seq(1, 20),
                     y = seq(1, 20),
                     z = seq(-6, 6),
                     w = seq(-6, 6)) %>%
  left_join(start, by = c("x", "y", "z", "w")) %>%
  mutate(state = if_else(is.na(state), ".", state)) %>%
  mutate(row = row_number())

find_neighbors <- function(dat) {
  space %>%
    filter(abs(x - dat$x) <= 1,
           abs(y - dat$y) <= 1,
           abs(z - dat$z) <= 1,
           abs(w - dat$w) <= 1,
           !(x == dat$x & y == dat$y & z == dat$z & w == dat$w)) %>%
    pull(row)
}

all_neighbors <- map(seq_len(nrow(space)), ~find_neighbors(space[.x, ]))

next_state <- function(x, nbs) {
  if (x == "#") {
    if (sum(nbs == "#") %in% c(2, 3)) {
      return("#")
    } else {
      return(".")
    }
  } else {
    if (sum(nbs == "#") == 3) {
      return("#")
    } else {
      return(".")
    }
  }
}

for(iter in 1:6) {
  all_neighbors_states <- map(all_neighbors, ~ space$state[.x])
  space$state <- map2_chr(space$state, all_neighbors_states, next_state)
}

sum(space$state == "#")

[1] 1696

442.808 sec elapsed

Day 18

Part 1

library(stringr)
library(purrr)
input <- readLines("2020/18-input")

`%+%` <- function(a, b) a + b
`%*%` <- function(a, b) a * b

eval_string <- function(x) {
  map_dbl(x, ~eval(parse(text = .x)))
}

options(scipen = 999)
input %>%
  str_replace_all(c("\\+" = "%\\+%", "\\*" = "%\\*%")) %>%
  eval_string() %>%
  sum()

[1] 8298263963837

0.014 sec elapsed

Part 2

library(stringr)
library(purrr)
input <- readLines("2020/18-input")

eval_string_rev <- function(x) {
  rev_env <- new.env()
  rev_env$`+` <- function(a, b) base::`*`(a, b)
  rev_env$`*` <- function(a, b) base::`+`(a, b)
  map_dbl(x, ~eval(parse(text = .x), envir = rev_env))
}

options(scipen = 999)
input %>%
  str_replace_all(c("\\+" = "temp", "\\*" = "+", "temp" = "*")) %>%
  eval_string_rev() %>%
  sum()

[1] 145575710203332

0.01 sec elapsed

Day 19

Part 1

library(stringr)
library(purrr)
input <- readLines("2020/19-input")
break_point <- which(input == "")

rules_raw <- input[seq(1, break_point - 1)]
rules_raw <- str_remove_all(rules_raw, "\"")
rules_raw <- str_split(rules_raw, ": ")
rules <- map_chr(rules_raw, 2)
rules <- map_chr(str_split(rules, " "), ~paste(glue::glue("_{.x}_"),collapse = ""))
rules <- str_replace_all(rules, c("_\\|_" = "\\|", "_a_" = "a", "_b_" = "b"))
rules <- paste0("(", rules, ")")
names(rules) <- paste0("_", map(rules_raw, 1), "_")

messages <- input[seq(break_point + 1, length(input))]

master <- "_0_"
while(str_detect(master, "[0-9]")) {
  master <- str_replace_all(master, rules)
}

sum(str_detect(messages, glue::glue("^{master}$")))

[1] 162

0.115 sec elapsed

Part 2

library(stringr)
library(purrr)
input <- readLines("2020/19-input")
break_point <- which(input == "")

rules_raw <- input[seq(1, break_point - 1)]
rules_raw <- str_remove_all(rules_raw, "\"")
rules_raw <- str_split(rules_raw, ": ")
rules <- map_chr(rules_raw, 2)
rules <- map_chr(str_split(rules, " "), ~paste(glue::glue("_{.x}_"),collapse = ""))
rules <- str_replace_all(rules, c("_\\|_" = "\\|", "_a_" = "a", "_b_" = "b"))
rules <- paste0("(", rules, ")")
names(rules) <- paste0("_", map(rules_raw, 1), "_")
rules["_8_"] <- "(_42_+)"
rules["_11_"] <- "(_42__31_|_42__42__31__31_|_42__42__42__31__31__31_|_42__42__42__42__31__31__31__31_|_42__42__42__42__42__31__31__31__31__31_|_42__42__42__42__42__42__42__31__31__31__31__31__31__31_)"

messages <- input[seq(break_point + 1, length(input))]

master <- "_0_"
while(str_detect(master, "[0-9]")) {
  master <- str_replace_all(master, rules)
}

sum(grepl(glue::glue("^{master}$"), messages))

[1] 267

0.282 sec elapsed

Day 20

Part 1

library(tidyverse)

input <- read_file("2020/20-input")
input <- str_remove(input, "\n$")

tiles <- str_split(input, "\n\n")[[1]]

tile_info <- function(x) {
  lines <- str_split(x, "\n")[[1]]

  id <- str_extract(lines[1], "[0-9]+")
  grid <- lines[-1]

  sides <- c(
    paste0(str_sub(grid, 1, 1), collapse = ""),
    paste0(str_sub(grid, length(grid), length(grid)), collapse = ""),
    grid[c(1, length(grid))]
  )

  tibble(id, side = c(sides, stringi::stri_reverse(sides)))
}

tile_sides <- map_dfr(tiles, tile_info)

options(scipen = 999)
joints <- inner_join(tile_sides, tile_sides, by = "side") %>%
  filter(id.x != id.y) %>%
  transmute(pair = map2_chr(id.x, id.y, ~
                              paste(sort(c(.x, .y)), collapse = " ")
  )) %>%
  distinct() %>%
  separate(pair, c("a", "b"), " ")

joints %>%
  pivot_longer(everything()) %>%
  count(value) %>%
  filter(n == 2) %>%
  summarize(res = prod(as.numeric(value))) %>%
  pull(res)

[1] 18482479935793

0.227 sec elapsed

Part 2

library(tidyverse)

input <- read_file("2020/20-input")
input <- str_remove(input, "\n$")

tiles <- str_split(input, "\n\n")[[1]]

tile_info <- function(x) {
  lines <- str_split(x, "\n")[[1]]

  id <- str_extract(lines[1], "[0-9]+")
  grid <- lines[-1]

  sides <- c(
    paste0(str_sub(grid, 1, 1), collapse = ""),
    paste0(str_sub(grid, length(grid), length(grid)), collapse = ""),
    grid[c(1, length(grid))]
  )

  tibble(id, side = c(sides, stringi::stri_reverse(sides)))
}

tile_sides <- map_dfr(tiles, tile_info)

options(scipen = 999)
joints <- inner_join(tile_sides, tile_sides, by = "side") %>%
  filter(id.x != id.y) %>%
  transmute(pair = map2_chr(id.x, id.y, ~
                              paste(sort(c(.x, .y)), collapse = " ")
  )) %>%
  distinct() %>%
  separate(pair, c("a", "b"), " ")

current <- joints %>%
  pivot_longer(everything()) %>%
  count(value) %>%
  filter(n == 2) %>%
  slice(1) %>%
  pull(value)

middle <- joints %>%
  pivot_longer(everything()) %>%
  count(value) %>%
  filter(n == 4) %>%
  pull(value)

non_middle <- joints %>%
  filter(!a %in% middle, !b %in% middle)

places <- matrix(NA, 12, 12)

used <- c()
round <- c()

repeat {
  round <- c(round, current)

  next_tile <- non_middle %>%
    filter(a %in% current | b %in% current, !a %in% used, !b %in% used) %>%
    slice(1) %>%
    unlist() %>%
    setdiff(current)

  if(length(next_tile) == 0) break
  used <- c(used, current)
  current <- next_tile
}

places[1, 1:12] <- round[1:12]
places[2:12, 12] <- round[13:23]
places[12, 11:1] <- round[24:34]
places[11:2, 1] <- round[35:44]

for (i in 2:11) {
  for (j in 2:11) {
    partners <- c(places[i-1, j], places[i, j-1])

    places[i, j] <- intersect(
      joints %>%
        filter(a %in% partners[1] | b %in% partners[1]) %>%
        unlist() %>%
        setdiff(partners[1]),
      joints %>%
        filter(a %in% partners[2] | b %in% partners[2]) %>%
        unlist() %>%
        setdiff(partners[1])
    ) %>%
      setdiff(places[i - 1, j - 1])
  }
}

extract_full_grid <- function(x) {
  str_split(x, "\n")[[1]][-1] %>%
    str_split("") %>%
    unlist() %>%
    matrix(nrow = 10, byrow = TRUE)
}

full_tiles <- map(tiles, extract_full_grid)
names(full_tiles) <- str_extract(tiles, "[0-9]+")

rotate <- function(x) t(apply(x, 2, rev))

all_tiles <- map(1:12, ~map(1:12, ~list()))

all_tiles[[1]][[1]] <- full_tiles[[places[1, 1]]][, 10:1]

all_symmmetries <- list(
  function(x) x,
  function(x) rotate(x),
  function(x) rotate(rotate(x)),
  function(x) rotate(rotate(rotate(x))),
  function(x) x[, 10:1],
  function(x) rotate(x[, 10:1]),
  function(x) rotate(rotate(x[, 10:1])),
  function(x) rotate(rotate(rotate(x[, 10:1])))
)

for (i in 2:12) {
  tile <- full_tiles[[places[1, i]]]

  tile_symmetries <- map(all_symmmetries, ~.x(tile))

  tile_which <- map_lgl(tile_symmetries, ~ all(all_tiles[[1]][[i - 1]][, 10] == .x[, 1]))

  all_tiles[[1]][[i]] <- tile_symmetries[[which(tile_which)]]
}

for (j in 2:12) {
  for (i in 1:12) {
    tile <- full_tiles[[places[j, i]]]

    tile_symmetries <- map(all_symmmetries, ~.x(tile))

    tile_which <- map_lgl(tile_symmetries, ~ all(all_tiles[[j - 1]][[i]][10, ] == .x[1, ]))

    all_tiles[[j]][[i]] <- tile_symmetries[[which(tile_which)]]
  }
}

x <- all_tiles[[1]][[1]]

get_inner <- function(x) {
  x[2:9, 2:9]
}

lake <- reduce(map(all_tiles, ~reduce(map(.x, get_inner), cbind)), rbind)

monster <- c(
  "                  # ",
  "#    ##    ##    ###",
  " #  #  #  #  #  #   "
) %>%
  str_split("") %>%
  unlist() %>%
  matrix(nrow = 3, byrow = TRUE)


for (turn in 1:8) {
  for (i in 1:94) {
    for (j in 1:77) {
      inlake <- lake[seq(i, i + 2), seq(j, j + 19)][monster == "#"]

      if (all(inlake %in% c("#", "0"))) {
        lake[seq(i, i + 2), seq(j, j + 19)][monster == "#"] <- "0"
      }
    }
  }
  lake <- rotate(lake)
  if(turn == 4) {
    lake <- lake[, seq_len(nrow(lake))]
  }
}

sum(lake == "#")

[1] 2118

1.719 sec elapsed

Day 21

Part 1

library(stringr)
library(purrr)

input <- readLines("2020/21-input")

allergies <- str_extract(input, "\\(.*")
allergies <- str_remove(allergies, "\\(contains ")
allergies <- str_remove(allergies, "\\)")
allergies <- str_split(allergies, ", ")

ingredient <- str_extract(input, "[ a-z]+")
ingredient <- str_extract_all(ingredient, "[a-z]+")

all_allergies <- unique(unlist(allergies))
all_ingredient <- character(length(all_allergies))

repeat {
  res <- length(unlist(ingredient))

  for (i in seq_along(all_allergies)) {
    x <- all_allergies[i]

    x_foods <- ingredient[map_lgl(allergies, ~any(.x %in% x))]

    candidates <- reduce(x_foods, intersect)
    if (length(candidates) != 1) next
    all_ingredient[i] <- candidates
    ingredient <- map(ingredient, setdiff, all_ingredient)
  }

  new_res <- length(unlist(ingredient))

  if (res == new_res) break
  res <- new_res
}

length(unlist(ingredient))

[1] 2724

0.04 sec elapsed

Part 2

library(stringr)
library(purrr)

input <- readLines("2020/21-input")

allergies <- str_extract(input, "\\(.*")
allergies <- str_remove(allergies, "\\(contains ")
allergies <- str_remove(allergies, "\\)")
allergies <- str_split(allergies, ", ")

ingredient <- str_extract(input, "[ a-z]+")
ingredient <- str_extract_all(ingredient, "[a-z]+")

all_allergies <- unique(unlist(allergies))
all_ingredient <- character(length(all_allergies))

repeat {
  res <- length(unlist(ingredient))

  for (i in seq_along(all_allergies)) {
    x <- all_allergies[i]

    x_foods <- ingredient[map_lgl(allergies, ~any(.x %in% x))]

    candidates <- reduce(x_foods, intersect)
    if (length(candidates) != 1) next
    all_ingredient[i] <- candidates
    ingredient <- map(ingredient, setdiff, all_ingredient)
  }

  new_res <- length(unlist(ingredient))

  if (res == new_res) break
  res <- new_res
}

paste(all_ingredient[order(all_allergies)], collapse = ",")

[1] "xlxknk,cskbmx,cjdmk,bmhn,jrmr,tzxcmr,fmgxh,fxzh"

0.028 sec elapsed

Day 22

Part 1

input <- readLines("2020/22-input")

bp <- which(input == "")

player1 <- as.numeric(input[seq(2, bp-1)])
player2 <- as.numeric(input[seq(bp + 2, length(input))])

repeat {
  if (player1[1] > player2[1]) {
    player1 <- c(player1[-1], player1[1], player2[1])
    player2 <- player2[-1]
  } else {
    player2 <- c(player2[-1], player2[1], player1[1])
    player1 <- player1[-1]
  }
  if (length(player1) == 0 | length(player2) == 0) break
}

sum(player1 * rev(seq_along(player1))) +
  sum(player2 * rev(seq_along(player2)))

[1] 32472

0.011 sec elapsed

Part 2

library(purrr)

input <- readLines("2020/22-input")

bp <- which(input == "")

player1 <- as.numeric(input[seq(2, bp - 1)])
player2 <- as.numeric(input[seq(bp + 2, length(input))])

play_game <- function(hand1, hand2, subgame = FALSE) {
  previous_hands1 <- list()
  previous_hands2 <- list()
  repeat {
    if (any(map_lgl(previous_hands1, ~identical(.x, hand1))) &
        any(map_lgl(previous_hands2, ~identical(.x, hand2)))) {
      if (subgame) {
        return(TRUE)
      } else {
        return(sum(hand1 * rev(seq_along(hand1))) +
                 sum(hand2 * rev(seq_along(hand2))))
      }
    }

    draw1 <- hand1[1]
    draw2 <- hand2[1]

    optim <- (max(hand1) > max(hand2)) &
      max(hand1) > (length(c(hand1, hand2))) &
      subgame
    if(optim) {
      return(TRUE)
    }


    if (draw1 < length(hand1) & draw2 < length(hand2)) {
      winner <- play_game(hand1[seq_len(draw1) + 1],
                          hand2[seq_len(draw2) + 1], subgame = TRUE)
    } else {
      winner <- hand1[1] > hand2[1]
    }

    previous_hands1 <- c(previous_hands1, list(hand1))
    previous_hands2 <- c(previous_hands2, list(hand2))

    if (winner) {
      hand1 <- c(hand1[-1], hand1[1], hand2[1])
      hand2 <- hand2[-1]
    } else {
      hand2 <- c(hand2[-1], hand2[1], hand1[1])
      hand1 <- hand1[-1]
    }
    if (length(hand1) == 0 | length(hand2) == 0) break
  }

  if (subgame) {
    return(length(hand2) == 0)
  } else {
    return(sum(hand1 * rev(seq_along(hand1))) +
           sum(hand2 * rev(seq_along(hand2))))
  }
}

play_game(player1, player2)

[1] 36463

17.005 sec elapsed

Day 23

Part 1

input <- c(4, 7, 6, 1, 3, 8, 2, 5, 9)
current <- input[1]

a <- numeric(length(input))

input_len <- length(input)

for (i in seq_along(a)) {
  which_i <- which(input == i)
  if (which_i == input_len) {
    a[i] <- input[1]
  } else {
    a[i] <- input[which_i + 1]
  }
}

for (i in 1:100) {

  pick1 <- a[current]
  pick2 <- a[pick1]
  pick3 <- a[pick2]
  pick4 <- a[pick3]

  a[current] <- pick4

  dest <- current - 1

  if (dest == 0) {
    dest <- input_len
  }

  while (dest %in% c(pick1, pick2, pick3)) {
    dest <- dest - 1
  }

  if (dest == 0) {
    dest <- input_len
  }

  while (dest %in% c(pick1, pick2, pick3)) {
    dest <- dest - 1
  }

  end <- a[dest]

  a[pick3] <- end
  a[dest] <- pick1

  current <- a[current]
}

res <- numeric(length(a))
res[1] <- 1

for (i in 2:length(a)) {
  res[i] <- a[res[i-1]]
}

paste0(res[-1], collapse = "")

[1] "97245386"

0.029 sec elapsed

Part 2

input <- c(4, 7, 6, 1, 3, 8, 2, 5, 9)
current <- input[1]

a <- numeric(length(input))

input_len <- length(input)

a <- c(3, 5, 8, 7, 9, 1, 6, 2, 10,  seq(11, 1000000), 4)

tictoc::tic()
for (i in 1:10000000) {

  pick1 <- a[current]
  pick2 <- a[pick1]
  pick3 <- a[pick2]
  pick4 <- a[pick3]

  a[current] <- pick4

  dest <- current - 1

  if (dest == 0) {
    dest <- input_len
  }

  while (dest %in% c(pick1, pick2, pick3)) {
    dest <- dest - 1
  }

  if (dest == 0) {
    dest <- input_len
  }

  while (dest %in% c(pick1, pick2, pick3)) {
    dest <- dest - 1
  }

  end <- a[dest]

  a[pick3] <- end
  a[dest] <- pick1

  current <- a[current]
}
tictoc::toc()

a[1] * a[a[1]]

25.478 sec elapsed

[1] 43717931544

25.49 sec elapsed

Day 24

Part 1

library(stringr)
library(purrr)

input <- readLines("2020/24-input")

moves <- c(
  e = 1 + 0i,
  se = 0 - 1i,
  sw = -1 - 1i,
  w = -1 + 0i,
  nw = 0 + 1i,
  ne = 1 + 1i
)
flips <- input %>%
  str_extract_all("[ns]?[ew]") %>%
  map(~moves[.x]) %>%
  map(sum) %>%
  reduce(c)

flips %>%
  table() %>%
  {sum(. %% 2 == 1)}

[1] 386

0.013 sec elapsed

Part 2

library(stringr)
library(purrr)

input <- readLines("2020/24-input")

moves <- c(
  e = 1 + 0i,
  se = 0 - 1i,
  sw = -1 - 1i,
  w = -1 + 0i,
  nw = 0 + 1i,
  ne = 1 + 1i
)
flips <- input %>%
  str_extract_all("[ns]?[ew]") %>%
  map(~moves[.x]) %>%
  map(sum) %>%
  reduce(c)

n_neighbors <- function(x, y, moves) {
  rowSums(matrix(outer(x, moves, `+`) %in% y, ncol = length(moves)))
}
black <- as.complex(names(table(flips)[table(flips) %% 2 == 1]))

for (i in 1:100) {
  stay_black <- n_neighbors(black, black, moves) == 1

  white_candidates <- map(black, ~.x + moves) %>%
    unlist() %>%
    unique()

  new_black_ind <- n_neighbors(white_candidates, black, moves) == 2

  new_black <- white_candidates[new_black_ind]

  black <- c(black[stay_black], new_black)
}

length(black)

[1] 4214

1.635 sec elapsed

Day 25

Part 1

div <- 20201227

card_public <- 10943862
door_public <- 12721030

transform <- function(subject, lpt) {
  value <- 1
  c <- 0
  while (c < lpt) {
    value <- value * subject
    value <- value %% div
    c <- c + 1
  }
  value
}

bruteforce <- function(value_goal) {
  lpt <- 1
  value <- 1
  repeat {
    value <- value * 7
    value <- value %% div
    if (value == value_goal) {
      return(lpt)
    }
    lpt <- lpt + 1
  }
}

card_lpt_size <- bruteforce(card_public)
door_lpt_size <- bruteforce(door_public)

transform(door_public, card_lpt_size)

[1] 5025281

8.838 sec elapsed