year2015/
day06.rs

1use utils::prelude::*;
2
3/// Light grid.
4///
5/// Reducing the 1000x1000 grid based on the unique x and y bounds in the input gives a ~4x speedup.
6/// For example, the 1000x1000 grid for this input:
7///
8/// ```text
9/// turn on 0,0 through 999,999
10/// toggle 0,0 through 999,0
11/// turn off 499,499 through 500,500
12/// ```
13///
14/// Can be converted into this 3x4 grid:
15///
16/// ```text
17/// | 0,0   through 498,0   | 499,0   through 500,0   | 501,0   through 999,0   |
18/// | 0,1   through 498,498 | 499,1   through 500,498 | 501,1   through 999,498 |
19/// | 0,499 through 498,500 | 499,499 through 500,500 | 501,499 through 999,500 |
20/// | 0,501 through 498,999 | 499,501 through 500,999 | 501,501 through 999,999 |
21/// ```
22#[derive(Clone, Debug)]
23pub struct Day06 {
24    instructions: Vec<(Action, (u16, u16, u16, u16))>,
25    row_widths: Vec<u16>,
26    col_heights: Vec<u16>,
27}
28
29#[derive(Clone, Copy, Debug)]
30enum Action {
31    TurnOn,
32    TurnOff,
33    Toggle,
34}
35
36impl Day06 {
37    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
38        let mut instructions = parser::literal_map!(
39            "turn off " => Action::TurnOff,
40            "turn on " => Action::TurnOn,
41            "toggle " => Action::Toggle,
42        )
43        .then(parser::u16())
44        .then(parser::u16().with_prefix(b','))
45        .then(parser::u16().with_prefix(" through "))
46        .then(parser::u16().with_prefix(b','))
47        .map(|(action, x1, y1, x2, y2)| (action, (x1.min(x2), y1.min(y2), x1.max(x2), y1.max(y2))))
48        .parse_lines(input)?;
49
50        let mut x_values = Vec::with_capacity(instructions.len() * 2);
51        let mut y_values = Vec::with_capacity(instructions.len() * 2);
52        instructions.iter().for_each(|&(_, (x1, y1, x2, y2))| {
53            x_values.push(x1);
54            x_values.push(x2 + 1);
55            y_values.push(y1);
56            y_values.push(y2 + 1);
57        });
58        x_values.sort_unstable();
59        x_values.dedup();
60        y_values.sort_unstable();
61        y_values.dedup();
62
63        let row_widths: Vec<u16> = x_values.windows(2).map(|w| w[1] - w[0]).collect();
64        let col_heights: Vec<u16> = y_values.windows(2).map(|w| w[1] - w[0]).collect();
65
66        let mut x_map = [0; 1000];
67        for (i, w) in x_values.windows(2).enumerate() {
68            x_map[w[0] as usize..w[1] as usize].fill(i as u16)
69        }
70        let mut y_map = [0; 1000];
71        for (i, w) in y_values.windows(2).enumerate() {
72            y_map[w[0] as usize..w[1] as usize].fill(i as u16)
73        }
74
75        instructions.iter_mut().for_each(|(_, (x1, y1, x2, y2))| {
76            *x1 = x_map[*x1 as usize];
77            *y1 = y_map[*y1 as usize];
78            *x2 = x_map[*x2 as usize];
79            *y2 = y_map[*y2 as usize];
80        });
81
82        Ok(Self {
83            instructions,
84            row_widths,
85            col_heights,
86        })
87    }
88
89    #[must_use]
90    pub fn part1(&self) -> u32 {
91        self.total_lights(|slice, action| match action {
92            Action::TurnOn => slice.iter_mut().for_each(|v| *v = 1),
93            Action::TurnOff => slice.iter_mut().for_each(|v| *v = 0),
94            Action::Toggle => slice.iter_mut().for_each(|v| *v ^= 1),
95        })
96    }
97
98    #[must_use]
99    pub fn part2(&self) -> u32 {
100        self.total_lights(|slice, action| match action {
101            Action::TurnOn => slice.iter_mut().for_each(|v| *v += 1),
102            Action::TurnOff => slice.iter_mut().for_each(|v| *v = v.saturating_sub(1)),
103            Action::Toggle => slice.iter_mut().for_each(|v| *v += 2),
104        })
105    }
106
107    fn total_lights(&self, f: impl Fn(&mut [u8], Action)) -> u32 {
108        let width = self.row_widths.len();
109        let height = self.col_heights.len();
110        let mut grid = vec![0u8; width * height];
111
112        for &(action, (x1, y1, x2, y2)) in &self.instructions {
113            for y in y1..=y2 {
114                let index1 = (y as usize) * width + x1 as usize;
115                let index2 = (y as usize) * width + x2 as usize;
116                f(&mut grid[index1..=index2], action);
117            }
118        }
119
120        let mut total = 0;
121        for y in 0..height {
122            for x in 0..width {
123                total += grid[y * width + x] as u32
124                    * self.row_widths[x] as u32
125                    * self.col_heights[y] as u32;
126            }
127        }
128        total
129    }
130}
131
132examples!(Day06 -> (u32, u32) [
133    {
134        input: "turn on 0,0 through 999,999\n\
135            toggle 0,0 through 999,0\n\
136            turn off 499,499 through 500,500",
137        part1: 998996,
138    },
139    {
140        input: "turn on 0,0 through 0,0\n\
141            toggle 0,0 through 999,999\n",
142        part2: 2000001,
143    },
144]);
year2015/day06.rs

year2015/
day06.rs
