diff options
Diffstat (limited to '2022/src/bin/day_17.rs')
| -rw-r--r-- | 2022/src/bin/day_17.rs | 238 |
1 files changed, 238 insertions, 0 deletions
diff --git a/2022/src/bin/day_17.rs b/2022/src/bin/day_17.rs new file mode 100644 index 0000000..46fedc8 --- /dev/null +++ b/2022/src/bin/day_17.rs @@ -0,0 +1,238 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + combinator::{map, value}, + multi::many1, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_17.txt")?; + let nudges = Inputs::parser(&input).unwrap().1; + let pieces = Piece::all(); + let board = GameBoard::new(pieces, nudges.nudges); + + { + let mut part_1_board = board.clone(); + for _ in 0..2022 { + part_1_board.drop_next_piece(); + } + dbg!(part_1_board.full_height()); + } + + { + let mut part_2_board = board.clone(); + for i in 0..1_000_000_000_000u64 { + if i % 1_000_000_000 == 0 { + dbg!(i / 1_000_000_000, part_2_board.truncated); + } + part_2_board.drop_next_piece(); + } + dbg!(part_2_board.full_height()); + } + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Inputs { + nudges: Vec<Nudge>, +} + +#[derive(Debug, Clone)] +enum Nudge { + Left, + Right, +} + +#[derive(Debug, Clone)] +struct Piece { + data_at_x: Vec<Vec<u8>>, +} + +impl Inputs { + fn parser(input: &str) -> IResult<&str, Self> { + map( + many1(alt(( + value(Nudge::Left, tag("<")), + value(Nudge::Right, tag(">")), + ))), + |nudges| Inputs { nudges }, + )(input) + } +} + +impl Piece { + fn new(data_at_x_0: Vec<u8>) -> Piece { + let mut shifting_data = data_at_x_0.clone(); + + let mut data_at_x = vec![data_at_x_0]; + + while shifting_data.iter().all(|b| b & 0b00000010 == 0) { + for row in &mut shifting_data { + *row >>= 1; + } + data_at_x.push(shifting_data.clone()); + } + + Piece { data_at_x } + } + + fn all() -> Vec<Piece> { + vec![ + Piece::new(vec![0b11110000]), + Piece::new(vec![0b01000000, 0b11100000, 0b01000000]), + Piece::new(vec![0b11100000, 0b00100000, 0b00100000]), + Piece::new(vec![0b10000000, 0b10000000, 0b10000000, 0b10000000]), + Piece::new(vec![0b11000000, 0b11000000]), + ] + } +} + +#[derive(Debug, Clone)] +struct GameBoard { + pieces: Vec<Piece>, + piece_index: usize, + nudges: Vec<Nudge>, + compound_nudges: Vec<Vec<usize>>, + nudge_index: usize, + solidified: Vec<u8>, + truncated: u64, +} + +impl GameBoard { + fn new(pieces: Vec<Piece>, nudges: Vec<Nudge>) -> GameBoard { + GameBoard { + compound_nudges: pieces + .iter() + .map(|piece| { + (0..nudges.len()) + .map(|nudge_start| { + let mut piece_x = 2; + for i in 0..4 { + let nudge_i = (nudge_start + i) % nudges.len(); + match nudges[nudge_i] { + Nudge::Left => { + if piece_x > 0 { + piece_x -= 1; + } + } + Nudge::Right => { + if piece_x < piece.data_at_x.len() - 1 { + piece_x += 1; + } + } + } + } + piece_x + }) + .collect() + }) + .collect(), + pieces, + piece_index: 0, + nudges, + nudge_index: 0, + solidified: Vec::new(), + truncated: 0, + } + } + + fn drop_next_piece(&mut self) { + let piece = &self.pieces[self.piece_index]; + // precomputes the effect of the first 4 nudges + let mut piece_x = self.compound_nudges[self.piece_index][self.nudge_index]; + + self.piece_index += 1; + if self.piece_index >= self.pieces.len() { + self.piece_index -= self.pieces.len(); + } + + self.nudge_index += 4; + if self.nudge_index >= self.nudges.len() { + self.nudge_index -= self.nudges.len(); + } + + let mut piece_y = self.first_open_row(); + + loop { + if piece_y > 0 && self.piece_can_be_at(piece_y - 1, &piece.data_at_x[piece_x]) { + piece_y -= 1; + } else { + break; + } + + let nudge = &self.nudges[self.nudge_index]; + self.nudge_index += 1; + if self.nudge_index >= self.nudges.len() { + self.nudge_index -= self.nudges.len(); + } + + match nudge { + Nudge::Left => { + if piece_x > 0 && self.piece_can_be_at(piece_y, &piece.data_at_x[piece_x - 1]) { + piece_x -= 1; + } + } + Nudge::Right => { + if piece_x < piece.data_at_x.len() - 1 + && self.piece_can_be_at(piece_y, &piece.data_at_x[piece_x + 1]) + { + piece_x += 1; + } + } + } + } + + let mut to_truncate = None; + for (i, piece_row) in piece.data_at_x[piece_x].iter().enumerate() { + let full_index = piece_y + i; + if full_index >= self.solidified.len() { + self.solidified.push(piece_row.clone()); + } else { + self.solidified[full_index] |= piece_row; + if self.solidified[full_index] == 0b11111110 { + to_truncate = Some(full_index); + } + } + } + + if let Some(to_truncate) = to_truncate { + self.truncated += to_truncate as u64; + let truncated_len = self.solidified.len() - to_truncate; + for move_i in 0..truncated_len { + self.solidified[move_i] = self.solidified[move_i + to_truncate]; + } + self.solidified.truncate(truncated_len); + } + } + + fn piece_can_be_at(&self, piece_y: usize, piece: &[u8]) -> bool { + for (i, row) in piece.iter().enumerate() { + let full_i = piece_y + i; + if full_i >= self.solidified.len() { + return true; + } + if self.solidified[full_i] & row != 0 { + return false; + } + } + return true; + } + + fn first_open_row(&self) -> usize { + self.solidified.len() + } + + fn full_height(&self) -> u64 { + self.first_open_row() as u64 + self.truncated + } + + fn debug(&self) { + println!("Clearerd: {}", self.truncated); + for row in self.solidified.iter().rev() { + println!("{:08b}", row); + } + } +} |