2024

Day 1 Day 2 Day 3 Day 4 Day 5 Day 6 Day 7 Day 8 Day 9 Day 10 Day 11 Day 12 Day 13 Day 14 Day 15 Day 16

R

— R Day 16 Part 1 —

solve_day16_part1 <- function(input) {
  nrows <- length(input)
  maze <<- matrix(unlist(strsplit(input, "")),
                 nrow = nrows,
                 byrow = TRUE)
  ncols <- NCOL(maze)

  start <- which(maze == "S", arr.ind = TRUE)
  end <- which(maze == "E", arr.ind = TRUE)
  # N, E, S, W as 1, 2, 3, 4
  dirs <<- list(c(-1L, 0L), c(0L, 1L), c(1L, 0L), c(0L, -1L))

  cost_queue <- vector("list", nrows * ncols)
  # store each position as pos[x, y], facing, cost
  # starting with 2 for East and 0 cost:
  cost_queue[1L] <- list(c(list(start), 2L, 0L))
  free_ptr <- 2L
  min_cost_ptr <- 1L

  # visited 3D array with facing as 3rd dimension?
  visited <<- array(Inf, dim = c(nrows, ncols, 4L))

  pos <- cost_queue[[min_cost_ptr]][[1L]]
  facing <- cost_queue[[min_cost_ptr]][[2L]]
  cost <- cost_queue[[min_cost_ptr]][[3L]]

  while(any(pos != end)) {
    # identify next possible positions and there costs
    # +1L cost for moving in the current dir
    # +1000L cost for rotating
    increase <- 1L

    # add to cost_queue and visited?
    cost_queue <- add_pos(cost_queue, free_ptr, pos, facing, cost, increase)
    free_ptr <- which_free(cost_queue)

    # turns cost more
    increase <- 1000L
    # 90 degrees clockwise
    facing <- facing %% 4L + 1L
    cost_queue <- add_pos(cost_queue, free_ptr, pos, facing, cost, increase)
    free_ptr <- which_free(cost_queue)

    # 90 degrees anticlockwise (270 anticlockwise)
    facing <- facing %% 4L + 1L
    facing <- facing %% 4L + 1L
    cost_queue <- add_pos(cost_queue, free_ptr, pos, facing, cost, increase)
    free_ptr <- which_free(cost_queue)

    # remove current item from queue
    # TODO: stop shrinking the queue
    cost_queue[min_cost_ptr] <- NULL
    free_ptr <- which_free(cost_queue)

    # find next position with lowest cost
    min_cost_ptr <- which_min_cost(cost_queue)

    pos <- cost_queue[[min_cost_ptr]][[1L]]
    facing <- cost_queue[[min_cost_ptr]][[2L]]
    cost <- cost_queue[[min_cost_ptr]][[3L]]
  }

  visited[pos[[1L]], pos[[2L]], facing]
}

#' Find the first free space in the cost queue
which_free <- function(cost_queue) {
  empty <- vapply(cost_queue, is.null, logical(1))

  if (any(empty)) {
    which.max(empty) # first empty slot
  } else {
    length(cost_queue) + 25L # expand list if no empty slos
  }
}

# assuming checking the whole vector is quicker than growing and
# shrinking by popping and inserting elements
which_min_cost <- function(cost_queue) {
  costs <- vapply(
    cost_queue,
    \(x) if (!is.null(x)) x[[3L]] else Inf,
    numeric(1L)
  )

  which.min(costs)
}

add_pos <- function(cost_queue, free_ptr, pos, facing, cost, increase) {
  if (increase == 1L) {
    new_pos <- pos + dirs[[facing]]
  } else {
    new_pos <- pos # when we rotate without changing coordinates
  }

  # if it's a dead end, discard this path
  if (maze[new_pos] == "#") {
    return(cost_queue)
  }

  new_cost <- cost + increase

  # if we've already go to the same pos and facing with less cost,
  # let's discard this path
  if (visited[new_pos[[1L]], new_pos[[2L]], facing] < new_cost) {
    return(cost_queue)
  }


  visited[new_pos[[1L]], new_pos[[2L]], facing] <<- new_cost
  cost_queue[free_ptr] <- list(c(list(new_pos), facing, new_cost))

  cost_queue
}

aoc_source(day = 16, part = 1)

input = aoc_read(day = 16)

aoc_run(solve_day16_part1(input))

Elapsed: 633.98 seconds
Memory:  17395460 KB