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 for edge in [candidates[0].0, candidates.last().unwrap().0] {
128 if edge != marker {
129 finite[edge] = false;
130 }
131 }
132
133 // Only consider finite coordinates.
134 for &[(_, m0, x0), (i, m1, x1), (_, m2, x2)] in candidates.array_windows() {
135 // Skip coordinates where all points are equally distant from their neighbor.
136 if i != marker {
137 if row == input.min_y || row == input.max_y {
138 // All coordinates that are closest to the top or bottom row are infinite.
139 finite[i] = false;
140 } else {
141 // Count points closest to the left, to the right and the coordinate itself.
142 let left = (x1 - x0 + m0 - m1 - 1) / 2;
143 let right = (x2 - x1 + m2 - m1 - 1) / 2;
144 area[i] += left + 1 + right;
145 }
146 }
147 }
148
149 candidates.clear();
150 }
151
152 // Find largest area closest to finite coordinate.
153 area.iter().zip(&finite).filter_map(|(&a, &f)| f.then_some(a)).max().unwrap()
154}
155
156pub fn part2(input: &Input) -> i32 {
157 part2_testable(input, 10_000)
158}
159
160/// Sweep from top to bottom to find the size of the roughly circular area that is less than
161/// a specified maximum distance from all other points.
162///
163/// Finding the center of this circle to act as a starting point is an interesting sub-problem.
164/// The two-dimensional [geometric median](https://en.wikipedia.org/wiki/Geometric_median) that
165/// minimizes the Euclidean distance to all other points has no general closed form formula.
166/// The [centroid](https://en.wikipedia.org/wiki/Centroid) is close but not exact as it minimizes
167/// the distance *squared*.
168///
169/// However, the Manhattan distance is independent for each axis, so we can instead solve for the
170/// one-dimensional case. This is the [median](https://en.wikipedia.org/wiki/Median) of each axis.
171/// Intuitively this makes sense, as the median has the same number of points on either side,
172/// so moving either direction, the increase from half the points is cancelled out by the decrease
173/// of the other half of the points.
174///
175/// The algorithm is:
176/// * Find center.
177/// * Go upwards from center until top edge of circle reached.
178/// * For each row of circle, find left and right extents.
179/// * Add area of row to total, then advance to row below.
180pub fn part2_testable(input: &Input, max_distance: i32) -> i32 {
181 // Sort points in ascending order in order to find median.
182 let mut xs: Vec<_> = input.points.iter().map(|p| p.x).collect();
183 xs.sort_unstable();
184
185 let mut ys: Vec<_> = input.points.iter().map(|p| p.y).collect();
186 ys.sort_unstable();
187
188 // Find coordinate closest to median point.
189 let x = xs[xs.len() / 2];
190 let mut y = ys[ys.len() / 2];
191
192 // Calculate minimum distance.
193 let median = Point::new(x, y);
194 let mut y_distance: i32 = input.points.iter().map(|o| o.manhattan(median)).sum();
195
196 // Find top of region.
197 while y_distance + prev(&ys, y) < max_distance {
198 y_distance += prev(&ys, y);
199 y -= 1;
200 }
201
202 let mut left = x;
203 let mut left_dist = y_distance;
204 let mut right = x;
205 let mut right_dist = y_distance;
206 let mut area = 0;
207
208 // Sweep top to bottom.
209 while y_distance < max_distance {
210 // Expand moving left edge to the left.
211 while left_dist < max_distance {
212 left_dist += prev(&xs, left);
213 left -= 1;
214 }
215 // Contract moving left edge to the right.
216 while left_dist >= max_distance {
217 left_dist += next(&xs, left);
218 left += 1;
219 }
220 // Expand moving right edge to the right.
221 while right_dist < max_distance {
222 right_dist += next(&xs, right);
223 right += 1;
224 }
225 // Contract moving right edge to the left.
226 while right_dist >= max_distance {
227 right_dist += prev(&xs, right);
228 right -= 1;
229 }
230
231 // Move downwards one row.
232 let next = next(&ys, y);
233 y_distance += next;
234 left_dist += next;
235 right_dist += next;
236
237 y += 1;
238 area += right - left + 1;
239 }
240
241 area
242}
243
244/// Calculate the change in distance moving left or up.
245/// The slice is sorted so we can use binary search instead of a linear scan.
246fn prev(slice: &[i32], n: i32) -> i32 {
247 let below = slice.partition_point(|&s| s < n) as i32;
248 slice.len() as i32 - 2 * below
249}
250
251/// Calculate the change in distance moving down or right.
252/// The slice is sorted so we can use binary search instead of a linear scan.
253fn next(slice: &[i32], n: i32) -> i32 {
254 let at_or_below = slice.partition_point(|&s| s <= n) as i32;
255 2 * at_or_below - slice.len() as i32
256}