From abbb602726f39356b3b525b7e0f2f4f06c3e9489 Mon Sep 17 00:00:00 2001 From: Martin Ashby Date: Sun, 18 Dec 2022 23:30:44 +0000 Subject: day17 Found an approach I think will work --- src/day17.rs | 63 +++++++++++++++++++++++++++++++++++++++++++++++------------- src/main.rs | 3 ++- 2 files changed, 52 insertions(+), 14 deletions(-) diff --git a/src/day17.rs b/src/day17.rs index d8953ee..e965af6 100644 --- a/src/day17.rs +++ b/src/day17.rs @@ -1,6 +1,6 @@ //use std::{thread::{sleep}, time::Duration}; -use std::{collections::VecDeque, thread::sleep, time::Duration}; +use std::{collections::{VecDeque, HashSet, HashMap}, thread::sleep, time::Duration}; const ROCK: char = '#'; const AIR: char = '.'; @@ -42,7 +42,7 @@ impl Grid { // 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; + let tt = self.rows.len() as i64 - 200; if tt > 0 { for _ in 0..tt { let _ = self.rows.pop_front(); @@ -66,7 +66,7 @@ impl Grid { 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)}) { + if pts.contains(&Pos{x:(x as i64),y:(*y as i64)}) { print!("@"); } else { print!("{}", cell); @@ -76,17 +76,22 @@ impl Grid { } println!("+++++++ height: {} rocks: {}", self.rock_height(), rock_count); } + fn height_adjust(&mut self, x: usize) { + for mut row in self.rows.iter_mut() { + row.0 += x; + } + } } #[derive(Debug,Clone,PartialEq)] struct Pos { - x: i32, - y: i32, + x: i64, + y: i64, } impl Pos { - fn new(x:i32,y:i32) -> Pos { + fn new(x:i64,y:i64) -> Pos { Pos{x, y} } fn translate(&self, other: &Pos) -> Pos { @@ -163,7 +168,7 @@ impl Rock { // Bounds check p.y < 0 || p.x < 0 || - p.x >= Grid::WIDTH as i32 || + p.x >= Grid::WIDTH as i64 || // Intersecting another rock? grid.get(p) != AIR }) { @@ -182,17 +187,24 @@ impl Rock { } pub fn run(input: String) { - 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 rocks = vec![RockType::Bar,RockType::Cross,RockType::Ell,RockType::VBar,RockType::Square].into_iter().enumerate().cycle(); + let mut gas_jets = input.chars().enumerate().cycle(); + + let mut grid: Grid = Grid::new(); + let (mut rtypeix, mut rtype) = rocks.next().unwrap(); let mut rock = Rock{ - rtype: rocks.next().unwrap(), + rtype: rtype, pos: Pos{x: 2, y: 3} }; + let mut rock_count: usize = 1; + + let mut track: HashMap<(usize,usize),(usize,usize)> = HashMap::new(); 'lp: loop { - let push = match gas_jets.next().unwrap() { + let (gasjetix, gas_jet) = gas_jets.next().unwrap(); + let push = match gas_jet { '>' => Direction::Right, '<' => Direction::Left, dir => panic!("Unexpected jet direction! {}", dir) @@ -216,9 +228,10 @@ pub fn run(input: String) { println!("Done {} rocks...", rock_count); } // Spawn new rock + (rtypeix,rtype) = rocks.next().unwrap(); Rock { - rtype: rocks.next().unwrap(), - pos: Pos{x: 2, y: max_rock as i32 +3 } + rtype: rtype, + pos: Pos{x: 2, y: max_rock as i64 +3 } } } }; @@ -229,6 +242,30 @@ pub fn run(input: String) { // sleep(Duration::from_millis(50)); // It just isn't enough.. we need to detect the repeating pattern!!!!! or find a fast enough computer :D + let track_key = (gasjetix,rtypeix); + if let Some((prev_rock_count, prev_rock_height)) = track.get(&track_key) { + + let rcp = rock_count - *prev_rock_count; + let rhp = grid.rock_height() - *prev_rock_height; + let rco= *prev_rock_count; + let rho = *prev_rock_height; + // find max n such that + // (n * rcp) + rco <= 1_000_000_000_000; + let n:usize = (1_000_000_000_000 - rco) / rcp; + // set rock_count to P + // (n * rcp) + rco = P; + rock_count = n * rcp + rco; + // set rock_height to X + // (n * rhp) + rho = X; + let new_rock_height = (n * rhp) + rho; + let rhd = new_rock_height - grid.rock_height(); + grid.height_adjust(rhd); + rock.pos.y += rhd as i64; + println!("Periodicity encountered, zipping ahead rcp {} rhp {} rco {} rho {} n {} rock_count {} new_rock_height {} rhd {}", rcp, rhp, rco, rho, n, rock_count, new_rock_height, rhd); + grid.print(&rock, rock_count); + } else { + track.insert(track_key, (rock_count, grid.rock_height())); + } } println!("Day 17: {}", grid.rock_height()); } \ No newline at end of file diff --git a/src/main.rs b/src/main.rs index 34d8bad..47f41a7 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,5 +1,6 @@ #![feature(get_many_mut)] #![feature(iterator_try_collect)] +#![feature(int_roundings)] use std::fs; // mod day1; @@ -37,5 +38,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_ex.txt").expect("Failed to read input file!")); + day17::run(fs::read_to_string("input/day17.txt").expect("Failed to read input file!")); } -- cgit v1.2.3-ZIG