aoc/year2022/
day17.rs

1//! # Pyroclastic Flow
2//!
3//! ## Part One
4//!
5//! For speed we encode each rock shape as binary bits so that we can use bitwise logic to check
6//! for collisions. Each rock is encoded top to bottom and left to right. For example:
7//!
8//! ```none
9//!    #     00010000    0x10
10//!   ### => 00111000 => 0x38 => 0x00103810
11//!    #     00010000    0x10
12//! ```
13//!
14//! The bits are shifted 2 away from the left wall. Walls are also encoded in binary, overlapping
15//! the left and right walls (no rock will ever collide first with a wall and its top row):
16//!
17//! ```none
18//!   100000001
19//!   100000001 => 0x01010101
20//!   100000001
21//! ```
22//!
23//! We store the accumulated tower efficiently as a vec of `u8` including the floor at index
24//! zero as a special pattern of `11111111`.
25//!
26//! We use bitwise AND to check for collisions between the rock, the walls and the existing tower
27//! in one operation.
28//!
29//! ## Part Two
30//!
31//! Since there's no reasonable way to analytically predict the height after some `n` rocks
32//! and brute force would take too long we can assume that there must be a
33//! [cycle](https://en.wikipedia.org/wiki/Cycle_(graph_theory)) in the output.
34//!
35//! We choose an arbitrary length and generate a sequence of that size then search
36//! for repeating patterns. Once we find the length of the cycle then we can extrapolate for
37//! any `n` greater than the start of the cycle.
38use std::iter::{Copied, Cycle};
39use std::slice::Iter;
40
41/// Convenience alias to shorten type name.
42type Wrapper<'a, T> = Cycle<Copied<Iter<'a, T>>>;
43
44/// Encode pieces one row per byte, highest row in the most significant position.
45const FLOOR: u8 = 0xff;
46const WALLS: u32 = 0x01010101;
47const ROCKS: [Rock; 5] = [
48    Rock { size: 1, shape: 0x0000003c },
49    Rock { size: 3, shape: 0x00103810 },
50    Rock { size: 3, shape: 0x00080838 },
51    Rock { size: 4, shape: 0x20202020 },
52    Rock { size: 2, shape: 0x00003030 },
53];
54
55#[derive(Copy, Clone)]
56struct Rock {
57    size: usize,
58    shape: u32,
59}
60
61struct State<'a> {
62    rocks: Wrapper<'a, Rock>,
63    jets: Wrapper<'a, u8>,
64    tower: Vec<u8>,
65    height: usize,
66}
67
68impl State<'_> {
69    fn new(input: &[u8]) -> State<'_> {
70        // Rocks and jets repeat endlessly.
71        // 13,000 is the the maximum possible height that the tower could reach after 5000 rocks.
72        let mut state = State {
73            rocks: ROCKS.iter().copied().cycle(),
74            jets: input.iter().copied().cycle(),
75            tower: vec![0; 13_000],
76            height: 0,
77        };
78        state.tower[0] = FLOOR;
79        state
80    }
81}
82
83/// Implement as an iterator for ergonomics.
84impl Iterator for State<'_> {
85    type Item = usize;
86
87    fn next(&mut self) -> Option<Self::Item> {
88        let Rock { size, mut shape } = self.rocks.next().unwrap();
89        let mut chunk = WALLS;
90        // Start 3 rows above the current top of the tower.
91        let mut index = self.height + 3;
92
93        loop {
94            let jet = self.jets.next().unwrap();
95            let candidate = if jet == b'<' { shape.rotate_left(1) } else { shape.rotate_right(1) };
96            // Check for a horizontal collision (this does not prevent downwards movement).
97            if candidate & chunk == 0 {
98                shape = candidate;
99            }
100
101            // The neat part of using bitwise AND to compare is that we can check all four
102            // rows in a single operation, including both walls and the existing tower.
103            chunk = (chunk << 8) | WALLS | (self.tower[index] as u32);
104
105            if shape & chunk == 0 {
106                // Keep falling
107                index -= 1;
108            } else {
109                // Add the new piece to the tower.
110                let bytes = shape.to_le_bytes();
111                self.tower[index + 1] |= bytes[0];
112                self.tower[index + 2] |= bytes[1];
113                self.tower[index + 3] |= bytes[2];
114                self.tower[index + 4] |= bytes[3];
115                // Rock may have fallen far enough to not add any additional height.
116                self.height = self.height.max(index + size);
117                break Some(self.height);
118            }
119        }
120    }
121}
122
123pub fn parse(input: &str) -> &[u8] {
124    input.trim().as_bytes()
125}
126
127pub fn part1(input: &[u8]) -> usize {
128    State::new(input).nth(2021).unwrap()
129}
130
131pub fn part2(input: &[u8]) -> usize {
132    // We make two complete [SWAGs](https://en.wikipedia.org/wiki/Scientific_wild-ass_guess):
133    // * 1000 row deltas are enough to form a unique prefix
134    // * The tower pattern will repeat in a cycle in first 5000 rows.
135    let guess = 1000;
136    let height: Vec<_> = State::new(input).take(5 * guess).collect();
137    // We compare based on the *delta* between rows instead of absolute heights.
138    let deltas: Vec<_> = height
139        .iter()
140        .scan(0, |state, &height| {
141            let delta = height - *state;
142            *state = height;
143            Some(delta)
144        })
145        .collect();
146
147    // Simple brute force check, instead of a
148    // [cycle detection](https://en.wikipedia.org/wiki/Cycle_detection) algorithm.
149    let end = deltas.len() - guess;
150    let needle = &deltas[end..];
151    let start = deltas.windows(guess).position(|w| w == needle).unwrap();
152
153    // Now that we know when the cycle repeats, we can work out the height for any arbitrary
154    // number of rocks after that point.
155    let cycle_height = height[end] - height[start];
156    let cycle_width = end - start;
157    let offset = 1_000_000_000_000 - 1 - start;
158    let quotient = offset / cycle_width;
159    let remainder = offset % cycle_width;
160    (quotient * cycle_height) + height[start + remainder]
161}
aoc/year2022/day17.rs

aoc/year2022/
day17.rs
