2025

Day 1 Day 2 Day 3 Day 4

A happy little grid puzzle :)

My initial approach was quite slow to run, so for part 2 I tried to cut down the search space by only checking rolls that had neighbours removed. After a bit of a convoluted refactor of my R part 2 solution I finally down to <0.2s which is good enough for me.

One improvement was implementing a clunky queue in a matrix because I like seeing array indices, using start and end pointers. Another big improvement was going from searching in 8 directions from each position to find roll counts, to essentially shifting the whole grid 8 times and using vectorised addition.

I then slapped together a fully brute force Python solution and it runs in <1s, sigh. Still, I was happy with my original time-to-solution.

— R Day 4 Part 1 —

solve_day4_part1 <- function(input) {
  grid <- aoc_input_to_chr_matrix(input)
  nrows <- NROW(grid)
  ncols <- NCOL(grid)
  liftable <- matrix(FALSE, nrows, ncols)

  for (row in seq_len(nrows)) {
    for (col in seq_len(ncols)) {
      liftable[row, col] <- is_liftable(grid, row, col, nrows, ncols)
    }
  }

  sum(liftable)
}

is_liftable <- function(grid, row, col, nrows, ncols) {
  char <- grid[row, col]
  pos <- matrix(c(row, col), nrow = 1)

  if (char != "@") {
    return(FALSE)
  }

  dir_list <- aoc_2D_dirs()
  roll_count <- 0L

  for (dir in dir_list) {
    search_pos <- pos + dir
    if (aoc_2D_out_of_bounds(search_pos, nrows, ncols)) next

    if (grid[search_pos] == "@") {
      roll_count <- roll_count + 1L
    }
  }

  roll_count < 4L
}
Run
aoc_source(day = 4, part = 1)

input = aoc_read(day = 4)

aoc_run(solve_day4_part1(input))
Elapsed: 0.267 seconds
Memory:  1066 KB

— R Day 4 Part 2 —

solve_day4_part2 <- function(input) {
  grid  <- aoc_input_to_chr_matrix(input)
  nrows <- NROW(grid)
  ncols <- NCOL(grid)
  dir_list <- aoc_2D_dirs()

  surrounding <- count_surrounding(grid, dir_list, nrows, ncols)

  max_queue <- 5e4L
  remove_queue <- matrix(NA_real_, nrow = max_queue, ncol = 2L)

  first_removals <- which(surrounding < 4, arr.ind = TRUE)

  queue_start <- 1L
  queue_end   <- NROW(first_removals)
  remove_queue[queue_start:queue_end, ] <- first_removals

  total_removed <- 0L

  while (queue_start <= queue_end) {
    pos <- matrix(remove_queue[queue_start, ], nrow = 1)
    queue_start <- queue_start + 1L

    if (!is.finite(surrounding[pos])) next

    # remove roll
    total_removed <- total_removed + 1L
    surrounding[pos] <- Inf

    # update neighbours and check if they should be removed
    for (dir in dir_list) {
      change_pos <- pos + dir
      if (aoc_2D_out_of_bounds(change_pos, nrows, ncols)) next

      val <- surrounding[change_pos]
      if (!is.finite(val)) next

      surrounding[change_pos] <- val - 1

      # they should be removed if going from 4 to 3 neighbouring rolls
      if (val == 4L) {
        queue_end <- queue_end + 1L
        remove_queue[queue_end, ] <- change_pos
      }
    }
  }

  total_removed
}

#' Where previously I was checking in 8 directions from each position,
#' this version shifts the whole grid in each direction,
#' so it can do a vectorised addition to count
count_surrounding <- function(grid, dir_list, nrows, ncols) {
  surrounding <- matrix(0L, nrows, ncols)

  is_roll <- grid == "@"

  for (dir in dir_list) {
    row_adj <- dir[1L]
    col_adj <- dir[2L]

    # in bounds sequence of positions to check for rolls
    check_rows <- seq(max(1, 1 - row_adj), min(nrows, nrows - row_adj))
    check_cols <- seq(max(1, 1 - col_adj), min(ncols, ncols - col_adj))

    # positions to update count for
    dest_rows <- check_rows + row_adj
    dest_cols <- check_cols + col_adj

    surrounding[dest_rows, dest_cols] <- surrounding[dest_rows, dest_cols] +
      is_roll[check_rows, check_cols]
  }

  surrounding[!is_roll] <- Inf

  surrounding
}
Run
aoc_source(day = 4, part = 2)

input = aoc_read(day = 4)

aoc_run(solve_day4_part2(input))
Elapsed: 0.151 seconds
Memory:  3882 KB

— Python Day 4 Part 1 —

def solve_day4_part1(text):
    nrows = len(text)
    ncols = len(text[0])
    liftable_count = 0

    for row in range(nrows):
        for col in range(ncols):
            if is_liftable(text, row, col, nrows, ncols):
                liftable_count += 1

    return(liftable_count)

def is_liftable(grid, row, col, nrows, ncols):
    char = grid[row][col]
    roll_count = 0

    if char != "@":
        return(False)

    for row_adj in range(-1, 2):
        search_row = row + row_adj
        if search_row < 0 or search_row >= nrows:
            continue

        for col_adj in range(-1, 2):
            search_col = col + col_adj

            if search_col < 0 or search_col >= ncols:
                continue
            if row == search_row and col == search_col:
                continue

            if grid[search_row][search_col] == "@":
                roll_count += 1

    return(roll_count < 4)
Run
aoc_source(day = 4, part = 1)

input = aoc_read(day = 4)

result = aoc_run("solve_day4_part1(input)")
Elapsed: 0.053 seconds
Memory:  12 KB

— Python Day 4 Part 2 —

def solve_day4_part2(text):
    grid = [list(row) for row in text]
    nrows = len(grid)
    ncols = len(grid[0])
    removed_count = 0
    removing_rolls = True

    while removing_rolls:
        removing_rolls = False
        for row in range(nrows):
            for col in range(ncols):
                if grid[row][col] != "@":
                    continue

                neighbours = 0
                for row_adj in range(-1, 2):
                    search_row = row + row_adj

                    if search_row < 0 or search_row >= nrows:
                        continue

                    for col_adj in range(-1, 2):
                        search_col = col + col_adj
                        if search_col < 0 or search_col >= ncols:
                            continue
                        if row == search_row and col == search_col:
                            continue

                        if grid[search_row][search_col] == "@":
                            neighbours += 1

                if neighbours < 4:
                    removing_rolls = True
                    removed_count += 1
                    grid[row][col] = "."

    return(removed_count)
Run
aoc_source(day = 4, part = 2)

input = aoc_read(day = 4)

result = aoc_run("solve_day4_part2(input)")
Elapsed: 0.781 seconds
Memory:  169 KB
Back to top