aoc/year2021/
day25.rs

1//! # Sea Cucumber
2//!
3//! To speed things up we compute an entire row at a time for each direction, storing `across`
4//! and `down` sea cucumbers as bits in a 256 bit wide variable.
5//!
6//! For example `...>>>>>...` is represented as `00011111000`.
7//! To compute the movement the steps are:
8//! * Rotate right by one `00001111100`
9//! * Invert existing cucumbers `11100000111`
10//! * Bitwise AND together to find cucumbers that can move `00000000100`
11//! * Rotate `00000001000` left by one, invert `11111110111` then bitwise AND with original
12//!   cucumbers to remove moving cucumbers from static `00011110000`
13//! * Finally bitwise OR static and moving cucumbers together for the final result
14//!   `00011110000 | 00000000100 = 00011110100`
15//!
16//! In the actual implementation `across` and `down` are stored separately so that we know
17//! which cucumbers turn it is to move. We bitwise OR both together to calculate any blockers.
18use std::ops::{BitAnd, BitOr, Not};
19
20/// Duct tape two `u128` together to make a 256 bit wide integer.
21#[derive(Clone, Copy, Default)]
22pub struct U256 {
23    left: u128,
24    right: u128,
25}
26
27impl U256 {
28    fn bit_set(&mut self, offset: usize) {
29        if offset < 128 {
30            self.right |= 1 << offset;
31        } else {
32            self.left |= 1 << (offset - 128);
33        }
34    }
35
36    fn non_zero(&self) -> bool {
37        self.left != 0 || self.right != 0
38    }
39
40    /// Perform a `rotate_left` where the width can be different from 256 bits.
41    fn left_roll(&self, width: usize) -> U256 {
42        if width <= 128 {
43            let mask = !(1 << width);
44            let right = ((self.right << 1) & mask) | (self.right >> (width - 1));
45            U256 { left: self.left, right }
46        } else {
47            let mask = !(1 << (width - 128));
48            let left = ((self.left << 1) & mask) | (self.right >> 127);
49            let right = (self.right << 1) | (self.left >> (width - 129));
50            U256 { left, right }
51        }
52    }
53
54    /// Perform a `rotate_right` where the width can be different from 256 bits.
55    fn right_roll(&self, width: usize) -> U256 {
56        if width <= 128 {
57            let right = (self.right >> 1) | ((self.right & 1) << (width - 1));
58            U256 { left: self.left, right }
59        } else {
60            let left = (self.left >> 1) | ((self.right & 1) << (width - 129));
61            let right = (self.right >> 1) | ((self.left & 1) << 127);
62            U256 { left, right }
63        }
64    }
65}
66
67/// Implement operator bitswise logic so that we can use the regular `&`, `|` and `!` notation.
68impl BitAnd for U256 {
69    type Output = U256;
70
71    fn bitand(self, rhs: U256) -> U256 {
72        U256 { left: self.left & rhs.left, right: self.right & rhs.right }
73    }
74}
75
76impl BitOr for U256 {
77    type Output = U256;
78
79    fn bitor(self, rhs: U256) -> U256 {
80        U256 { left: self.left | rhs.left, right: self.right | rhs.right }
81    }
82}
83
84impl Not for U256 {
85    type Output = U256;
86
87    fn not(self) -> U256 {
88        U256 { left: !self.left, right: !self.right }
89    }
90}
91
92#[derive(Clone)]
93pub struct State {
94    width: usize,
95    height: usize,
96    across: Vec<U256>,
97    down: Vec<U256>,
98}
99
100/// Parse the sea cucumbers as individual bits into separate `across` and `down` arrays.
101pub fn parse(input: &str) -> State {
102    let raw: Vec<&[u8]> = input.lines().map(str::as_bytes).collect();
103    let width = raw[0].len();
104    let height = raw.len();
105    let mut across = Vec::new();
106    let mut down = Vec::new();
107
108    for row in raw {
109        let mut next_across = U256::default();
110        let mut next_down = U256::default();
111
112        for (offset, &col) in row.iter().enumerate() {
113            match col {
114                b'>' => next_across.bit_set(offset),
115                b'v' => next_down.bit_set(offset),
116                _ => (),
117            }
118        }
119
120        across.push(next_across);
121        down.push(next_down);
122    }
123
124    State { width, height, across, down }
125}
126
127pub fn part1(input: &State) -> usize {
128    let State { width, height, mut across, mut down } = input.clone();
129    let mut changed = true;
130    let mut count = 0;
131
132    while changed {
133        changed = false;
134        count += 1;
135
136        // Use the bitwise logic described above to process an entire row across at a time.
137        // Direction is reflected due to the parsing so we rotate left instead of right.
138        for i in 0..height {
139            let candidates = across[i].left_roll(width);
140            let moved = candidates & !(across[i] | down[i]);
141            changed |= moved.non_zero();
142            let stay = across[i] & !moved.right_roll(width);
143            across[i] = moved | stay;
144        }
145
146        // Use a similar approach to handle an entire row down at a time.
147        let last_mask = across[0] | down[0];
148        let mut moved = down[height - 1] & !last_mask;
149
150        for i in 0..(height - 1) {
151            changed |= moved.non_zero();
152            let mask = across[i + 1] | down[i + 1];
153            let stay = down[i] & mask;
154            let next_moved = down[i] & !mask;
155            down[i] = moved | stay;
156            moved = next_moved;
157        }
158
159        changed |= moved.non_zero();
160        let stay = down[height - 1] & last_mask;
161        down[height - 1] = moved | stay;
162    }
163
164    count
165}
166
167pub fn part2(_input: &State) -> &'static str {
168    "n/a"
169}
aoc/year2021/day25.rs

aoc/year2021/
day25.rs
