aoc/year2020/
day11.rs

1//! # Seating System
2//!
3//! Cellular automata are hard to speed up due to the need to check all neighbors each iteration.
4//! For both parts we minimize expensive memory allocation by creating only two temporary buffers
5//! then swapping between them each turn, a similar approach to double buffering.
6//!
7//! For part two we can further optimize by precalculating the locations of the nearest visible
8//! seats only once then reusing that information for each step.
9//!
10//! The SIMD version speed things up by calculating 32 lanes at a time.
11use crate::util::grid::*;
12use crate::util::point::*;
13
14const SEAT: u8 = b'L';
15
16pub fn parse(input: &str) -> Grid<u8> {
17    Grid::parse(input)
18}
19
20pub fn part1(input: &Grid<u8>) -> u32 {
21    #[cfg(not(feature = "simd"))]
22    let result = scalar::simulate(input, false, 4);
23
24    #[cfg(feature = "simd")]
25    let result = simd::simulate(input, false, 4);
26
27    result
28}
29
30pub fn part2(input: &Grid<u8>) -> u32 {
31    #[cfg(not(feature = "simd"))]
32    let result = scalar::simulate(input, true, 5);
33
34    #[cfg(feature = "simd")]
35    let result = simd::simulate(input, true, 5);
36
37    result
38}
39
40#[cfg(not(feature = "simd"))]
41mod scalar {
42    use super::*;
43
44    struct Seat {
45        point: Point,
46        size: usize,
47        neighbors: [Point; 8],
48    }
49
50    impl Seat {
51        fn push(&mut self, index: Point) {
52            self.neighbors[self.size] = index;
53            self.size += 1;
54        }
55    }
56
57    pub(super) fn simulate(input: &Grid<u8>, part_two: bool, limit: u8) -> u32 {
58        let mut seats = Vec::new();
59
60        for y in 0..input.height {
61            for x in 0..input.width {
62                let point = Point::new(x, y);
63                if input[point] != SEAT {
64                    continue;
65                }
66
67                let mut seat = Seat { point, size: 0, neighbors: [ORIGIN; 8] };
68
69                for direction in DIAGONAL {
70                    if part_two {
71                        let mut next = point + direction;
72                        while input.contains(next) {
73                            if input[next] == SEAT {
74                                seat.push(next);
75                                break;
76                            }
77                            next += direction;
78                        }
79                    } else {
80                        let next = point + direction;
81                        if input.contains(next) && input[next] == SEAT {
82                            seat.push(next);
83                        }
84                    }
85                }
86
87                seats.push(seat);
88            }
89        }
90
91        let mut current = input.same_size_with(0);
92        let mut next = input.same_size_with(0);
93
94        loop {
95            for seat in &seats {
96                let total: u8 = seat.neighbors[0..seat.size].iter().map(|&i| current[i]).sum();
97
98                next[seat.point] = if current[seat.point] == 0 {
99                    u8::from(total == 0)
100                } else {
101                    u8::from(total < limit)
102                };
103            }
104
105            (current, next) = (next, current);
106            if current == next {
107                return current.bytes.iter().map(|&n| n as u32).sum();
108            }
109        }
110    }
111}
112
113#[cfg(feature = "simd")]
114mod simd {
115    use super::*;
116    use std::simd::cmp::SimdPartialEq as _;
117    use std::simd::cmp::SimdPartialOrd as _;
118    use std::simd::*;
119
120    const LANE_WIDTH: usize = 32;
121    type Vector = Simd<u8, LANE_WIDTH>;
122
123    pub(super) fn simulate(input: &Grid<u8>, part_two: bool, limit: u8) -> u32 {
124        // Input grid is taller than it is wide. To make efficient use of the wide SIMD operations:
125        // * Add an empty border to eliminate bounds checking.
126        // * Transpose the input grid to make it wider than it is tall.
127        // * Round width up to next multiple of LANE_WIDTH.
128        let width = 2 + (input.height as usize).next_multiple_of(LANE_WIDTH) as i32;
129        let height = 2 + input.width;
130        let mut grid = Grid::new(width, height, 0);
131
132        for y in 0..input.height {
133            for x in 0..input.width {
134                let from = Point::new(x, y);
135                let to = Point::new(y + 1, x + 1);
136                grid[to] = u8::from(input[from] == SEAT);
137            }
138        }
139
140        // Build a list of seats that are non-adjacent but visible to each other.
141        let mut visible = Vec::new();
142
143        if part_two {
144            for y in 0..height {
145                for x in 0..width {
146                    let from = Point::new(x, y);
147                    if grid[from] == 0 {
148                        continue;
149                    }
150
151                    for direction in DIAGONAL {
152                        if grid[from + direction] == 1 {
153                            continue;
154                        }
155
156                        let mut to = from + direction * 2;
157                        while grid.contains(to) {
158                            if grid[to] == 1 {
159                                visible.push((from, to));
160                                break;
161                            }
162                            to += direction;
163                        }
164                    }
165                }
166            }
167        }
168
169        // Common constants.
170        let zero = Simd::splat(0);
171        let one = Simd::splat(1);
172        let limit = Simd::splat(limit);
173
174        let mut current = grid.same_size_with(0);
175        let mut next = grid.same_size_with(0);
176        let mut extra = grid.same_size_with(0);
177
178        loop {
179            // Add any non-adjacent seats that are visible to the total.
180            if part_two {
181                extra.bytes.fill(0);
182                for &(from, to) in &visible {
183                    extra[to] += current[from];
184                }
185            }
186
187            // Process grid column by column using wide SIMG vectors.
188            for x in (1..width - 1).step_by(LANE_WIDTH) {
189                let mut above = horizontal_neighbors(&current, x, 0);
190                let mut row = horizontal_neighbors(&current, x, 1);
191
192                for y in 1..height - 1 {
193                    let index = (width * y + x) as usize;
194                    let seats = Simd::from_slice(&grid.bytes[index..]);
195                    let occupied = Simd::from_slice(&current.bytes[index..]);
196                    let extra = Simd::from_slice(&extra.bytes[index..]);
197
198                    let below = horizontal_neighbors(&current, x, y + 1);
199                    let total = row + above + below + extra;
200                    above = row;
201                    row = below;
202
203                    // Empty to occupied.
204                    let first = total.simd_eq(zero).select(one, zero);
205                    // Occupied to empty
206                    let second = total.simd_le(limit).select(occupied, zero);
207                    // Nobody sits on the floor.
208                    let result = (first + second) & seats;
209
210                    result.copy_to_slice(&mut next.bytes[index..]);
211                }
212            }
213
214            (current, next) = (next, current);
215            if current == next {
216                return current.bytes.iter().map(|&b| b as u32).sum();
217            }
218        }
219    }
220
221    /// Create SIMD vector of the sum of left, right and center lanes.
222    #[inline]
223    fn horizontal_neighbors(grid: &Grid<u8>, x: i32, y: i32) -> Vector {
224        let index = (grid.width * y + x) as usize;
225
226        let center = Simd::from_slice(&grid.bytes[index..]);
227        let left = center.shift_elements_left::<1>(grid.bytes[index + LANE_WIDTH]);
228        let right = center.shift_elements_right::<1>(grid.bytes[index - 1]);
229
230        center + left + right
231    }
232}