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 surroundings neighbors of each tile, to a "push" model
11//! where we update the neighbors of each black tile instead.
12//!
13//! [`day 17`]: crate::year2020::day17
14use crate::util::hash::*;
15use std::array::from_fn;
16
17#[derive(PartialEq, Eq, Hash)]
18pub struct Hex {
19    q: i32,
20    r: i32,
21}
22
23pub fn parse(input: &str) -> FastSet<Hex> {
24    let mut tiles = FastSet::new();
25
26    for line in input.lines() {
27        let mut iter = line.bytes();
28        let mut q = 0;
29        let mut r = 0;
30
31        while let Some(b) = iter.next() {
32            match b {
33                b'e' => q += 1,
34                b'w' => q -= 1,
35                b'n' => {
36                    if b'e' == iter.next().unwrap() {
37                        q += 1;
38                    }
39                    r -= 1;
40                }
41                b's' => {
42                    if b'e' != iter.next().unwrap() {
43                        q -= 1;
44                    }
45                    r += 1;
46                }
47                _ => unreachable!(),
48            }
49        }
50
51        let tile = Hex { q, r };
52        if tiles.contains(&tile) {
53            tiles.remove(&tile);
54        } else {
55            tiles.insert(tile);
56        }
57    }
58
59    tiles
60}
61
62pub fn part1(input: &FastSet<Hex>) -> usize {
63    input.len()
64}
65
66pub fn part2(input: &FastSet<Hex>) -> usize {
67    // Determine bounds
68    let mut q1 = i32::MAX;
69    let mut q2 = i32::MIN;
70    let mut r1 = i32::MAX;
71    let mut r2 = i32::MIN;
72
73    for hex in input {
74        q1 = q1.min(hex.q);
75        q2 = q2.max(hex.q);
76        r1 = r1.min(hex.r);
77        r2 = 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;
83    let height = r2 - r1 + 203;
84    let neighbors: [i32; 6] = [-1, 1, -width, width, 1 - width, width - 1];
85    let neighbors: [usize; 6] = from_fn(|i| neighbors[i] as usize);
86
87    let mut active = Vec::with_capacity(5_000);
88    let mut candidates = Vec::with_capacity(5_000);
89    let mut next_active = Vec::with_capacity(5_000);
90
91    // Create initial active state, offsetting tiles so that all indices are positive.
92    for hex in input {
93        let index = width * (hex.r - r1 + 101) + (hex.q - q1 + 101);
94        active.push(index as usize);
95    }
96
97    for _ in 0..100 {
98        let mut state: Vec<u8> = vec![0; (width * height) as usize];
99
100        for &tile in &active {
101            for &offset in &neighbors {
102                // Earlier we converted the offsets from signed `i32` to unsigned `usize`. To
103                // achieve subtraction for negative indices, we use a `wrapping_add` that performs
104                // [two's complement](https://en.wikipedia.org/wiki/Two%27s_complement) arithmetic.
105                let index = tile.wrapping_add(offset);
106                state[index] += 1;
107
108                if state[index] == 2 {
109                    candidates.push(index);
110                }
111            }
112        }
113
114        // Active tiles remain active with both one and two neighbors.
115        for &tile in &active {
116            if state[tile] == 1 {
117                next_active.push(tile);
118            }
119        }
120
121        // Check that the neighbor count for inactive tiles hasn't exceeded two.
122        for &tile in &candidates {
123            if state[tile] == 2 {
124                next_active.push(tile);
125            }
126        }
127
128        // Swap to make next generation the current generation.
129        (active, next_active) = (next_active, active);
130        candidates.clear();
131        next_active.clear();
132    }
133
134    active.len()
135}
aoc/year2020/day24.rs

aoc/year2020/
day24.rs
