aoc/year2025/
day09.rs

1//! # Movie Theater
2use crate::util::iter::*;
3use crate::util::parse::*;
4
5type Tile = [u64; 2];
6
7struct Candidate {
8    x: u64,
9    y: u64,
10    interval: Interval,
11}
12
13/// The set { x in u64 | l <= x <= r }.
14#[derive(Clone, Copy)]
15struct Interval {
16    l: u64,
17    r: u64,
18}
19
20impl Interval {
21    fn new(l: u64, r: u64) -> Self {
22        debug_assert!(l <= r);
23
24        Interval { l, r }
25    }
26
27    fn intersects(self, other: Self) -> bool {
28        other.l <= self.r && self.l <= other.r
29    }
30
31    fn intersection(self, other: Self) -> Self {
32        debug_assert!(self.intersects(other));
33
34        Interval::new(self.l.max(other.l), self.r.min(other.r))
35    }
36
37    fn contains(self, x: u64) -> bool {
38        self.l <= x && x <= self.r
39    }
40}
41
42pub fn parse(input: &str) -> Vec<Tile> {
43    input.iter_unsigned::<u64>().chunk::<2>().collect()
44}
45
46pub fn part1(tiles: &[Tile]) -> u64 {
47    let mut area = 0;
48
49    for (i, &[x1, y1]) in tiles.iter().enumerate() {
50        for &[x2, y2] in tiles.iter().skip(i + 1) {
51            let dx = x1.abs_diff(x2) + 1;
52            let dy = y1.abs_diff(y2) + 1;
53            area = area.max(dx * dy);
54        }
55    }
56
57    area
58}
59
60pub fn part2(tiles: &[Tile]) -> u64 {
61    let mut tiles = tiles.to_vec();
62
63    tiles.sort_unstable_by_key(|&[x, y]| (y, x));
64
65    let tiles = tiles;
66
67    // Track the largest area so far during scanning:
68    let mut largest_area: u64 = 0;
69
70    // Each red tile (`x`, `y`) becomes a candidate for being a top corner of the largest area, and during the
71    // scan the `interval` containing the maximum possible width is updated:
72    let mut candidates: Vec<Candidate> = Vec::with_capacity(512);
73
74    // Maintain an ordered list of descending edges, i.e. [begin_interval_0, end_interval_0, begin_interval_1, end_interval_1, ...]:
75    let mut descending_edges: Vec<u64> = vec![];
76    let mut intervals_from_descending_edges = vec![];
77
78    // Invariants on the input data (defined by the puzzle) result in points arriving in pairs on the same y line:
79    let mut it = tiles.into_iter();
80
81    while let (Some([x0, y]), Some([x1, y1])) = (it.next(), it.next()) {
82        debug_assert_eq!(y, y1);
83
84        // Update the descending edges; since we are scanning from top to bottom, and within each line left to right,
85        // when we, starting from outside of the region, hit a corner tile it is either:
86        //
87        // - The corner of two edges, one going right and one going down. In this case, the `descending_edges` won't contain
88        //   the `x` coordinate, and we should "toggle" it on to denote that there is a new descending edge.
89        // - The corner of two edges, one going right and one going up. The `descending_edges` will contain an `x` coordinate,
90        //   that should be "toggled" off.
91        //
92        // Simular arguments work for when we are scanning inside the edge and we hit the corner that ends the edge; this is also
93        // why corners always arrive in pairs.
94        //
95        // Do the update:
96        for x in [x0, x1] {
97            toggle_value_membership_in_ordered_list(&mut descending_edges, x);
98        }
99
100        // Every pair of descending edges in the ordered list defines a region; find the resulting intervals on this line:
101        update_intervals_from_descending_edges(
102            &descending_edges,
103            &mut intervals_from_descending_edges,
104        );
105
106        // Check the rectangles this red tile could be a bottom tile for, with the current candidates:
107        for candidate in &candidates {
108            for x in [x0, x1] {
109                if candidate.interval.contains(x) {
110                    largest_area = largest_area
111                        .max((candidate.x.abs_diff(x) + 1) * (candidate.y.abs_diff(y) + 1));
112                }
113            }
114        }
115
116        // Update candidates when their interval shrinks due to descending edge changes, and drop them when their interval becomes empty:
117        candidates.retain_mut(|candidate| {
118            if let Some(intersection_containing_x) =
119                intervals_from_descending_edges.iter().find(|i| i.contains(candidate.x))
120            {
121                candidate.interval = intersection_containing_x.intersection(candidate.interval);
122
123                true
124            } else {
125                false
126            }
127        });
128
129        // Add any new candidates:
130        for x in [x0, x1] {
131            if let Some(&containing) =
132                intervals_from_descending_edges.iter().find(|i| i.contains(x))
133            {
134                candidates.push(Candidate { x, y, interval: containing });
135            }
136        }
137    }
138
139    largest_area
140}
141
142// Adds `value` if it isn't in `ordered_list`, removes it if it is, maintaining the order.
143fn toggle_value_membership_in_ordered_list(ordered_list: &mut Vec<u64>, value: u64) {
144    let mut i = 0;
145
146    while i < ordered_list.len() && ordered_list[i] < value {
147        i += 1;
148    }
149
150    if i == ordered_list.len() || ordered_list[i] != value {
151        ordered_list.insert(i, value);
152    } else {
153        ordered_list.remove(i);
154    }
155}
156
157// Changes the list of descending edges, [begin_interval_0, end_interval_0, begin_interval_1, end_interval_1, ...],
158// into a vector containing the intervals.
159#[inline]
160fn update_intervals_from_descending_edges(descending_edges: &[u64], to_update: &mut Vec<Interval>) {
161    debug_assert!(descending_edges.len().is_multiple_of(2));
162
163    to_update.clear();
164
165    let mut it = descending_edges.iter();
166
167    while let (Some(&l), Some(&r)) = (it.next(), it.next()) {
168        to_update.push(Interval::new(l, r));
169    }
170}
aoc/year2025/day09.rs

aoc/year2025/
day09.rs
