commit bcbc8279488f62e0eea4b986d5d59b6b5947d4f5
parent d733b17cc2fbb9b7109d8bced04696748fa3a242
Author: Eamon Caddigan <ec@eamoncaddigan.net>
Date: Tue, 9 Dec 2025 14:31:27 -0800
Solve day 09, part 1
Diffstat:
| A | src/day09.R | | | 104 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 104 insertions(+), 0 deletions(-)
diff --git a/src/day09.R b/src/day09.R
@@ -0,0 +1,104 @@
+#!/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))()
+}
+
+point_lt <- function(p1, p2) {
+ p1[2] < p2[2] || p1[2] == p2[2] && p1[1] < p1[1]
+}
+
+# Hacked together implementation of Graham Scan
+# Not worrying about efficient stack implementation; R's lists should suffice I
+# hope
+# Note: not robust to real-world input
+convex_hull <- function(points) {
+ find_p0 <- function(points) {
+ min_point_idx <- 1
+ for (i in 2:nrow(points)) {
+ if (point_lt(points[i, ], points[min_point_idx, ])) {
+ min_point_idx <- i
+ }
+ }
+ min_point_idx
+ }
+
+ right_turn <- function(p1, p2, p3) {
+ (p2[1] - p1[1]) * (p3[2] - p1[2]) - (p2[2] - p1[2]) * (p3[1] - p1[1]) < 0
+ }
+
+ sort_points <- function(points) {
+ p0 <- find_p0(points)
+ slope <- (points[-p0, 1] - points[p0, 1]) / (points[-p0, 2] - points[p0, 2])
+ rbind(
+ points[p0, ],
+ (points[-p0, ])[order(slope, decreasing = TRUE), ]
+ )
+ }
+
+ points_sorted <- sort_points(points)
+ hull_list <- list()
+ for (i in seq_len(nrow(points_sorted))) {
+ while (length(hull_list) > 2 && right_turn(
+ hull_list[[length(hull_list) - 1]],
+ hull_list[[length(hull_list)]],
+ points_sorted[i, ]
+ )) {
+ hull_list[[length(hull_list)]] <- NULL
+ }
+ hull_list[[length(hull_list) + 1]] <- points_sorted[i, ]
+ }
+ do.call(rbind, hull_list)
+}
+
+measure_square <- function(p1, p2) {
+ (abs(p1[1] - p2[1]) + 1) * (abs(p1[2] - p2[2]) + 1)
+}
+
+largest_square_on_hull <- function(points) {
+ hull <- convex_hull(points)
+ largest_square <- NULL
+ for (i in 1:(nrow(hull) - 1)) {
+ for (j in 2:nrow(hull)) {
+ largest_square <- max(
+ largest_square,
+ measure_square(hull[i, ], hull[j, ])
+ )
+ }
+ }
+ largest_square
+}
+
+part1 <- function(input_lines) {
+ input_lines |>
+ parse_input() |>
+ largest_square_on_hull()
+}
+
+test_part1 <- function() {
+ stopifnot(part1(test_input) == 50)
+}
+
+main <- function() {
+ test_part1()
+ cat("Part 1 solution: ", part1(puzzle_input), "\n")
+}
+
+main()
