year2025/
day09.rs

1use utils::geometry::Vec2;
2use utils::prelude::*;
3
4/// Finding the largest rectangle inside a polygon.
5#[derive(Clone, Debug)]
6pub struct Day09 {
7    part1: u64,
8    part2: u64,
9}
10
11impl Day09 {
12    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
13        let points = parser::u32()
14            .repeat_n(b',')
15            .map(Vec2::from)
16            .parse_lines(input)?;
17
18        if points.len() < 4 {
19            return Err(InputError::new(input, 0, "expected at least 4 points"));
20        }
21
22        for (p1, p2) in points.iter().zip(points.iter().cycle().skip(1)) {
23            if p1.x != p2.x && p1.y != p2.y {
24                return Err(InputError::new(
25                    input,
26                    0,
27                    "expected points to form horizontal or vertical lines",
28                ));
29            }
30        }
31
32        // Compress coordinates to reduce grid size
33        let mut xs: Vec<u32> = points.iter().map(|p| p.x).collect();
34        xs.sort_unstable();
35        xs.dedup();
36        let mut ys: Vec<u32> = points.iter().map(|p| p.y).collect();
37        ys.sort_unstable();
38        ys.dedup();
39        let points_compressed = points
40            .iter()
41            .map(|p| {
42                Vec2::new(
43                    xs.binary_search(&p.x).unwrap(),
44                    ys.binary_search(&p.y).unwrap(),
45                )
46            })
47            .collect::<Vec<_>>();
48
49        // Compressed vertical edges, sorted by x coordinate
50        let mut vertical_edges = points_compressed
51            .iter()
52            .zip(points_compressed.iter().cycle().skip(1))
53            .filter(|(a, b)| a.x == b.x && a.y != b.y)
54            .map(|(a, b)| (a.x, a.y.min(b.y), a.y.max(b.y)))
55            .collect::<Vec<_>>();
56        vertical_edges.sort_unstable_by_key(|&(x, _, _)| x);
57
58        // Compressed point inside polygon grid, each cell (x, y) representing whether the region
59        // (xs[x], ys[y]) to (xs[x+1], ys[y+1]) is inside the polygon.
60        let inside_width = xs.len() - 1;
61        let inside_height = ys.len() - 1;
62        let mut inside_grid = vec![false; inside_width * inside_height];
63        for y in 0..inside_height {
64            let mut inside = false;
65            let mut last_x = 0;
66            for &(x, y1, y2) in vertical_edges.iter() {
67                if y < y1 || y >= y2 {
68                    continue;
69                }
70
71                if inside {
72                    inside_grid[y * inside_width + last_x..y * inside_width + x].fill(inside);
73                }
74
75                inside = !inside;
76                last_x = x;
77            }
78        }
79
80        // Prefix sum grid to quickly count how many cells within a rectangle are inside the polygon
81        let prefix_width = inside_width + 1;
82        let prefix_height = inside_height + 1;
83        let mut prefix_grid = vec![0u32; prefix_width * prefix_height];
84        for y in 0..inside_height {
85            let mut row_sum = 0u32;
86            for x in 0..inside_width {
87                row_sum += u32::from(inside_grid[y * inside_width + x]);
88                prefix_grid[(y + 1) * prefix_width + (x + 1)] =
89                    prefix_grid[y * prefix_width + (x + 1)] + row_sum;
90            }
91        }
92
93        let (mut part1, mut part2) = (0, 0);
94        for i in 0..points.len() {
95            let x1 = points[i].x;
96            let x1_compressed = points_compressed[i].x;
97            let y1 = points[i].y;
98            let y1_compressed = points_compressed[i].y;
99
100            for j in (i + 1)..points.len() {
101                let dx = x1.abs_diff(points[j].x) as u64 + 1;
102                let dy = y1.abs_diff(points[j].y) as u64 + 1;
103                let area = dx * dy;
104                part1 = part1.max(area);
105
106                if area <= part2 {
107                    continue;
108                }
109
110                let x2_compressed = points_compressed[j].x;
111                let y2_compressed = points_compressed[j].y;
112
113                let x_min_compressed = x1_compressed.min(x2_compressed);
114                let x_max_compressed = x1_compressed.max(x2_compressed);
115                let y_min_compressed = y1_compressed.min(y2_compressed);
116                let y_max_compressed = y1_compressed.max(y2_compressed);
117
118                let inside_cells = prefix_grid[y_max_compressed * prefix_width + x_max_compressed]
119                    + prefix_grid[y_min_compressed * prefix_width + x_min_compressed]
120                    - prefix_grid[y_min_compressed * prefix_width + x_max_compressed]
121                    - prefix_grid[y_max_compressed * prefix_width + x_min_compressed];
122
123                let width_compressed = x_max_compressed - x_min_compressed;
124                let height_compressed = y_max_compressed - y_min_compressed;
125                let total_cells = (width_compressed * height_compressed) as u32;
126
127                if inside_cells != total_cells {
128                    continue;
129                }
130
131                part2 = area;
132            }
133        }
134
135        Ok(Self { part1, part2 })
136    }
137
138    #[must_use]
139    pub fn part1(&self) -> u64 {
140        self.part1
141    }
142
143    #[must_use]
144    pub fn part2(&self) -> u64 {
145        self.part2
146    }
147}
148
149examples!(Day09 -> (u64, u64) [
150    {input: "7,1\n11,1\n11,7\n9,7\n9,5\n2,5\n2,3\n7,3", part1: 50, part2: 24},
151]);
year2025/day09.rs

year2025/
day09.rs
