day17.rs (8172B)
1 //use std::{thread::{sleep}, time::Duration}; 2 3 use std::{collections::{VecDeque, HashSet, HashMap}, thread::sleep, time::Duration}; 4 5 const ROCK: char = '#'; 6 const AIR: char = '.'; 7 8 //type Grid = Vec<Vec<char>>; 9 type GridRow = (usize,Vec<char>); 10 struct Grid { 11 rows: VecDeque<GridRow> 12 } 13 impl Grid { 14 const WIDTH:usize = 7; 15 fn new() -> Grid { 16 let mut rows = VecDeque::new(); 17 rows.push_back((0,(0..Grid::WIDTH).map(|_| { AIR }).collect())); 18 Grid { rows } 19 } 20 fn iy(&mut self, p: &Pos) -> usize { 21 let lb = self.rows[0].0; 22 let y = p.y as usize; 23 let iy:usize = y - lb; // will fail if we try to access a trimmed blcok 24 // Grow on demand 25 if iy >= self.rows.len() { 26 let lr = self.rows.back().unwrap().0; 27 for y in (lr+1)..=y { 28 self.rows.push_back((y, (0..Grid::WIDTH).map(|_| { AIR }).collect())) 29 } 30 } 31 iy 32 } 33 fn get(&mut self, p: &Pos)->char { 34 let iy = self.iy(p); 35 self.rows[iy].1[p.x as usize] 36 } 37 fn set(&mut self, p: &Pos, x: char) { 38 let iy:usize = self.iy(p); 39 self.rows[iy].1[p.x as usize] = x; 40 } 41 fn trim(&mut self) { 42 // cheat, jjust keep the top 100 rows 43 // really we should check for impassable points 44 // I don't really like this solution either tbh, I want an rtruncate method... 45 let tt = self.rows.len() as i64 - 200; 46 if tt > 0 { 47 for _ in 0..tt { 48 let _ = self.rows.pop_front(); 49 } 50 } 51 } 52 fn rock_height(&self) -> usize { 53 self.rows.iter() 54 .rfind(|row| { 55 row.1.iter().any(|cell| {*cell == ROCK}) 56 }) 57 .map(|row| { 58 row.0+1 // height is one more than the index.. 59 }) 60 .unwrap_or(0) 61 } 62 fn print(&self, rock: &Rock, rock_count: usize) { 63 print!("{}[2J", 27 as char); // clear terminal! 64 println!("+++++++"); 65 let pts = rock.points(); 66 for (y ,row) in self.rows.iter().rev() { 67 print!("{:012} ", y); 68 for (x, cell) in row.iter().enumerate() { 69 if pts.contains(&Pos{x:(x as i64),y:(*y as i64)}) { 70 print!("@"); 71 } else { 72 print!("{}", cell); 73 } 74 } 75 print!("\n"); 76 } 77 println!("+++++++ height: {} rocks: {}", self.rock_height(), rock_count); 78 } 79 fn height_adjust(&mut self, x: usize) { 80 for mut row in self.rows.iter_mut() { 81 row.0 += x; 82 } 83 } 84 85 } 86 87 #[derive(Debug,Clone,PartialEq)] 88 struct Pos { 89 x: i64, 90 y: i64, 91 } 92 93 impl Pos { 94 fn new(x:i64,y:i64) -> Pos { 95 Pos{x, y} 96 } 97 fn translate(&self, other: &Pos) -> Pos { 98 Pos{x: self.x+other.x, y: self.y+other.y} 99 } 100 } 101 102 /* 103 #### 104 105 .#. 106 ### 107 .#. 108 109 ..# 110 ..# 111 ### 112 113 # 114 # 115 # 116 # 117 118 ## 119 ## 120 */ 121 #[derive(Debug,Clone,PartialEq)] 122 enum RockType { 123 Bar,Cross,Ell,VBar,Square 124 } 125 126 impl RockType { 127 fn points(&self) -> Vec<Pos> { 128 match self { 129 Self::Bar => vec![Pos::new(0,0), Pos::new(1,0), Pos::new(2,0), Pos::new(3,0)], 130 Self::Cross => vec![Pos::new(1,0), Pos::new(0,1), Pos::new(1,1), Pos::new(2,1), Pos::new(1,2)], 131 Self::Ell => vec![Pos::new(0,0), Pos::new(1,0), Pos::new(2,0), Pos::new(2,1), Pos::new(2,2)], 132 Self::VBar => vec![Pos::new(0,0), Pos::new(0,1), Pos::new(0,2), Pos::new(0,3)], 133 Self::Square => vec![Pos::new(0,0), Pos::new(0,1), Pos::new(1,0), Pos::new(1,1)], 134 } 135 } 136 } 137 138 #[derive(Debug,Clone,PartialEq)] 139 enum Direction { 140 Down,Left,Right 141 } 142 143 impl Direction { 144 fn unit(&self)->Pos { 145 match self { 146 Self::Down => Pos{x:0, y:-1}, 147 Self::Left => Pos{x:-1, y:0}, 148 Self::Right => Pos{x:1, y:0}, 149 } 150 } 151 } 152 153 #[derive(Debug,Clone,PartialEq)] 154 struct Rock { 155 rtype: RockType, 156 pos: Pos, // Position of lower left point in formation 157 } 158 159 impl Rock { 160 fn points(&self) -> Vec<Pos> { 161 self.rtype.points() 162 .into_iter().map(|p| {p.translate(&self.pos)}).collect() 163 } 164 pub fn mv(self, dir: Direction, grid: &mut Grid) -> Result<Self,Self> { 165 let du = dir.unit(); 166 let np: Vec<Pos> = self.points().into_iter().map(|p| {p.translate(&du)}).collect(); 167 if np.iter().any(|p| { 168 // Bounds check 169 p.y < 0 || 170 p.x < 0 || 171 p.x >= Grid::WIDTH as i64 || 172 // Intersecting another rock? 173 grid.get(p) != AIR 174 }) { 175 Err(self) 176 } else { 177 let mut nr = self.clone(); 178 nr.pos = self.pos.translate(&du); 179 Ok(nr) 180 } 181 } 182 pub fn solidify(self, grid: &mut Grid) { 183 for pt in self.points() { 184 grid.set(&pt,ROCK); 185 } 186 } 187 } 188 189 pub fn run(input: String) { 190 let mut rocks = vec![RockType::Bar,RockType::Cross,RockType::Ell,RockType::VBar,RockType::Square].into_iter().enumerate().cycle(); 191 let mut gas_jets = input.chars().enumerate().cycle(); 192 193 194 let mut grid: Grid = Grid::new(); 195 196 let (mut rtypeix, mut rtype) = rocks.next().unwrap(); 197 let mut rock = Rock{ 198 rtype: rtype, 199 pos: Pos{x: 2, y: 3} 200 }; 201 202 let mut rock_count: usize = 1; 203 204 let mut track: HashMap<(usize,usize),(usize,usize)> = HashMap::new(); 205 'lp: loop { 206 let (gasjetix, gas_jet) = gas_jets.next().unwrap(); 207 let push = match gas_jet { 208 '>' => Direction::Right, 209 '<' => Direction::Left, 210 dir => panic!("Unexpected jet direction! {}", dir) 211 }; 212 // apply jet, ignore any error. 213 rock = rock.mv(push, &mut grid).unwrap_or_else(|e| {e}); 214 // apply gravity 215 rock = match rock.mv(Direction::Down, &mut grid) { 216 Ok(rr) => rr, // Complete the move! 217 Err(rr) => { 218 // We didn't move, solidify! 219 rr.solidify(&mut grid); 220 if rock_count == 1_000_000_000_000 { 221 break 'lp; 222 } 223 // Measure height... 224 let max_rock = grid.rock_height(); 225 // remember how many rocks we did 226 rock_count += 1; 227 if rock_count % 1_000_000 == 0 { 228 println!("Done {} rocks...", rock_count); 229 } 230 // Spawn new rock 231 (rtypeix,rtype) = rocks.next().unwrap(); 232 Rock { 233 rtype: rtype, 234 pos: Pos{x: 2, y: max_rock as i64 +3 } 235 } 236 } 237 }; 238 239 grid.trim(); 240 // grid.print(&rock, rock_count); 241 //print(&grid, &rock, rocks_count); 242 // sleep(Duration::from_millis(50)); 243 244 // It just isn't enough.. we need to detect the repeating pattern!!!!! or find a fast enough computer :D 245 let track_key = (gasjetix,rtypeix); 246 if let Some((prev_rock_count, prev_rock_height)) = track.get(&track_key) { 247 248 let rcp = rock_count - *prev_rock_count; 249 let rhp = grid.rock_height() - *prev_rock_height; 250 let rco= *prev_rock_count; 251 let rho = *prev_rock_height; 252 // find max n such that 253 // (n * rcp) + rco <= 1_000_000_000_000; 254 let n:usize = (1_000_000_000_000 - rco) / rcp; 255 // set rock_count to P 256 // (n * rcp) + rco = P; 257 rock_count = n * rcp + rco; 258 // set rock_height to X 259 // (n * rhp) + rho = X; 260 let new_rock_height = (n * rhp) + rho; 261 let rhd = new_rock_height - grid.rock_height(); 262 grid.height_adjust(rhd); 263 rock.pos.y += rhd as i64; 264 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); 265 grid.print(&rock, rock_count); 266 } else { 267 track.insert(track_key, (rock_count, grid.rock_height())); 268 } 269 } 270 println!("Day 17: {}", grid.rock_height()); 271 }