advent_of_code_2025

day09.R (4543B)

---

 #!/usr/bin/env Rscript
 
 source("src/utils.R")
 
 test_input <- c(
   "7,1",
   "11,1",
   "11,7",
   "9,7",
   "9,5",
   "2,5",
   "2,3",
   "7,3"
 )
 puzzle_input <- aoc_input(9)
 
 parse_input <- function(input_lines) {
   input_lines |>
     strsplit(",") |>
     lapply(as.numeric) |>
     (\(x) do.call(rbind, x))()
 }
 
 tabulate_edges <- function(input_points) {
   edge_info <- list(
     tab = utils::hashtab("identical", nrow(input_points)),
     ind = rep(NA_real_, nrow(input_points))
   )
   for (p1 in seq_len(nrow(input_points))) {
     p2 <- (p1 %% nrow(input_points)) + 1
     l_h <- input_points[p1, 2]
     if (l_h == input_points[p2, 2]) {
       edge_info$ind[length(edge_info$ind) + 1] <- l_h
       utils::sethash(
         edge_info$tab,
         l_h,
         c(
           list(c(input_points[p1, 1], input_points[p2, 1])),
           utils::gethash(edge_info$tab, l_h, list())
         )
       )
     }
   }
   edge_info$ind <- unique(sort(edge_info$ind[!is.na(edge_info$ind)]))
   edge_info
 }
 
 # Part 1 =====================================================================
 
 measure_rect <- function(p1, p2) {
   (abs(p1[1] - p2[1]) + 1) * (abs(p1[2] - p2[2]) + 1)
 }
 
 find_max_rect <- function(edge_info) {
   max_rectangle <- NULL
   for (sl in seq_along(edge_info$ind)) {
     for (sl2 in sl:length(edge_info$ind)) {
       for (p1 in range(unlist(edge_info$tab[[edge_info$ind[sl]]]))) {
         for (p2 in range(unlist(edge_info$tab[[edge_info$ind[sl2]]]))) {
           max_rectangle <- max(
             max_rectangle,
             measure_rect(
               c(p1, edge_info$ind[sl]),
               c(p2, edge_info$ind[sl2])
             )
           )
         }
       }
     }
   }
   max_rectangle
 }
 
 part1 <- function(input_lines) {
   input_lines |>
     parse_input() |>
     tabulate_edges() |>
     find_max_rect()
 }
 
 test_part1 <- function() {
   stopifnot(part1(test_input) == 50)
 }
 
 # Part 2 =====================================================================
 
 edge_inside <- function(e1, e2) {
   min(e2) < max(e1) && max(e2) > min(e1)
 }
 
 remove_edge <- function(e1, e2) {
   if (max(e2) >= max(e1)) {
     if (min(e2) <= min(e1)) {
       NULL
     } else {
       list(c(min(e1), min(e2)))
     }
   } else if (min(e2) <= min(e1)) {
     list(c(max(e2), max(e1)))
   } else {
     list(c(min(e1), min(e2)), c(max(e2), max(e1)))
   }
 }
 
 add_or_remove_edge <- function(edge_front, edge, can_add = TRUE) {
   for (i in seq_along(edge_front)) {
     if (edge_inside(edge_front[[i]], edge)) {
       return(c(
         edge_front[-i],
         remove_edge(edge_front[[i]], edge)
       ))
     }
   }
   if (can_add) {
     edge_front <- c(edge_front, list(edge))
     edge_front <- edge_front[order(vapply(edge_front, \(x) x[1], numeric(1)))]
     i <- 1
     repeat {
       if (i >= length(edge_front)) break
       if (max(edge_front[[i]]) == min(edge_front[[i + 1]])) {
         edge_front[[i]] <- c(min(edge_front[[i]]), max(edge_front[[i + 1]]))
         edge_front[[i + 1]] <- NULL
       } else {
         i <- i + 1
       }
     }
   }
   edge_front
 }
 
 points_in_edge_front <- function(edge_front, p) {
   points_in_edge <- function(edge) {
     min(p) >= min(edge) && max(p) <= max(edge)
   }
   any(vapply(edge_front, points_in_edge, logical(1)))
 }
 
 sweep_edge_front <- function(edge_info) {
   max_rectangle <- NULL
   start_front <- list()
   for (y1_idx in 1:(length(edge_info$ind) - 1)) {
     y1 <- edge_info$ind[y1_idx]
     start_edges <- edge_info$tab[[y1]]
     start_front <- Reduce(add_or_remove_edge, start_edges, start_front)
     end_front <- start_front
     for (x1 in unlist(start_edges)) {
       for (y2_idx in (y1_idx + 1):length(edge_info$ind)) {
         y2 <- edge_info$ind[y2_idx]
         end_edges <- edge_info$tab[[y2]]
         for (x2 in unlist(end_edges)) {
           if (points_in_edge_front(start_front, c(x1, x2)) &&
             points_in_edge_front(end_front, c(x1, x2))) {
             max_rectangle <- max(
               max_rectangle,
               measure_rect(c(y1, x1), c(y2, x2))
             )
           }
         }
         end_front <- Reduce(\(x, y) add_or_remove_edge(x, y, FALSE), end_edges, end_front)
         if (!points_in_edge_front(end_front, x1)) break
       }
     }
   }
   max_rectangle
 }
 
 part2 <- function(input_lines) {
   input_lines |>
     parse_input() |>
     tabulate_edges() |>
     sweep_edge_front()
 }
 
 test_part2 <- function() {
   stopifnot(part2(test_input) == 24)
 }
 
 main <- function() {
   test_part1()
   cat("Part 1 solution: ", part1(puzzle_input), "\n")
   test_part2()
   cat("Part 2 solution: ", part2(puzzle_input), "\n")
 }
 
 main()