aoc/year2020/
day24.rs

1//! # Lobby Layout
2//!
3//! Hex grid parsing and navigation uses
4//! [Axial Coordinates](https://www.redblobgames.com/grids/hexagons/#coordinates-cube)
5//! exactly as described in the excellent [Red Blob Games](https://www.redblobgames.com/) blog.
6//!
7//! Part two uses exactly the same approach as [`day 17`] and most of the code is identical.
8//!
9//! As the black tiles are very sparse (about 8% for my input) it's faster to switch from
10//! a "pull" model where we check the surrounding neighbors of each tile, to a "push" model
11//! where we update the neighbors of each black tile instead.
12//!
13//! The SIMD alternative approach is much faster, processing 32 lanes at a time. As a further
14//! optimization we skip rows and columns that the active state hasn't reached. The approach
15//! is very similar to [`day 11`].
16//!
17//! [`day 17`]: crate::year2020::day17
18//! [`day 11`]: crate::year2020::day11
19use crate::util::hash::*;
20
21#[derive(PartialEq, Eq, Hash)]
22pub struct Hex {
23    q: i32,
24    r: i32,
25}
26
27pub fn parse(input: &str) -> FastSet<Hex> {
28    let mut tiles = FastSet::new();
29
30    for line in input.lines() {
31        let mut iter = line.bytes();
32        let mut q = 0;
33        let mut r = 0;
34
35        while let Some(b) = iter.next() {
36            match b {
37                b'e' => q += 1,
38                b'w' => q -= 1,
39                b'n' => {
40                    r -= 1;
41                    if iter.next().unwrap() == b'e' {
42                        q += 1;
43                    }
44                }
45                b's' => {
46                    r += 1;
47                    if iter.next().unwrap() == b'w' {
48                        q -= 1;
49                    }
50                }
51                _ => unreachable!(),
52            }
53        }
54
55        let tile = Hex { q, r };
56        if !tiles.remove(&tile) {
57            tiles.insert(tile);
58        }
59    }
60
61    tiles
62}
63
64pub fn part1(input: &FastSet<Hex>) -> usize {
65    input.len()
66}
67
68pub fn part2(input: &FastSet<Hex>) -> usize {
69    #[cfg(not(feature = "simd"))]
70    let result = scalar::simulate(input);
71
72    #[cfg(feature = "simd")]
73    let result = simd::simulate(input);
74
75    result
76}
77
78#[cfg(not(feature = "simd"))]
79mod scalar {
80    use super::*;
81
82    pub(super) fn simulate(input: &FastSet<Hex>) -> usize {
83        // Determine bounds
84        let (q1, q2, r1, r2) =
85            input.iter().fold((i32::MAX, i32::MIN, i32::MAX, i32::MIN), |(q1, q2, r1, r2), hex| {
86                (q1.min(hex.q), q2.max(hex.q), r1.min(hex.r), r2.max(hex.r))
87            });
88
89        // Create array with enough space to allow expansion for 100 generations.
90        // 2 * (100 generations + 1 buffer) + Origin = 203 extra in each dimension
91        let width = (q2 - q1 + 203) as usize;
92        let height = (r2 - r1 + 203) as usize;
93
94        let mut state = vec![0_u8; width * height];
95        let mut active = Vec::with_capacity(5_000);
96        let mut candidates = Vec::with_capacity(5_000);
97        let mut next_active = Vec::with_capacity(5_000);
98
99        // Create initial active state, offsetting tiles so that all indices are positive.
100        for hex in input {
101            let index = width * (hex.r - r1 + 101) as usize + (hex.q - q1 + 101) as usize;
102            active.push(index);
103        }
104
105        for _ in 0..100 {
106            state.fill(0);
107
108            for &tile in &active {
109                for index in [
110                    tile + 1,
111                    tile - 1,
112                    tile + width,
113                    tile - width,
114                    tile + 1 - width,
115                    tile - 1 + width,
116                ] {
117                    state[index] += 1;
118
119                    if state[index] == 2 {
120                        candidates.push(index);
121                    }
122                }
123            }
124
125            // Active tiles remain active with both one and two neighbors.
126            for &tile in &active {
127                if state[tile] == 1 {
128                    next_active.push(tile);
129                }
130            }
131
132            // Check that the neighbor count for inactive tiles hasn't exceeded two.
133            for &tile in &candidates {
134                if state[tile] == 2 {
135                    next_active.push(tile);
136                }
137            }
138
139            // Swap to make next generation the current generation.
140            (active, next_active) = (next_active, active);
141            candidates.clear();
142            next_active.clear();
143        }
144
145        active.len()
146    }
147}
148
149#[cfg(feature = "simd")]
150mod simd {
151    use super::*;
152    use std::simd::cmp::SimdPartialEq as _;
153    use std::simd::*;
154
155    const LANE_WIDTH: usize = 32;
156    type Vector = Simd<u8, LANE_WIDTH>;
157
158    pub(super) fn simulate(input: &FastSet<Hex>) -> usize {
159        // Determine bounds
160        let (q1, q2, r1, r2) =
161            input.iter().fold((i32::MAX, i32::MIN, i32::MAX, i32::MIN), |(q1, q2, r1, r2), hex| {
162                (q1.min(hex.q), q2.max(hex.q), r1.min(hex.r), r2.max(hex.r))
163            });
164
165        // Create array with enough space to allow expansion for 100 generations.
166        // 2 * (100 generations + 1 buffer) + Origin = 203 extra in each dimension
167        let width = 2 + ((q2 - q1 + 201) as usize).next_multiple_of(LANE_WIDTH);
168        let height = (r2 - r1 + 203) as usize;
169
170        // Create initial active state, offsetting tiles so that all indices are positive.
171        let mut current = vec![0; width * height];
172        let mut next = vec![0; width * height];
173
174        for hex in input {
175            let index = width * (hex.r - r1 + 101) as usize + (hex.q - q1 + 101) as usize;
176            current[index] = 1;
177        }
178
179        let zero = Simd::splat(0);
180        let one = Simd::splat(1);
181        let two = Simd::splat(2);
182
183        for round in 0..100 {
184            // The active state boundary expands by 1 horizontally and vertically each round.
185            let edge = 100 - round;
186
187            for x in (edge..width - edge).step_by(LANE_WIDTH) {
188                for y in edge..height - edge {
189                    let index = width * y + x;
190                    let tiles = Simd::from_slice(&current[index..]);
191
192                    let above = left_center(&current, index - width);
193                    let row = left_right(&current, index);
194                    let below = center_right(&current, index + width);
195                    let total = row + above + below;
196
197                    // Black => Black (one neighbor).
198                    let first = (tiles.simd_eq(one) & total.simd_eq(one)).select(one, zero);
199                    // White => Black and Black => Black (two neighbors).
200                    let second = total.simd_eq(two).select(one, zero);
201
202                    let result = first + second;
203                    result.copy_to_slice(&mut next[index..]);
204                }
205            }
206
207            (current, next) = (next, current);
208        }
209
210        current.iter().map(|&b| b as usize).sum()
211    }
212
213    #[inline]
214    fn left_center(current: &[u8], index: usize) -> Vector {
215        let center = Simd::from_slice(&current[index..]);
216        let left = center.shift_elements_left::<1>(current[index + LANE_WIDTH]);
217        left + center
218    }
219
220    #[inline]
221    fn left_right(current: &[u8], index: usize) -> Vector {
222        let center = Simd::from_slice(&current[index..]);
223        let left = center.shift_elements_left::<1>(current[index + LANE_WIDTH]);
224        let right = center.shift_elements_right::<1>(current[index - 1]);
225        left + right
226    }
227
228    #[inline]
229    fn center_right(current: &[u8], index: usize) -> Vector {
230        let center = Simd::from_slice(&current[index..]);
231        let right = center.shift_elements_right::<1>(current[index - 1]);
232        center + right
233    }
234}
aoc/year2020/day24.rs

aoc/year2020/
day24.rs
