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