day17 pt2

But it's the wrong track, it's too slow.

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<Vec<char>>;
+//type Grid = Vec<Vec<char>>;
+type GridRow = (usize,Vec<char>);
+struct Grid {
+    rows: VecDeque<GridRow>
+}
+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<Self,Self> {
-        let width: i32 = grid[0].len() as i32;
+    pub fn mv(self, dir: Direction, grid: &mut Grid) -> Result<Self,Self> {
         let du = dir.unit();
         let np: Vec<Pos> = 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<Vec<char>>) {
+    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!"));
 }