From b29e650c66a3efe3cffe56ba0c41338072eac09f Mon Sep 17 00:00:00 2001 From: Martin Ashby Date: Sun, 18 Dec 2022 21:55:43 +0000 Subject: day17 pt2 But it's the wrong track, it's too slow. --- src/day17.rs | 150 ++++++++++++++++++++++++++++++++++++++--------------------- src/main.rs | 2 +- 2 files changed, 98 insertions(+), 54 deletions(-) diff --git a/src/day17.rs b/src/day17.rs index da1a6e7..d8953ee 100644 --- a/src/day17.rs +++ b/src/day17.rs @@ -1,9 +1,83 @@ //use std::{thread::{sleep}, time::Duration}; +use std::{collections::VecDeque, thread::sleep, time::Duration}; + const ROCK: char = '#'; const AIR: char = '.'; -type Grid = Vec>; +//type Grid = Vec>; +type GridRow = (usize,Vec); +struct Grid { + rows: VecDeque +} +impl Grid { + const WIDTH:usize = 7; + fn new() -> Grid { + let mut rows = VecDeque::new(); + rows.push_back((0,(0..Grid::WIDTH).map(|_| { AIR }).collect())); + Grid { rows } + } + fn iy(&mut self, p: &Pos) -> usize { + let lb = self.rows[0].0; + let y = p.y as usize; + let iy:usize = y - lb; // will fail if we try to access a trimmed blcok + // Grow on demand + if iy >= self.rows.len() { + let lr = self.rows.back().unwrap().0; + for y in (lr+1)..=y { + self.rows.push_back((y, (0..Grid::WIDTH).map(|_| { AIR }).collect())) + } + } + iy + } + fn get(&mut self, p: &Pos)->char { + let iy = self.iy(p); + self.rows[iy].1[p.x as usize] + } + fn set(&mut self, p: &Pos, x: char) { + let iy:usize = self.iy(p); + self.rows[iy].1[p.x as usize] = x; + } + fn trim(&mut self) { + // cheat, jjust keep the top 100 rows + // really we should check for impassable points + // I don't really like this solution either tbh, I want an rtruncate method... + let tt = self.rows.len() as i32 - 30; + if tt > 0 { + for _ in 0..tt { + let _ = self.rows.pop_front(); + } + } + } + fn rock_height(&self) -> usize { + self.rows.iter() + .rfind(|row| { + row.1.iter().any(|cell| {*cell == ROCK}) + }) + .map(|row| { + row.0+1 // height is one more than the index.. + }) + .unwrap_or(0) + } + fn print(&self, rock: &Rock, rock_count: usize) { + print!("{}[2J", 27 as char); // clear terminal! + println!("+++++++"); + let pts = rock.points(); + for (y ,row) in self.rows.iter().rev() { + print!("{:012} ", y); + for (x, cell) in row.iter().enumerate() { + if pts.contains(&Pos{x:(x as i32),y:(*y as i32)}) { + print!("@"); + } else { + print!("{}", cell); + } + } + print!("\n"); + } + println!("+++++++ height: {} rocks: {}", self.rock_height(), rock_count); + } + +} #[derive(Debug,Clone,PartialEq)] struct Pos { @@ -82,17 +156,16 @@ impl Rock { self.rtype.points() .into_iter().map(|p| {p.translate(&self.pos)}).collect() } - pub fn mv(self, dir: Direction, grid: &Grid) -> Result { - let width: i32 = grid[0].len() as i32; + pub fn mv(self, dir: Direction, grid: &mut Grid) -> Result { let du = dir.unit(); let np: Vec = self.points().into_iter().map(|p| {p.translate(&du)}).collect(); if np.iter().any(|p| { // Bounds check p.y < 0 || p.x < 0 || - p.x >= width || + p.x >= Grid::WIDTH as i32 || // Intersecting another rock? - grid[p.y as usize][p.x as usize] != AIR + grid.get(p) != AIR }) { Err(self) } else { @@ -101,55 +174,23 @@ impl Rock { Ok(nr) } } - pub fn solidify(self, grid: &mut Vec>) { + pub fn solidify(self, grid: &mut Grid) { for pt in self.points() { - grid[pt.y as usize][pt.x as usize] = ROCK; + grid.set(&pt,ROCK); } } } -fn rock_height(grid: &Grid) -> usize { - grid.iter().enumerate() - .rfind(|row| { - row.1.iter().any(|cell| {*cell == ROCK}) - }) - .map(|row| { - row.0+1 // height is one more than the index.. - }) - .unwrap_or(0) -} - -// fn print(grid: &Grid, rock: &Rock, rock_count: usize) { -// print!("{}[2J", 27 as char); // clear terminal! -// println!("+++++++"); -// let pts = rock.points(); -// for (y ,row) in grid.iter().enumerate().rev() { -// for (x, cell) in row.iter().enumerate() { -// if pts.contains(&Pos{x:(x as i32),y:(y as i32)}) { -// print!("@"); -// } else { -// print!("{}", cell); -// } -// } -// print!("\n"); -// } -// println!("+++++++ height: {} rocks: {}", rock_height(grid), rock_count); -// } - pub fn run(input: String) { - let initial_height = 6; - let width = 7; let mut rocks = vec![RockType::Bar,RockType::Cross,RockType::Ell,RockType::VBar,RockType::Square].into_iter().cycle(); let mut gas_jets = input.chars().cycle(); - let mut grid: Grid = (0..initial_height).map(|_| { - (0..width).map(|_| {AIR}).collect() - }).collect(); + let mut grid: Grid = Grid::new(); let mut rock = Rock{ rtype: rocks.next().unwrap(), pos: Pos{x: 2, y: 3} }; - let mut rocks_count: usize = 1; + let mut rock_count: usize = 1; 'lp: loop { let push = match gas_jets.next().unwrap() { '>' => Direction::Right, @@ -157,25 +198,23 @@ pub fn run(input: String) { dir => panic!("Unexpected jet direction! {}", dir) }; // apply jet, ignore any error. - rock = rock.mv(push, &grid).unwrap_or_else(|e| {e}); + rock = rock.mv(push, &mut grid).unwrap_or_else(|e| {e}); // apply gravity - rock = match rock.mv(Direction::Down, &grid) { + rock = match rock.mv(Direction::Down, &mut grid) { Ok(rr) => rr, // Complete the move! Err(rr) => { // We didn't move, solidify! rr.solidify(&mut grid); - if rocks_count == 2022 { + if rock_count == 1_000_000_000_000 { break 'lp; } // Measure height... - let max_rock = rock_height(&grid); - // Extend grid to max_rock + 7 (enough room for any new rocks at a height of at least 3 over the old ones) - let ext = (max_rock+7)-grid.len(); - if ext > 0 { - grid.extend((0..ext).map(|_| { (0..width).map(|_| { AIR }).collect() })); - } + let max_rock = grid.rock_height(); // remember how many rocks we did - rocks_count += 1; + rock_count += 1; + if rock_count % 1_000_000 == 0 { + println!("Done {} rocks...", rock_count); + } // Spawn new rock Rock { rtype: rocks.next().unwrap(), @@ -183,8 +222,13 @@ pub fn run(input: String) { } } }; + + grid.trim(); + // grid.print(&rock, rock_count); //print(&grid, &rock, rocks_count); - //sleep(Duration::from_millis(100)); + // sleep(Duration::from_millis(50)); + + // It just isn't enough.. we need to detect the repeating pattern!!!!! or find a fast enough computer :D } - println!("Day 17: {}", rock_height(&grid)); + println!("Day 17: {}", grid.rock_height()); } \ No newline at end of file diff --git a/src/main.rs b/src/main.rs index a40ab53..34d8bad 100644 --- a/src/main.rs +++ b/src/main.rs @@ -37,5 +37,5 @@ fn main() { // day14::run(fs::read_to_string("input/day14.txt").expect("Failed to read input file!")); // day15::run(fs::read_to_string("input/day15.txt").expect("Failed to read input file!")); // day16::run(fs::read_to_string("input/day16.txt").expect("Failed to read input file!")); - day17::run(fs::read_to_string("input/day17.txt").expect("Failed to read input file!")); + day17::run(fs::read_to_string("input/day17_ex.txt").expect("Failed to read input file!")); } -- cgit v1.2.3-ZIG