year2018/
day06.rs

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

year2018/
day06.rs
