aoc/year2018/day06.rs
1//! # Chronal Coordinates
2//!
3//! Both parts can be solved with a [BFS](https://en.wikipedia.org/wiki/Breadth-first_search)
4//! approach. The bounding box of the coordinates is roughly 300 wide by 300 high so the total
5//! complexity would be approximately `O(90,000)`.
6//!
7//! A much faster approach for both parts is a
8//! [sweep line algorithm](https://en.wikipedia.org/wiki/Sweep_line_algorithm). We sweep from
9//! top to bottom (minimum y coordinate to maximum y coordinate) computing the area a slice at a
10//! time. There are 50 coordinates so the complexity of this approach is much lower at
11//! approximately `O(300 * 50) = O(15000)`.
12use crate::util::iter::*;
13use crate::util::parse::*;
14use crate::util::point::*;
15
16pub struct Input {
17 min_y: i32,
18 max_y: i32,
19 points: Vec<Point>,
20}
21
22pub fn parse(input: &str) -> Input {
23 let points: Vec<_> = input.iter_signed().chunk::<2>().map(|[x, y]| Point::new(x, y)).collect();
24 let min_y = points.iter().map(|p| p.y).min().unwrap();
25 let max_y = points.iter().map(|p| p.y).max().unwrap();
26 Input { min_y, max_y, points }
27}
28
29/// Sweep line approach computing the area of each *finite* coordinate. A coordinate has infinite
30/// area if any point on the edge of the bounding box formed by the minimum and maximum x and y
31/// coordinates is closest to that coordinate.
32///
33/// We sort the coordinates in ascending x value then for each row, compare the next coordinate
34/// against the head of a stack. This quickly eliminates coordinates that are further away at all
35/// points. Interestingly, this approach is very similar to the previous [`Day 5`].
36///
37/// [`Day 5`]: crate::year2018::day05
38pub fn part1(input: &Input) -> i32 {
39 let mut points = input.points.clone();
40 let mut area = vec![0; points.len()];
41 let mut finite = vec![true; points.len()];
42 let mut candidates: Vec<(usize, i32, i32)> = Vec::new();
43
44 // Special value for coordinates that are equidistant from nearest neighbor.
45 let marker = usize::MAX;
46
47 // Sorts points left to right so that ranges can be merged.
48 points.sort_unstable_by_key(|p| p.x);
49
50 // Sweep top to bottom.
51 for row in input.min_y..=input.max_y {
52 // Left to right.
53 for (j, &p) in points.iter().enumerate() {
54 // Manhattan distance is the absolute difference in y coordinates since the x
55 // coordinate is already identical.
56 let m1 = (p.y - row).abs();
57 let x1 = p.x;
58
59 loop {
60 if let Some((i, m0, x0)) = candidates.pop() {
61 // Compare against the head of the stack.
62 let delta = m1 - m0;
63 let width = x1 - x0;
64
65 if delta < -width {
66 // Left coordinate is further away at every point.
67 // Discard and pop next left coordinate from the stack.
68 //
69 // rrrrrrrrrrrrrrrr <-- Considering only this row
70 // ....R...........
71 // ................
72 // ................
73 // ..L.............
74 continue;
75 } else if delta == -width {
76 // Left coordinate is equal from its center leftwards
77 // Replace with special marker value.
78 //
79 // ...rrrrrrrrrrrrr
80 // ....R...........
81 // ................
82 // ..L.............
83 candidates.push((marker, m0, x0));
84 candidates.push((j, m1, x1));
85 } else if delta == width {
86 // Right coordinate is equal from its center rightwards.
87 // Replace with special marker value.
88 //
89 // llll............
90 // ..L.............
91 // ................
92 // ....R...........
93 candidates.push((i, m0, x0));
94 candidates.push((marker, m1, x1));
95 } else if delta > width {
96 // Right coordinate is further away at every point.
97 // Discard then check next right coordinate from points.
98 //
99 // llllllllllllllll
100 // ..L.............
101 // ................
102 // ................
103 // ....R...........
104 candidates.push((i, m0, x0));
105 } else {
106 // Coordinates split the distance, some points closer to left and others
107 // closer to right. Add both to candidates.
108 //
109 // lllll.rrrrrrrrrr
110 // .........R......
111 // ..L.............
112 // ................
113 // ................
114 candidates.push((i, m0, x0));
115 candidates.push((j, m1, x1));
116 }
117 } else {
118 // Nothing on stack to compare with, push coordinate.
119 candidates.push((j, m1, x1));
120 }
121
122 break;
123 }
124 }
125
126 // Any coordinates that are closest to the bounding box edges are infinite.
127 let left = candidates[0].0;
128 if left != marker {
129 finite[left] = false;
130 }
131
132 let right = candidates.last().unwrap().0;
133 if right != marker {
134 finite[right] = false;
135 }
136
137 // Only consider finite coordinates.
138 for &[(_, m0, x0), (i, m1, x1), (_, m2, x2)] in candidates.array_windows() {
139 // Skip coordinates where all points are equally distant from their neighbor.
140 if i != marker {
141 if row == input.min_y || row == input.max_y {
142 // All coordinates that are closest to the top or bottom row are infinite.
143 finite[i] = false;
144 } else {
145 // Count points closest to the left, to the right and the coordinate itself.
146 let left = (x1 - x0 + m0 - m1 - 1) / 2;
147 let right = (x2 - x1 + m2 - m1 - 1) / 2;
148 area[i] += left + 1 + right;
149 }
150 }
151 }
152
153 candidates.clear();
154 }
155
156 // Find largest area closest to finite coordinate.
157 area.iter().zip(&finite).filter_map(|(&a, &f)| f.then_some(a)).max().unwrap()
158}
159
160pub fn part2(input: &Input) -> i32 {
161 part2_testable(input, 10_000)
162}
163
164/// Sweep from top to bottom to find the size of the roughly circular area that is less than
165/// a specified maximum distance from all other points.
166///
167/// Finding the center of this circle to act as a starting point is an interesting sub-problem.
168/// The two-dimensional [geometric median](https://en.wikipedia.org/wiki/Geometric_median) that
169/// minimizes the Euclidean distance to all other points has no general closed form formula.
170/// The [centroid](https://en.wikipedia.org/wiki/Centroid) is close but not exact as it minimizes
171/// the distance *squared*.
172///
173/// However, the Manhattan distance is independent for each axis, so we can instead solve for the
174/// one-dimensional case. This is the [median](https://en.wikipedia.org/wiki/Median) of each axis.
175/// Intuitively this makes sense, as the median has the same number of points on either side,
176/// so moving either direction, the increase from half the points is cancelled out by the decrease
177/// of the other half of the points.
178///
179/// The algorithm is:
180/// * Find center
181/// * Go upwards from center until top edge of circle reached.
182/// * For each row of circle, find left and right extents
183/// * Add area of row to total, then advance to row below.
184pub fn part2_testable(input: &Input, max_distance: i32) -> i32 {
185 // Sort points in ascending order in order to find median.
186 let mut xs: Vec<_> = input.points.iter().map(|p| p.x).collect();
187 xs.sort_unstable();
188
189 let mut ys: Vec<_> = input.points.iter().map(|p| p.y).collect();
190 ys.sort_unstable();
191
192 // Find coordinate closest to median point.
193 let x = xs[xs.len() / 2];
194 let mut y = ys[ys.len() / 2];
195
196 // Calculate minimum distance.
197 let median = Point::new(x, y);
198 let mut y_distance: i32 = input.points.iter().map(|o| o.manhattan(median)).sum();
199
200 // Find top of region.
201 while y_distance + prev(&ys, y) < max_distance {
202 y_distance += prev(&ys, y);
203 y -= 1;
204 }
205
206 let mut left = x;
207 let mut left_dist = y_distance;
208 let mut right = x;
209 let mut right_dist = y_distance;
210 let mut area = 0;
211
212 // Sweep top to bottom.
213 while y_distance < max_distance {
214 // Expand moving left edge to the left.
215 while left_dist < max_distance {
216 left_dist += prev(&xs, left);
217 left -= 1;
218 }
219 // Contract moving left edge to the right.
220 while left_dist >= max_distance {
221 left_dist += next(&xs, left);
222 left += 1;
223 }
224 // Expand moving right edge to the right.
225 while right_dist < max_distance {
226 right_dist += next(&xs, right);
227 right += 1;
228 }
229 // Contract moving right edge to the left.
230 while right_dist >= max_distance {
231 right_dist += prev(&xs, right);
232 right -= 1;
233 }
234
235 // Move downwards one row.
236 let next = next(&ys, y);
237 y_distance += next;
238 left_dist += next;
239 right_dist += next;
240
241 y += 1;
242 area += right - left + 1;
243 }
244
245 area
246}
247
248/// Calculate the change in distance moving left or up.
249/// The slice is sorted so we can use binary search instead of a linear scan.
250fn prev(slice: &[i32], n: i32) -> i32 {
251 let below = slice.partition_point(|&s| s < n) as i32;
252 slice.len() as i32 - 2 * below
253}
254
255/// Calculate the change in distance moving down or right.
256/// The slice is sorted so we can use binary search instead of a linear scan.
257fn next(slice: &[i32], n: i32) -> i32 {
258 let at_or_below = slice.partition_point(|&s| s <= n) as i32;
259 2 * at_or_below - slice.len() as i32
260}