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::*;
20use implementation::*;
21
22#[derive(PartialEq, Eq, Hash)]
23pub struct Hex {
24    q: i32,
25    r: i32,
26}
27
28pub fn parse(input: &str) -> FastSet<Hex> {
29    let mut tiles = FastSet::new();
30
31    for line in input.lines() {
32        let mut iter = line.bytes();
33        let mut q = 0;
34        let mut r = 0;
35
36        while let Some(b) = iter.next() {
37            match b {
38                b'e' => q += 1,
39                b'w' => q -= 1,
40                b'n' => {
41                    r -= 1;
42                    if iter.next().unwrap() == b'e' {
43                        q += 1;
44                    }
45                }
46                b's' => {
47                    r += 1;
48                    if iter.next().unwrap() == b'w' {
49                        q -= 1;
50                    }
51                }
52                _ => unreachable!(),
53            }
54        }
55
56        let tile = Hex { q, r };
57        if !tiles.remove(&tile) {
58            tiles.insert(tile);
59        }
60    }
61
62    tiles
63}
64
65pub fn part1(input: &FastSet<Hex>) -> usize {
66    input.len()
67}
68
69pub fn part2(input: &FastSet<Hex>) -> usize {
70    simulate(input)
71}
72
73#[cfg(not(feature = "simd"))]
74mod implementation {
75    use super::*;
76
77    pub(super) fn simulate(input: &FastSet<Hex>) -> usize {
78        // Determine bounds
79        let (q1, q2, r1, r2) =
80            input.iter().fold((i32::MAX, i32::MIN, i32::MAX, i32::MIN), |(q1, q2, r1, r2), hex| {
81                (q1.min(hex.q), q2.max(hex.q), r1.min(hex.r), r2.max(hex.r))
82            });
83
84        // Create array with enough space to allow expansion for 100 generations.
85        // 2 * (100 generations + 1 buffer) + Origin = 203 extra in each dimension
86        let width = (q2 - q1 + 203) as usize;
87        let height = (r2 - r1 + 203) as usize;
88
89        let mut state = vec![0_u8; width * height];
90        let mut active = Vec::with_capacity(5_000);
91        let mut candidates = Vec::with_capacity(5_000);
92        let mut next_active = Vec::with_capacity(5_000);
93
94        // Create initial active state, offsetting tiles so that all indices are positive.
95        for hex in input {
96            let index = width * (hex.r - r1 + 101) as usize + (hex.q - q1 + 101) as usize;
97            active.push(index);
98        }
99
100        for _ in 0..100 {
101            state.fill(0);
102
103            for &tile in &active {
104                for index in [
105                    tile + 1,
106                    tile - 1,
107                    tile + width,
108                    tile - width,
109                    tile + 1 - width,
110                    tile - 1 + width,
111                ] {
112                    state[index] += 1;
113
114                    if state[index] == 2 {
115                        candidates.push(index);
116                    }
117                }
118            }
119
120            // Active tiles remain active with both one and two neighbors.
121            next_active.extend(active.iter().filter(|&&tile| state[tile] == 1));
122            // Check that the neighbor count for inactive tiles hasn't exceeded two.
123            next_active.extend(candidates.iter().filter(|&&tile| state[tile] == 2));
124
125            // Swap to make next generation the current generation.
126            (active, next_active) = (next_active, active);
127            candidates.clear();
128            next_active.clear();
129        }
130
131        active.len()
132    }
133}
134
135#[cfg(feature = "simd")]
136mod implementation {
137    use super::*;
138    use std::simd::cmp::SimdPartialEq as _;
139    use std::simd::*;
140
141    const LANE_WIDTH: usize = 32;
142    type Vector = Simd<u8, LANE_WIDTH>;
143
144    pub(super) fn simulate(input: &FastSet<Hex>) -> usize {
145        // Determine bounds
146        let (q1, q2, r1, r2) =
147            input.iter().fold((i32::MAX, i32::MIN, i32::MAX, i32::MIN), |(q1, q2, r1, r2), hex| {
148                (q1.min(hex.q), q2.max(hex.q), r1.min(hex.r), r2.max(hex.r))
149            });
150
151        // Create array with enough space to allow expansion for 100 generations.
152        // 2 * (100 generations + 1 buffer) + Origin = 203 extra in each dimension
153        let width = 2 + ((q2 - q1 + 201) as usize).next_multiple_of(LANE_WIDTH);
154        let height = (r2 - r1 + 203) as usize;
155
156        // Create initial active state, offsetting tiles so that all indices are positive.
157        let mut current = vec![0; width * height];
158        let mut next = vec![0; width * height];
159
160        for hex in input {
161            let index = width * (hex.r - r1 + 101) as usize + (hex.q - q1 + 101) as usize;
162            current[index] = 1;
163        }
164
165        let zero = Simd::splat(0);
166        let one = Simd::splat(1);
167        let two = Simd::splat(2);
168
169        for round in 0..100 {
170            // The active state boundary expands by 1 horizontally and vertically each round.
171            let edge = 100 - round;
172
173            for x in (edge..width - edge).step_by(LANE_WIDTH) {
174                for y in edge..height - edge {
175                    let index = width * y + x;
176                    let tiles = Simd::from_slice(&current[index..]);
177
178                    let above = left_center(&current, index - width);
179                    let row = left_right(&current, index);
180                    let below = center_right(&current, index + width);
181                    let total = row + above + below;
182
183                    // Black => Black (one neighbor).
184                    let first = (tiles.simd_eq(one) & total.simd_eq(one)).select(one, zero);
185                    // White => Black and Black => Black (two neighbors).
186                    let second = total.simd_eq(two).select(one, zero);
187
188                    let result = first + second;
189                    result.copy_to_slice(&mut next[index..]);
190                }
191            }
192
193            (current, next) = (next, current);
194        }
195
196        current.iter().map(|&b| b as usize).sum()
197    }
198
199    #[inline]
200    fn left_center(current: &[u8], index: usize) -> Vector {
201        let center = Simd::from_slice(&current[index..]);
202        let left = center.shift_elements_left::<1>(current[index + LANE_WIDTH]);
203        left + center
204    }
205
206    #[inline]
207    fn left_right(current: &[u8], index: usize) -> Vector {
208        let center = Simd::from_slice(&current[index..]);
209        let left = center.shift_elements_left::<1>(current[index + LANE_WIDTH]);
210        let right = center.shift_elements_right::<1>(current[index - 1]);
211        left + right
212    }
213
214    #[inline]
215    fn center_right(current: &[u8], index: usize) -> Vector {
216        let center = Simd::from_slice(&current[index..]);
217        let right = center.shift_elements_right::<1>(current[index - 1]);
218        center + right
219    }
220}
aoc/year2020/day24.rs

aoc/year2020/
day24.rs
