year2018/
day06.rs

1use utils::point::Point2D;
2use utils::prelude::*;
3
4/// Measuring regions using Manhattan distance.
5#[derive(Clone, Debug)]
6pub struct Day06 {
7    locations: Vec<Point2D<usize>>,
8    region_threshold: u32,
9}
10
11const WIDTH: usize = 320;
12
13impl Day06 {
14    pub fn new(input: &str, input_type: InputType) -> Result<Self, InputError> {
15        let locations = parser::number_range(0..=999)
16            .repeat_n(", ")
17            .map(Point2D::from)
18            .parse_lines(input)?;
19        if locations.is_empty() {
20            return Err(InputError::new(input, 0, "expected at least one location"));
21        }
22        if locations.len() >= u8::MAX as usize {
23            return Err(InputError::new(input, 0, "too many locations"));
24        }
25
26        let min = locations.iter().map(|p| p.x.min(p.y)).min().unwrap();
27        let max = locations.iter().map(|p| p.x.max(p.y)).max().unwrap();
28        if max - min >= WIDTH {
29            return Err(InputError::new(input, 0, "coordinate range too large"));
30        }
31
32        let min_point = Point2D::new(min, min);
33        Ok(Self {
34            locations: locations.into_iter().map(|p| p - min_point).collect(),
35            region_threshold: match input_type {
36                InputType::Example => 32,
37                InputType::Real => 10000,
38            },
39        })
40    }
41
42    #[must_use]
43    pub fn part1(&self) -> u32 {
44        let mut distances = [0u16; WIDTH * WIDTH];
45        let mut closest = [0u8; WIDTH * WIDTH];
46
47        for (i, location) in self.locations.iter().enumerate() {
48            // Distances are stored inverted so the array can start zeroed
49            distances[location.y * WIDTH + location.x] = u16::MAX;
50            closest[location.y * WIDTH + location.x] = 1 + i as u8;
51        }
52
53        // Right
54        for y in 0..WIDTH {
55            Self::chunk(
56                &mut distances,
57                &mut closest,
58                (y * WIDTH)..(y * WIDTH) + (WIDTH - 1),
59                1,
60            );
61        }
62        // Down
63        Self::chunk(&mut distances, &mut closest, 0..WIDTH * (WIDTH - 1), WIDTH);
64
65        // Left
66        for y in (0..WIDTH).rev() {
67            Self::chunk(
68                &mut distances,
69                &mut closest,
70                ((y * WIDTH) + 1..(y * WIDTH) + WIDTH).rev(),
71                1usize.wrapping_neg(),
72            );
73        }
74        // Up
75        Self::chunk(
76            &mut distances,
77            &mut closest,
78            (WIDTH..WIDTH * WIDTH).rev(),
79            WIDTH.wrapping_neg(),
80        );
81
82        let mut finite = vec![true; self.locations.len() + 1];
83        finite[0] = false;
84        for i in 0..WIDTH {
85            finite[closest[i] as usize] = false;
86            finite[closest[WIDTH * (WIDTH - 1) + i] as usize] = false;
87            finite[closest[WIDTH * i] as usize] = false;
88            finite[closest[WIDTH * i + WIDTH - 1] as usize] = false;
89        }
90
91        let mut counts = vec![0; self.locations.len() + 1];
92        for &c in closest.iter() {
93            counts[c as usize] += 1;
94        }
95
96        counts
97            .iter()
98            .zip(finite.iter())
99            .filter(|&(_, &i)| i)
100            .map(|(&c, _)| c)
101            .max()
102            .unwrap()
103    }
104
105    #[inline]
106    fn chunk(
107        distances: &mut [u16],
108        closest: &mut [u8],
109        coords: impl Iterator<Item = usize>,
110        offset: usize,
111    ) {
112        for from in coords {
113            let to = from.wrapping_add(offset);
114            let dist = distances[from].saturating_sub(1);
115            if dist > distances[to] {
116                distances[to] = dist;
117                closest[to] = closest[from];
118            } else if dist == distances[to] && closest[to] != closest[from] {
119                closest[to] = 0;
120            }
121        }
122    }
123
124    #[must_use]
125    pub fn part2(&self) -> u32 {
126        let mut x_distances = [0u32; WIDTH];
127        let mut y_distances = [0u32; WIDTH];
128        for location in &self.locations {
129            for i in 0..WIDTH {
130                x_distances[i] += location.x.abs_diff(i) as u32;
131                y_distances[i] += location.y.abs_diff(i) as u32;
132            }
133        }
134
135        let mut region = 0;
136        for y_dist in y_distances {
137            region += x_distances
138                .iter()
139                .map(|&x| x + y_dist)
140                .filter(|&x| x < self.region_threshold)
141                .count() as u32;
142        }
143        region
144    }
145}
146
147examples!(Day06 -> (u32, u32) [
148    {input: "1, 1\n1, 6\n8, 3\n3, 4\n5, 5\n8, 9", part1: 17, part2: 16},
149]);
year2018/day06.rs

year2018/
day06.rs
