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, once};
39use std::slice::Iter;
40
41/// Encode pieces one row per byte, highest row in the most significant position.
42const FLOOR: u8 = 0xff;
43const WALLS: u32 = 0x01010101;
44const ROCKS: [Rock; 5] = [
45    Rock { size: 1, shape: 0x0000003c },
46    Rock { size: 3, shape: 0x00103810 },
47    Rock { size: 3, shape: 0x00080838 },
48    Rock { size: 4, shape: 0x20202020 },
49    Rock { size: 2, shape: 0x00003030 },
50];
51
52/// Convenience alias to shorten type name.
53type Wrapper<'a, T> = Cycle<Copied<Iter<'a, T>>>;
54
55#[derive(Clone, Copy)]
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        // 13,000 is the maximum possible height that the tower could reach after 5000 rocks.
71        let mut tower = vec![0; 13_000];
72        tower[0] = FLOOR;
73
74        // Rocks and jets repeat endlessly.
75        let rocks = ROCKS.iter().copied().cycle();
76        let jets = input.iter().copied().cycle();
77        State { rocks, jets, tower, height: 0 }
78    }
79}
80
81/// Implement as an iterator for ergonomics.
82impl Iterator for State<'_> {
83    type Item = usize;
84
85    fn next(&mut self) -> Option<Self::Item> {
86        let Rock { size, mut shape } = self.rocks.next().unwrap();
87        let mut chunk = WALLS;
88        // Start 3 rows above the current top of the tower.
89        let mut index = self.height + 3;
90
91        loop {
92            let jet = self.jets.next().unwrap();
93            let candidate = if jet == b'<' { shape.rotate_left(1) } else { shape.rotate_right(1) };
94            // Check for a horizontal collision (this does not prevent downwards movement).
95            if candidate & chunk == 0 {
96                shape = candidate;
97            }
98
99            // The neat part of using bitwise AND to compare is that we can check all four
100            // rows in a single operation, including both walls and the existing tower.
101            chunk = (chunk << 8) | WALLS | (self.tower[index] as u32);
102
103            if shape & chunk == 0 {
104                // Keep falling.
105                index -= 1;
106            } else {
107                // Add the new piece to the tower.
108                let bytes = shape.to_le_bytes();
109                self.tower[index + 1] |= bytes[0];
110                self.tower[index + 2] |= bytes[1];
111                self.tower[index + 3] |= bytes[2];
112                self.tower[index + 4] |= bytes[3];
113                // Rock may have fallen far enough to not add any additional height.
114                self.height = self.height.max(index + size);
115                break Some(self.height);
116            }
117        }
118    }
119}
120
121pub fn parse(input: &str) -> &[u8] {
122    input.trim().as_bytes()
123}
124
125pub fn part1(input: &[u8]) -> usize {
126    State::new(input).nth(2021).unwrap()
127}
128
129pub fn part2(input: &[u8]) -> usize {
130    // We make two complete [SWAGs](https://en.wikipedia.org/wiki/Scientific_wild-ass_guess):
131    // * 1000 row deltas are enough to form a unique prefix
132    // * The tower pattern will repeat in a cycle in the first 5000 rows.
133    let guess = 1000;
134    let height: Vec<_> = State::new(input).take(5 * guess).collect();
135    // We compare based on the *delta* between rows instead of absolute heights.
136    let deltas: Vec<_> =
137        once(height[0]).chain(height.array_windows().map(|[a, b]| b - a)).collect();
138
139    // Simple brute force check, instead of a
140    // [cycle detection](https://en.wikipedia.org/wiki/Cycle_detection) algorithm.
141    let end = deltas.len() - guess;
142    let needle = &deltas[end..];
143    let start = deltas.windows(guess).position(|w| w == needle).unwrap();
144
145    // Now that we know when the cycle repeats, we can work out the height for any arbitrary
146    // number of rocks after that point.
147    let cycle_height = height[end] - height[start];
148    let cycle_width = end - start;
149    let offset = 1_000_000_000_000 - 1 - start;
150    let quotient = offset / cycle_width;
151    let remainder = offset % cycle_width;
152    (quotient * cycle_height) + height[start + remainder]
153}
aoc/year2022/day17.rs

aoc/year2022/
day17.rs
