diff options
Diffstat (limited to '2024_rust/src/bin/day15.rs')
| -rw-r--r-- | 2024_rust/src/bin/day15.rs | 299 |
1 files changed, 299 insertions, 0 deletions
diff --git a/2024_rust/src/bin/day15.rs b/2024_rust/src/bin/day15.rs new file mode 100644 index 0000000..02e688d --- /dev/null +++ b/2024_rust/src/bin/day15.rs @@ -0,0 +1,299 @@ +use aoc2024::matrix; +use regex::Regex; +use std::collections::HashSet; +use std::fmt; +use std::{thread, time}; + +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +enum Direction { + Up, + Right, + Down, + Left, +} +use Direction::*; + +impl fmt::Display for Direction { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let ch = match self { + Up => "^", + Right => ">", + Down => "v", + Left => "<", + }; + write!(f, "{}", ch) + } +} + +impl Direction { + fn parse(c: char) -> Direction { + match c { + '^' => Up, + '>' => Right, + 'v' => Down, + '<' => Left, + _ => panic!("Invalid input"), + } + } + + fn offset(&self) -> (isize, isize) { + match self { + Up => (-1, 0), + Right => (0, 1), + Down => (1, 0), + Left => (0, -1), + } + } +} + +#[derive(Debug, Clone, Copy)] +enum Dot { + Robot, + Empty, + Wall, + // Box, + WideBox(bool), +} +use Dot::*; + +impl fmt::Display for Dot { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let ch = match self { + Robot => "@", + Empty => ".", + Wall => "#", + // Box => "O", + WideBox(false) => "[", + WideBox(true) => "]", + }; + write!(f, "{}", ch) + } +} + +impl Dot { + fn parse(c: char) -> Dot { + match c { + '@' => Robot, + '.' => Empty, + '#' => Wall, + // 'O' => Box, + '[' => WideBox(false), + ']' => WideBox(true), + c => panic!("Invalid char '{}'", c), + } + } +} + +#[derive(Clone)] +struct M { + matrix: matrix::Matrix<Dot>, + robot: matrix::Pos, + moves: Vec<Direction>, +} + +impl fmt::Display for M { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "{}", self.matrix)?; + writeln!(f, "[Robot: {:?}]", self.robot) + // write!( + // f, + // "{}", + // self.moves + // .iter() + // .map(Direction::to_string) + // .collect::<Vec<_>>() + // .join("") + // ) + } +} + +impl M { + // fn new(text: &str) -> Self { + // let re = Regex::new(r"([#.O@\n]*)\n([>v<^\n]*)").unwrap(); + // let (_full, [matrix, moves]) = re.captures(text).unwrap().extract(); + + // let matrix = matrix::Matrix::new(matrix, Dot::parse); + // let mut robot = (0, 0); + // for i in 0..matrix.limit.0 { + // for j in 0..matrix.limit.1 { + // if let Robot = matrix.get((i, j)) { + // robot = (i, j); + // break; + // } + // } + // } + + // let mut moves: Vec<Direction> = moves + // .chars() + // .filter(|&c| c != '\n') + // .map(Direction::parse) + // .collect(); + + // moves.reverse(); + + // M { + // matrix, + // robot, + // moves, + // } + // } + + fn new_wide(text: &str) -> Self { + let re = Regex::new(r"([#.O@\n]*)\n([>v<^\n]*)").unwrap(); + let (_full, [matrix, moves]) = re.captures(text).unwrap().extract(); + + let wide_matrix: String = matrix + .chars() + .flat_map(|c| { + if c == 'O' { + vec!['[', ']'] + } else if c == '@' { + vec!['@', '.'] + } else if c == '\n' { + vec!['\n'] + } else { + vec![c, c] + } + }) + .collect(); + + let matrix = matrix::Matrix::new(&wide_matrix, Dot::parse); + let mut robot = (0, 0); + for i in 0..matrix.limit.0 { + for j in 0..matrix.limit.1 { + if let Robot = matrix.get((i, j)) { + robot = (i, j); + break; + } + } + } + + let mut moves: Vec<Direction> = moves + .chars() + .filter(|&c| c != '\n') + .map(Direction::parse) + .collect(); + + moves.reverse(); + + M { + matrix, + robot, + moves, + } + } + + fn coordinates(&self) -> u32 { + let mut result = 0; + for i in 0..self.matrix.limit.0 { + for j in 0..self.matrix.limit.1 { + if let WideBox(false) = self.matrix.get((i, j)) { + let coords = i * 100 + j; + result += coords; + } + } + } + result as u32 + } + + fn swap(&mut self, p1: matrix::Pos, p2: matrix::Pos) { + let p1v = *self.matrix.get(p1); + let p2v = *self.matrix.get(p2); + self.put(p1, p2v); + self.put(p2, p1v); + } + + fn put(&mut self, p: matrix::Pos, val: Dot) { + self.matrix.set(p, val); + if let Robot = val { + self.robot = p; + } + } + + fn step(&mut self) -> bool { + let Some(dir) = self.moves.pop() else { + return false; + }; + let nextp = offset(self.robot, dir); + match self.matrix.get(nextp) { + Wall => (), + Robot => { + panic!("Dude this makes no sense. I mean, how could the robot bump into himself?") + } + Empty => self.swap(self.robot, nextp), + WideBox(half) => { + let mut ps: HashSet<matrix::Pos> = HashSet::new(); + ps.insert(nextp); + + // Add "untouched" side when pushing a box vertically + if [Up, Down].contains(&dir) { + let non_pushing_side_dir = if *half { Left } else { Right }; + ps.insert(offset(nextp, non_pushing_side_dir)); + } + let mut swaps: Vec<(matrix::Pos, matrix::Pos)> = vec![(self.robot, nextp)]; + + loop { + let mut newps: HashSet<matrix::Pos> = HashSet::new(); + for curr in ps { + let next = offset(curr, dir); + match self.matrix.get(next) { + Wall => return true, + Robot => { + panic!("Please stop") + } + Empty => swaps.push((curr, next)), + WideBox(half) => { + swaps.push((curr, next)); + newps.insert(next); + let non_pushing_side_dir = if *half { Left } else { Right }; + let non_pushing_side = offset(next, non_pushing_side_dir); + if [Up, Down].contains(&dir) { + newps.insert(non_pushing_side); + } + } + } + } + if newps.is_empty() { + break; + } + ps = newps; + } + while let Some((p1, p2)) = swaps.pop() { + self.swap(p1, p2); + } + } + } + true + } +} + +fn offset((x, y): matrix::Pos, d: Direction) -> matrix::Pos { + let (dx, dy) = d.offset(); + (x.saturating_add_signed(dx), y.saturating_add_signed(dy)) +} + +fn p1(_input: &str) -> String { + // let mut m = M::new(input); + // println!("{m}"); + // while m.step() {} + // println!("{m}"); + + let result = "(uncomment code)"; + result.to_string() +} + +fn p2(input: &str) -> String { + let mut m = M::new_wide(input); + println!("{m}"); + while m.step() { + println!("{m}"); + thread::sleep(time::Duration::from_millis(20)); + } + + let result = m.coordinates(); + result.to_string() +} + +fn main() { + aoc2024::run_day("15", p1, p2); +} |