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

aoc/year2020/
day24.rs
