path: root/src/day17.rs

//use std::{thread::{sleep}, time::Duration};

use std::{collections::{VecDeque, HashSet, HashMap}, thread::sleep, time::Duration};

const ROCK: char = '#';
const AIR: 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 i64 - 200;
        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 i64),y:(*y as i64)}) {
                    print!("@");
                } else {
                    print!("{}", cell);
                }
            }
            print!("\n");
        }
        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: i64,
    y: i64,
}

impl Pos {
    fn new(x:i64,y:i64) -> Pos {
        Pos{x, y}
    }
    fn translate(&self, other: &Pos) -> Pos {
        Pos{x: self.x+other.x, y: self.y+other.y}
    }
}

/*
####

.#.
###
.#.

..#
..#
###

#
#
#
#

##
##
*/
#[derive(Debug,Clone,PartialEq)]
enum RockType {
    Bar,Cross,Ell,VBar,Square
}

impl RockType {
    fn points(&self) -> Vec<Pos> {
        match self {
            Self::Bar => vec![Pos::new(0,0), Pos::new(1,0), Pos::new(2,0), Pos::new(3,0)],
            Self::Cross => vec![Pos::new(1,0), Pos::new(0,1), Pos::new(1,1), Pos::new(2,1), Pos::new(1,2)],
            Self::Ell => vec![Pos::new(0,0), Pos::new(1,0), Pos::new(2,0), Pos::new(2,1), Pos::new(2,2)],
            Self::VBar => vec![Pos::new(0,0), Pos::new(0,1), Pos::new(0,2), Pos::new(0,3)],
            Self::Square => vec![Pos::new(0,0), Pos::new(0,1), Pos::new(1,0), Pos::new(1,1)],
        }
    }
}

#[derive(Debug,Clone,PartialEq)]
enum Direction {
    Down,Left,Right
}

impl Direction {
    fn unit(&self)->Pos {
        match self {
            Self::Down => Pos{x:0, y:-1},
            Self::Left => Pos{x:-1, y:0},
            Self::Right => Pos{x:1, y:0},
        }
    }
}

#[derive(Debug,Clone,PartialEq)]
struct Rock {
    rtype: RockType,
    pos: Pos, // Position of lower left point in formation
}

impl Rock {
    fn points(&self) -> Vec<Pos> {
        self.rtype.points()
            .into_iter().map(|p| {p.translate(&self.pos)}).collect()
    }
    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 >= Grid::WIDTH as i64 ||
            // Intersecting another rock?
            grid.get(p) != AIR
        }) {
            Err(self)
        } else {
            let mut nr = self.clone();
            nr.pos = self.pos.translate(&du);
            Ok(nr)
        }
    }
    pub fn solidify(self, grid: &mut Grid) {
        for pt in self.points() {
            grid.set(&pt,ROCK);
        }
    }
}

pub fn run(input: String) {
    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: 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 (gasjetix, gas_jet) = gas_jets.next().unwrap();
        let push = match gas_jet {
            '>' => Direction::Right,
            '<' => Direction::Left,
            dir => panic!("Unexpected jet direction! {}", dir)
        };
        // apply jet, ignore any error.
        rock = rock.mv(push, &mut grid).unwrap_or_else(|e| {e});
        // apply gravity
        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 rock_count == 1_000_000_000_000 {
                    break 'lp;
                }
                // Measure height...
                let max_rock = grid.rock_height();
                // remember how many rocks we did
                rock_count += 1;
                if rock_count % 1_000_000 == 0 {
                    println!("Done {} rocks...", rock_count);
                }
                // Spawn new rock
                (rtypeix,rtype) = rocks.next().unwrap();
                Rock {
                    rtype: rtype,
                    pos: Pos{x: 2, y: max_rock as i64 +3 }
                }
            }
        };
        
        grid.trim();
        // grid.print(&rock, rock_count);
        //print(&grid, &rock, rocks_count);
        // 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());
}