2025

Day 1 Day 2 Day 3 Day 4 Day 5 Day 6 Day 7 Day 8 Day 9 Day 10 Day 11 Day 12

— R Day 10 Part 1 —

solve_day10_part1 <- function(input) {
  # everything after a [ that is not a ]
  goals <- stringi::stri_extract_first_regex(input, r"{(?<=\[)([^\]]+)}")
  goals <- stringi::stri_split_boundaries(goals, type='character')

  goal_lookup <- c("." = FALSE, "#" = TRUE)
  goals <- lapply(goals, \(goal) goal_lookup[goal])

  # everything between parentheses ()
  button_list <- stringi::stri_extract_all_regex(input, r"{(?<=\()(.+?)(?=\))}")
  to_buttons <- \(button) as.integer(unlist(strsplit(button, ","))) + 1L
  button_list <- lapply(button_list, \(buttons) lapply(buttons, to_buttons))

  num_presses <- mapply(min_presses, goals, button_list)

  sum(num_presses)
}

min_presses <- function(goal, buttons) {
  start <- goal
  start[] <- FALSE # all off

  states <- list(start)
  presses  <- 0L

  n_buttons <- length(buttons)

  visited <- new.env(hash = TRUE, parent = emptyenv())
  key_start <- paste0(as.integer(start), collapse = "")
  visited[[key_start]] <- TRUE

  repeat {
    presses <- presses + 1L

    next_states <- list()
    idx <- 0L

    for (lights in states) {
      for (toggle in buttons) {
        next_lights <- lights
        next_lights[toggle] <- !next_lights[toggle]

        # Exit if at goal ---
        if (identical(next_lights, goal)) {
          return(presses)
        }

        key <- paste0(as.integer(next_lights), collapse = "")
        if (!exists(key, envir = visited, inherits = FALSE)) {
          visited[[key]] <- TRUE
          idx <- idx + 1L
          next_states[[idx]] <- next_lights
        }
      }
    }

    states <- next_states
  }
}
Run
aoc_source(day = 10, part = 1)

input = aoc_read(day = 10)

aoc_run(solve_day10_part1(input))
Elapsed: 0.749 seconds
Memory:  3071 KB

— R Day 10 Part 2 —

solve_day10_part2 <- function(input) {
  # everything after a { that is not a }
  goals <- stringi::stri_extract_first_regex(input, r"{(?<=\{)([^\}]+)}")
  goals <- strsplit(goals, ",")
  goals <- lapply(goals, as.numeric)

  # everything between parentheses ()
  button_list <- stringi::stri_extract_all_regex(input, r"{(?<=\()(.+?)(?=\))}")
  to_buttons <- \(button) as.numeric(unlist(strsplit(button, ","))) + 1
  button_list <- lapply(button_list, \(buttons) lapply(buttons, to_buttons))

  num_presses <- mapply(solve_min_presses, goals, button_list)

  sum(num_presses)
}

solve_min_presses <- function(goal, buttons) {
  n_pos     <- length(goal)
  n_buttons <- length(buttons)

  # Set constraints to find x where
  #   A %*% x = goal

  # Constraint matrix A: rows = positions, cols = buttons
  rows <- unlist(buttons)
  cols <- rep(seq_len(n_buttons), n_buttons)

  constraints_mat <- matrix(0L, nrow = n_pos, ncol = n_buttons)
  for (j in seq_along(buttons)) {
    idx <- buttons[[j]]
    constraints_mat[idx, j] <- 1
  }

  indices <- seq_along(buttons)
  constraints_mat[ unlist(buttons[indices]), indices]

  # Comparison direction of constraint
  constraints_dir <- rep("=", n_pos)

  # Coefficients of objective funtion, all 1
  # That is, all distances are 1 step
  objective <- rep(1, n_buttons)

  result <- lpSolve::lp(
    direction    = "min",
    objective.in = objective,
    const.mat    = constraints_mat,
    const.dir    = constraints_dir,
    const.rhs    = goal,
    all.int      = TRUE
  )

  result$objval
}
Run
aoc_source(day = 10, part = 2)

input = aoc_read(day = 10)

aoc_run(solve_day10_part2(input))
Elapsed: 0.346 seconds
Memory:  1816 KB
Back to top