1use 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 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 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 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 if part_two {
181 extra.bytes.fill(0);
182 for &(from, to) in &visible {
183 extra[to] += current[from];
184 }
185 }
186
187 for x in (1..width - 1).step_by(LANE_WIDTH) {
189 let mut above = horizontal_neighbors(¤t, x, 0);
190 let mut row = horizontal_neighbors(¤t, 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(¤t.bytes[index..]);
196 let extra = Simd::from_slice(&extra.bytes[index..]);
197
198 let below = horizontal_neighbors(¤t, x, y + 1);
199 let total = row + above + below + extra;
200 above = row;
201 row = below;
202
203 let first = total.simd_eq(zero).select(one, zero);
205 let second = total.simd_le(limit).select(occupied, zero);
207 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 #[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}