1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169

//! # Sea Cucumber
//!
//! To speed things up we compute an entire row at a time for each direction, storing `across`
//! and `down` sea cucumbers as bits in a 256 bit wide variable.
//!
//! For example `...>>>>>...` is represented as `00011111000`.
//! To compute the movement the steps are:
//! * Rotate right by one `00001111100`
//! * Invert existing cucumbers `11100000111`
//! * Bitwise AND together to find cucumbers that can move `00000000100`
//! * Rotate `00000001000` left by one, invert `11111110111` then bitwise AND with original
//!   cucumbers to remove moving cucumbers from static `00011110000`
//! * Finally bitwise OR static and moving cucumbers together for the final result
//!   `00011110000 | 00000000100 = 00011110100`
//!
//! In the actual implementation `across` and `down` are stored separately so that we know
//! which cucumbers turn it is to move. We bitwise OR both together to calculate any blockers.
use std::ops::{BitAnd, BitOr, Not};

/// Duct tape two `u128` together to make a 256 bit wide integer.
#[derive(Clone, Copy, Default)]
pub struct U256 {
    left: u128,
    right: u128,
}

impl U256 {
    fn bit_set(&mut self, offset: usize) {
        if offset < 128 {
            self.right |= 1 << offset;
        } else {
            self.left |= 1 << (offset - 128);
        }
    }

    fn non_zero(&self) -> bool {
        self.left != 0 || self.right != 0
    }

    /// Perform a `rotate_left` where the width can be different from 256 bits.
    fn left_roll(&self, width: usize) -> U256 {
        if width <= 128 {
            let mask = !(1 << width);
            let right = ((self.right << 1) & mask) | (self.right >> (width - 1));
            U256 { left: self.left, right }
        } else {
            let mask = !(1 << (width - 128));
            let left = ((self.left << 1) & mask) | (self.right >> 127);
            let right = (self.right << 1) | (self.left >> (width - 129));
            U256 { left, right }
        }
    }

    /// Perform a `rotate_right` where the width can be different from 256 bits.
    fn right_roll(&self, width: usize) -> U256 {
        if width <= 128 {
            let right = (self.right >> 1) | ((self.right & 1) << (width - 1));
            U256 { left: self.left, right }
        } else {
            let left = (self.left >> 1) | ((self.right & 1) << (width - 129));
            let right = (self.right >> 1) | ((self.left & 1) << 127);
            U256 { left, right }
        }
    }
}

/// Implement operator bitswise logic so that we can use the regular `&`, `|` and `!` notation.
impl BitAnd for U256 {
    type Output = U256;

    fn bitand(self, rhs: U256) -> U256 {
        U256 { left: self.left & rhs.left, right: self.right & rhs.right }
    }
}

impl BitOr for U256 {
    type Output = U256;

    fn bitor(self, rhs: U256) -> U256 {
        U256 { left: self.left | rhs.left, right: self.right | rhs.right }
    }
}

impl Not for U256 {
    type Output = U256;

    fn not(self) -> U256 {
        U256 { left: !self.left, right: !self.right }
    }
}

#[derive(Clone)]
pub struct State {
    width: usize,
    height: usize,
    across: Vec<U256>,
    down: Vec<U256>,
}

/// Parse the sea cucumbers as individual bits into separate `across` and `down` arrays.
pub fn parse(input: &str) -> State {
    let raw: Vec<&[u8]> = input.lines().map(str::as_bytes).collect();
    let width = raw[0].len();
    let height = raw.len();
    let mut across = Vec::new();
    let mut down = Vec::new();

    for row in raw {
        let mut next_across = U256::default();
        let mut next_down = U256::default();

        for (offset, &col) in row.iter().enumerate() {
            match col {
                b'>' => next_across.bit_set(offset),
                b'v' => next_down.bit_set(offset),
                _ => (),
            }
        }

        across.push(next_across);
        down.push(next_down);
    }

    State { width, height, across, down }
}

pub fn part1(input: &State) -> usize {
    let State { width, height, mut across, mut down } = input.clone();
    let mut changed = true;
    let mut count = 0;

    while changed {
        changed = false;
        count += 1;

        // Use the bitwise logic described above to process an entire row across at a time.
        // Direction is reflected due to the parsing so we rotate left instead of right.
        for i in 0..height {
            let candidates = across[i].left_roll(width);
            let moved = candidates & !(across[i] | down[i]);
            changed |= moved.non_zero();
            let stay = across[i] & !moved.right_roll(width);
            across[i] = moved | stay;
        }

        // Use a similar approach to handle an entire row down at a time.
        let last_mask = across[0] | down[0];
        let mut moved = down[height - 1] & !last_mask;

        for i in 0..(height - 1) {
            changed |= moved.non_zero();
            let mask = across[i + 1] | down[i + 1];
            let stay = down[i] & mask;
            let next_moved = down[i] & !mask;
            down[i] = moved | stay;
            moved = next_moved;
        }

        changed |= moved.non_zero();
        let stay = down[height - 1] & last_mask;
        down[height - 1] = moved | stay;
    }

    count
}

pub fn part2(_input: &State) -> &'static str {
    "n/a"
}