diff options
author | Jesse Luehrs <doy@tozt.net> | 2022-12-17 02:59:05 -0500 |
---|---|---|
committer | Jesse Luehrs <doy@tozt.net> | 2022-12-17 02:59:05 -0500 |
commit | 87d04eb2c3e09e4f01a12eb08461b22bbbcf28d6 (patch) | |
tree | 653ba3f2298676591e8ebb9c696c093ffea92656 /src | |
parent | add7534a2230149800a836a6a848f2143a5a5e2f (diff) | |
download | advent-of-code-87d04eb2c3e09e4f01a12eb08461b22bbbcf28d6.tar.gz advent-of-code-87d04eb2c3e09e4f01a12eb08461b22bbbcf28d6.zip |
day 17
Diffstat (limited to 'src')
-rw-r--r-- | src/bin/2021/day25.rs | 2 | ||||
-rw-r--r-- | src/bin/2022/day17.rs | 263 | ||||
-rw-r--r-- | src/bin/2022/main.rs | 2 | ||||
-rw-r--r-- | src/grid.rs | 69 | ||||
-rw-r--r-- | src/parse.rs | 2 |
5 files changed, 315 insertions, 23 deletions
diff --git a/src/bin/2021/day25.rs b/src/bin/2021/day25.rs index 4bd5c92..135f6b3 100644 --- a/src/bin/2021/day25.rs +++ b/src/bin/2021/day25.rs @@ -1,6 +1,6 @@ use advent_of_code::prelude::*; -#[derive(Debug, Clone, Eq, PartialEq)] +#[derive(Debug, Clone, Eq, PartialEq, Hash)] pub enum Cell { Down, Right, diff --git a/src/bin/2022/day17.rs b/src/bin/2022/day17.rs new file mode 100644 index 0000000..46900e1 --- /dev/null +++ b/src/bin/2022/day17.rs @@ -0,0 +1,263 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +#[derive(Clone, Copy, Debug)] +pub enum Direction { + Left, + Right, +} + +impl TryFrom<u8> for Direction { + type Error = Error; + + fn try_from(value: u8) -> Result<Self, Self::Error> { + match value { + b'<' => Ok(Self::Left), + b'>' => Ok(Self::Right), + _ => Err(anyhow!("unknown char {}", value)), + } + } +} + +struct Piece(Vec<(Row, Col)>); +static PIECES: once_cell::sync::Lazy<[Piece; 5]> = + once_cell::sync::Lazy::new(|| { + fn p(row: usize, col: usize) -> (Row, Col) { + (Row(row), Col(col)) + } + [ + Piece(vec![p(0, 0), p(0, 1), p(0, 2), p(0, 3)]), + Piece(vec![p(0, 1), p(1, 0), p(1, 1), p(1, 2), p(2, 1)]), + Piece(vec![p(0, 0), p(0, 1), p(0, 2), p(1, 2), p(2, 2)]), + Piece(vec![p(0, 0), p(1, 0), p(2, 0), p(3, 0)]), + Piece(vec![p(0, 0), p(0, 1), p(1, 0), p(1, 1)]), + ] + }); + +#[derive(Default)] +struct Chamber { + grid: Grid<bool>, + piece_pos: Option<(Row, Col)>, + piece_idx: usize, + extra_height: usize, + seen: HashMap<u64, usize>, + heights: Vec<usize>, +} + +impl std::fmt::Display for Chamber { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + let absolute_pos = if let Some(piece_pos) = self.piece_pos { + self.piece() + .0 + .iter() + .map(|(row, col)| { + (*row + piece_pos.0 .0, *col + piece_pos.1 .0) + }) + .collect() + } else { + vec![] + }; + for row in self + .grid + .each_row() + .take( + absolute_pos + .iter() + .copied() + .map(|(row, _)| row.0) + .chain(std::iter::once(self.height())) + .max() + .unwrap_or(0) + + 1, + ) + .rev() + { + write!(f, "|")?; + for col in self.grid.each_col() { + if absolute_pos.iter().any(|(piece_row, piece_col)| { + row == *piece_row && col == *piece_col + }) { + write!(f, "@")?; + } else if self.grid[row][col] { + write!(f, "#")?; + } else { + write!(f, ".")?; + } + } + writeln!(f, "|")?; + } + write!(f, "|-------|")?; + Ok(()) + } +} + +impl Chamber { + fn step( + &mut self, + idx: usize, + direction: Direction, + ) -> Option<(usize, Option<usize>)> { + if self.piece_pos.is_none() { + let pos = (Row(self.height() + 3), Col(2)); + self.grid.grow(pos.0 + 4, Col(7)); + self.piece_pos = Some(pos); + } + let (mut row, mut col) = self.piece_pos.unwrap(); + + // println!("{}/{:?}", self.height(), direction); + // println!("{}", self); + // println!("*********"); + let new_col = Col(match direction { + Direction::Left => col.0.saturating_sub(1), + Direction::Right => col.0.saturating_add(1), + }); + let piece = self.piece(); + if !self.collides(piece, (row, new_col)) { + col = new_col; + self.piece_pos = Some((row, col)) + } + + // println!("{}/Down", self.height()); + // println!("{}", self); + // println!("*********"); + let collides = if row > Row(0) { + self.collides(piece, (row - 1, col)) + } else { + true + }; + if collides { + self.apply(piece, (row, col)); + self.shrink(); + self.heights.push(self.height() + self.extra_height); + let prev = self.seen_grid_hash(idx); + self.piece_pos = None; + self.piece_idx += 1; + Some((self.piece_idx - 1, prev)) + } else { + row = row - 1; + self.piece_pos = Some((row, col)); + None + } + } + + fn piece(&self) -> &'static Piece { + &PIECES[self.piece_idx % PIECES.len()] + } + + fn collides(&self, piece: &Piece, piece_pos: (Row, Col)) -> bool { + for pos in &piece.0 { + let absolute_pos = + (piece_pos.0 + pos.0 .0, piece_pos.1 + pos.1 .0); + if absolute_pos.1 >= Col(7) { + return true; + } + if self.grid[absolute_pos.0][absolute_pos.1] { + return true; + } + } + false + } + + fn apply(&mut self, piece: &Piece, piece_pos: (Row, Col)) { + for pos in &piece.0 { + let absolute_pos = + (piece_pos.0 + pos.0 .0, piece_pos.1 + pos.1 .0); + assert!(!self.grid[absolute_pos.0][absolute_pos.1]); + self.grid[absolute_pos.0][absolute_pos.1] = true; + } + } + + fn shrink(&mut self) { + let height = self + .grid + .each_col() + .map(|col| { + self.grid + .each_row() + .rev() + .find(|row| self.grid[*row][col]) + .map(|row| row.0 + 1) + .unwrap_or(0) + }) + .min() + .unwrap_or(0); + self.grid.unshift_rows(height); + self.extra_height += height; + } + + fn seen_grid_hash(&mut self, idx: usize) -> Option<usize> { + use std::hash::{Hash as _, Hasher as _}; + let mut hasher = ahash::AHasher::default(); + self.grid.hash(&mut hasher); + idx.hash(&mut hasher); + let hash = hasher.finish(); + let ret = self.seen.get(&hash).copied(); + self.seen.insert(hash, self.piece_idx); + ret + } + + fn height(&self) -> usize { + self.grid + .each_row() + .rev() + .find(|row| self.grid[*row].iter().any(|c| *c)) + .map(|row| row.0 + 1) + .unwrap_or(0) + } +} + +pub fn parse(fh: File) -> Result<Vec<Direction>> { + Ok(parse::bytes(fh) + .take_while(|c| *c == b'<' || *c == b'>') + .map(|c| c.try_into().unwrap()) + .collect()) +} + +pub fn part1(directions: Vec<Direction>) -> Result<usize> { + let mut chamber = Chamber::default(); + for (i, direction) in directions.iter().copied().enumerate().cycle() { + if let Some((dropped, prev)) = chamber.step(i, direction) { + if dropped + 1 >= 2022 { + break; + } + } + } + Ok(chamber.height() + chamber.extra_height) +} + +pub fn part2(directions: Vec<Direction>) -> Result<usize> { + let mut chamber = Chamber::default(); + for (i, direction) in directions.iter().copied().enumerate().cycle() { + if let Some((dropped, Some(prev))) = chamber.step(i, direction) { + let cycle_len = dropped - prev; + let height_diff = + chamber.heights[dropped] - chamber.heights[prev]; + let start_height = chamber.heights[prev]; + let rest = 1_000_000_000_000 - (prev + 1); + let remaining_full_cycles = rest / cycle_len; + let partial_cycle_len = rest - remaining_full_cycles * cycle_len; + let partial_height_diff = chamber.heights + [prev + partial_cycle_len] + - chamber.heights[prev]; + let height = start_height + + height_diff * remaining_full_cycles + + partial_height_diff; + return Ok(height); + } + } + unreachable!() +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 17).unwrap()).unwrap()).unwrap(), + 3083 + ); + assert_eq!( + part2(parse(parse::data(2022, 17).unwrap()).unwrap()).unwrap(), + 1532183908048 + ); +} diff --git a/src/bin/2022/main.rs b/src/bin/2022/main.rs index dff9ae4..744516a 100644 --- a/src/bin/2022/main.rs +++ b/src/bin/2022/main.rs @@ -27,6 +27,7 @@ mod day13; mod day14; mod day15; mod day16; +mod day17; // NEXT MOD #[paw::main] @@ -49,6 +50,7 @@ fn main(opt: Opt) -> Result<()> { 14 => advent_of_code::day!(2022, opt.day, opt.puzzle, day14), 15 => advent_of_code::day!(2022, opt.day, opt.puzzle, day15), 16 => advent_of_code::day!(2022, opt.day, opt.puzzle, day16), + 17 => advent_of_code::day!(2022, opt.day, opt.puzzle, day17), // NEXT PART _ => panic!("unknown day {}", opt.day), } diff --git a/src/grid.rs b/src/grid.rs index 96ac933..347c902 100644 --- a/src/grid.rs +++ b/src/grid.rs @@ -154,12 +154,12 @@ impl std::ops::Sub<ICol> for isize { } } -#[derive(Default, Clone, Debug, Eq, PartialEq)] -pub struct GridRow<T: Default + Clone + Eq + PartialEq> { +#[derive(Default, Clone, Debug, Eq, PartialEq, Hash)] +pub struct GridRow<T: Default + Clone + Eq + PartialEq + std::hash::Hash> { cells: Vec<T>, } -impl<T: Default + Clone + Eq + PartialEq> GridRow<T> { +impl<T: Default + Clone + Eq + PartialEq + std::hash::Hash> GridRow<T> { pub fn iter(&self) -> impl Iterator<Item = &T> + Clone { self.cells.iter() } @@ -169,8 +169,8 @@ impl<T: Default + Clone + Eq + PartialEq> GridRow<T> { } } -impl<T: Default + Clone + Eq + PartialEq> std::ops::Index<Col> - for GridRow<T> +impl<T: Default + Clone + Eq + PartialEq + std::hash::Hash> + std::ops::Index<Col> for GridRow<T> { type Output = T; fn index(&self, col: Col) -> &Self::Output { @@ -178,20 +178,20 @@ impl<T: Default + Clone + Eq + PartialEq> std::ops::Index<Col> } } -impl<T: Default + Clone + Eq + PartialEq> std::ops::IndexMut<Col> - for GridRow<T> +impl<T: Default + Clone + Eq + PartialEq + std::hash::Hash> + std::ops::IndexMut<Col> for GridRow<T> { fn index_mut(&mut self, col: Col) -> &mut Self::Output { &mut self.cells[col.0] } } -#[derive(Default, Clone, Debug, Eq, PartialEq)] -pub struct Grid<T: Default + Clone + Eq + PartialEq> { +#[derive(Default, Clone, Debug, Eq, PartialEq, Hash)] +pub struct Grid<T: Default + Clone + Eq + PartialEq + std::hash::Hash> { rows: Vec<GridRow<T>>, } -impl<T: Default + Clone + Eq + PartialEq> Grid<T> { +impl<T: Default + Clone + Eq + PartialEq + std::hash::Hash> Grid<T> { pub fn grow(&mut self, rows: Row, cols: Col) { self.rows .resize_with(rows.0.max(self.rows.len()), GridRow::default); @@ -201,6 +201,10 @@ impl<T: Default + Clone + Eq + PartialEq> Grid<T> { } } + pub fn unshift_rows(&mut self, count: usize) { + self.rows = self.rows.split_off(count); + } + pub fn rows(&self) -> Row { Row(self.rows.len()) } @@ -267,7 +271,15 @@ impl<T: Default + Clone + Eq + PartialEq> Grid<T> { } } -impl<T: Default + Clone + Eq + PartialEq + std::fmt::Display> Grid<T> { +impl< + T: Default + + Clone + + Eq + + PartialEq + + std::hash::Hash + + std::fmt::Display, + > Grid<T> +{ pub fn display_packed<F: Fn(&T) -> char>( &self, f: F, @@ -276,8 +288,14 @@ impl<T: Default + Clone + Eq + PartialEq + std::fmt::Display> Grid<T> { } } -impl<T: Default + Clone + Eq + PartialEq + std::fmt::Display> - std::fmt::Display for Grid<T> +impl< + T: Default + + Clone + + Eq + + PartialEq + + std::hash::Hash + + std::fmt::Display, + > std::fmt::Display for Grid<T> { fn fmt( &self, @@ -293,22 +311,26 @@ impl<T: Default + Clone + Eq + PartialEq + std::fmt::Display> } } -impl<T: Default + Clone + Eq + PartialEq> std::ops::Index<Row> for Grid<T> { +impl<T: Default + Clone + Eq + PartialEq + std::hash::Hash> + std::ops::Index<Row> for Grid<T> +{ type Output = GridRow<T>; fn index(&self, row: Row) -> &Self::Output { &self.rows[row.0] } } -impl<T: Default + Clone + Eq + PartialEq> std::ops::IndexMut<Row> - for Grid<T> +impl<T: Default + Clone + Eq + PartialEq + std::hash::Hash> + std::ops::IndexMut<Row> for Grid<T> { fn index_mut(&mut self, row: Row) -> &mut Self::Output { &mut self.rows[row.0] } } -impl<T: Default + Clone + Eq + PartialEq> FromIterator<Vec<T>> for Grid<T> { +impl<T: Default + Clone + Eq + PartialEq + std::hash::Hash> + FromIterator<Vec<T>> for Grid<T> +{ fn from_iter<I>(iter: I) -> Self where I: IntoIterator<Item = Vec<T>>, @@ -319,8 +341,8 @@ impl<T: Default + Clone + Eq + PartialEq> FromIterator<Vec<T>> for Grid<T> { } } -impl<T: Default + Clone + Eq + PartialEq> FromIterator<((Row, Col), T)> - for Grid<T> +impl<T: Default + Clone + Eq + PartialEq + std::hash::Hash> + FromIterator<((Row, Col), T)> for Grid<T> { fn from_iter<I>(iter: I) -> Self where @@ -337,13 +359,18 @@ impl<T: Default + Clone + Eq + PartialEq> FromIterator<((Row, Col), T)> pub struct DisplayPacked< 'a, - T: Default + Clone + Eq + PartialEq + std::fmt::Display, + T: Default + Clone + Eq + PartialEq + std::hash::Hash + std::fmt::Display, F: Fn(&'a T) -> char, >(&'a Grid<T>, F); impl< 'a, - T: Default + Clone + Eq + PartialEq + std::fmt::Display, + T: Default + + Clone + + Eq + + PartialEq + + std::hash::Hash + + std::fmt::Display, F: Fn(&'a T) -> char, > std::fmt::Display for DisplayPacked<'a, T, F> { diff --git a/src/parse.rs b/src/parse.rs index 1219484..6969e84 100644 --- a/src/parse.rs +++ b/src/parse.rs @@ -109,7 +109,7 @@ pub fn digit_grid(lines: impl Iterator<Item = String>) -> Grid<u8> { pub fn grid<F, T>(lines: impl Iterator<Item = String>, mut f: F) -> Grid<T> where F: FnMut(u8, Row, Col) -> T, - T: Clone + Default + Eq + PartialEq, + T: Clone + Default + Eq + PartialEq + std::hash::Hash, { lines .enumerate() |