diff options
Diffstat (limited to '2022/src/bin')
-rw-r--r-- | 2022/src/bin/day_22.rs | 411 |
1 files changed, 344 insertions, 67 deletions
diff --git a/2022/src/bin/day_22.rs b/2022/src/bin/day_22.rs index 693164d..784a608 100644 --- a/2022/src/bin/day_22.rs +++ b/2022/src/bin/day_22.rs @@ -13,8 +13,8 @@ fn main() -> Result<(), Box<dyn std::error::Error>> { let input = fs::read_to_string("inputs/day_22.txt")?; let parsed = Input::parser(&input).unwrap().1; - dbg!(State::walk_the_map(&parsed)); - dbg!(State::walk_the_map(&parsed).score()); + dbg!(State::walk_the_map(&parsed, false).score()); + dbg!(State::walk_the_map(&parsed, true).score()); Ok(()) } @@ -26,7 +26,10 @@ struct Input { } #[derive(Debug, Clone)] -struct Map(Vec<Vec<MapPoint>>); +struct Map { + grid: Vec<Vec<MapPoint>>, + portals: Vec<Portal>, +} #[derive(Debug, Clone, Copy, PartialEq, Eq)] enum MapPoint { @@ -58,7 +61,109 @@ impl Input { impl Map { fn parser(input: &str) -> IResult<&str, Self> { - map(separated_list1(line_ending, many1(MapPoint::parser)), Map)(input) + map( + separated_list1(line_ending, many1(MapPoint::parser)), + |grid| Map { + grid, + portals: Portal::add_reverse_portals(vec![ + Portal { + // A -> F + src_boundary: LineSegment { + start: Point { x: 50, y: 0 }, + end: Point { x: 99, y: 0 }, + }, + src_facing: Direction::Up, + dest_boundary: LineSegment { + start: Point { x: 0, y: 150 }, + end: Point { x: 0, y: 199 }, + }, + dest_facing: Direction::Right, + }, + Portal { + // A -> D + src_boundary: LineSegment { + start: Point { x: 50, y: 0 }, + end: Point { x: 50, y: 49 }, + }, + src_facing: Direction::Left, + dest_boundary: LineSegment { + start: Point { x: 0, y: 149 }, + end: Point { x: 0, y: 100 }, + }, + dest_facing: Direction::Right, + }, + Portal { + // B -> F + src_boundary: LineSegment { + start: Point { x: 100, y: 0 }, + end: Point { x: 149, y: 0 }, + }, + src_facing: Direction::Up, + dest_boundary: LineSegment { + start: Point { x: 0, y: 199 }, + end: Point { x: 49, y: 199 }, + }, + dest_facing: Direction::Up, + }, + Portal { + // B -> E + src_boundary: LineSegment { + start: Point { x: 149, y: 0 }, + end: Point { x: 149, y: 49 }, + }, + src_facing: Direction::Right, + dest_boundary: LineSegment { + start: Point { x: 99, y: 149 }, + end: Point { x: 99, y: 100 }, + }, + dest_facing: Direction::Left, + }, + Portal { + // B -> C + src_boundary: LineSegment { + start: Point { x: 100, y: 49 }, + end: Point { x: 149, y: 49 }, + }, + src_facing: Direction::Down, + dest_boundary: LineSegment { + start: Point { x: 99, y: 50 }, + end: Point { x: 99, y: 99 }, + }, + dest_facing: Direction::Left, + }, + Portal { + // C -> D + src_boundary: LineSegment { + start: Point { x: 50, y: 50 }, + end: Point { x: 50, y: 99 }, + }, + src_facing: Direction::Left, + dest_boundary: LineSegment { + start: Point { x: 0, y: 100 }, + end: Point { x: 49, y: 100 }, + }, + dest_facing: Direction::Down, + }, + Portal { + // E -> F + src_boundary: LineSegment { + start: Point { x: 50, y: 149 }, + end: Point { x: 99, y: 149 }, + }, + src_facing: Direction::Down, + dest_boundary: LineSegment { + start: Point { x: 49, y: 150 }, + end: Point { x: 49, y: 199 }, + }, + dest_facing: Direction::Left, + }, + // AB + // C + // DE + // F + ]), + }, + )(input) } } @@ -94,7 +199,7 @@ struct Point { y: usize, } -#[derive(Debug, Clone)] +#[derive(Debug, Clone, PartialEq, Eq)] enum Direction { Right, Down, @@ -103,25 +208,140 @@ enum Direction { } impl State { - fn walk_the_map(input: &Input) -> State { + fn walk_the_map(input: &Input, cube_wrapping: bool) -> State { let mut state = State::spawn(&input.map); for instruction in &input.instructions { - state.process_instruction(&input.map, &instruction); - dbg!((&instruction, &state)); + state.process_instruction(&input.map, &instruction, cube_wrapping); } state } fn spawn(map: &Map) -> State { let y = 0; - let x = map.0[y].iter().position(|p| p == &MapPoint::Empty).unwrap(); + let x = map.grid[y] + .iter() + .position(|p| p == &MapPoint::Empty) + .unwrap(); State { position: Point { x, y }, facing: Direction::Right, } } - fn process_instruction(&mut self, map: &Map, instruction: &Instruction) { + fn step_with_wrapping(&self, map: &Map) -> Point { + let mut next_point = self.position.clone(); + let mut made_a_step = false; + let mut hit_a_wall = false; + while !made_a_step && !hit_a_wall { + let peek = match self.facing { + Direction::Right => Point { + x: if next_point.x < map.grid[next_point.y].len() - 1 { + next_point.x + 1 + } else { + 0 + }, + ..next_point + }, + Direction::Left => Point { + x: if next_point.x > 0 { + next_point.x - 1 + } else { + map.grid[next_point.y].len() - 1 + }, + ..next_point + }, + Direction::Down => Point { + y: if next_point.y < map.grid.len() - 1 { + next_point.y + 1 + } else { + 0 + }, + ..next_point + }, + Direction::Up => Point { + y: if next_point.y > 0 { + next_point.y - 1 + } else { + map.grid.len() - 1 + }, + ..next_point + }, + }; + + let peek_value = map.grid[peek.y].get(peek.x); + match peek_value { + Some(MapPoint::Empty) => { + next_point = peek; + made_a_step = true; + } + Some(MapPoint::Void) | None => { + next_point = peek; + } + Some(MapPoint::Wall) => { + hit_a_wall = true; + } + } + } + + if hit_a_wall { + self.position.clone() + } else { + next_point + } + } + + fn step_with_cube_wrapping(&self, map: &Map) -> (Point, Direction) { + let (peek_position, peek_facing) = map + .portals + .iter() + .filter(|portal| portal.src_facing == self.facing) + .filter_map(|portal| { + portal + .src_boundary + .distance_from_start_on_line(&self.position) + .map(|distance| { + ( + portal.dest_boundary.find_point_on_line(distance), + portal.dest_facing.clone(), + ) + }) + }) + .next() + .unwrap_or_else(|| { + ( + match self.facing { + Direction::Right => Point { + x: self.position.x + 1, + ..self.position + }, + Direction::Left => Point { + x: self.position.x - 1, + ..self.position + }, + Direction::Down => Point { + y: self.position.y + 1, + ..self.position + }, + Direction::Up => Point { + y: self.position.y - 1, + ..self.position + }, + }, + self.facing.clone(), + ) + }); + + let peek_value = map.grid[peek_position.y].get(peek_position.x); + match peek_value { + Some(MapPoint::Empty) => (peek_position, peek_facing), + Some(MapPoint::Wall) => (self.position.clone(), self.facing.clone()), + Some(MapPoint::Void) | None => { + panic!("Cube wrapping shouldn't land on voids"); + } + } + } + + fn process_instruction(&mut self, map: &Map, instruction: &Instruction, cube_wrapping: bool) { match instruction { Instruction::TurnLeft => { self.facing = self.facing.spin_left(); @@ -131,63 +351,12 @@ impl State { } Instruction::Walk(amount) => { for _ in 0..*amount { - let mut next_point = self.position.clone(); - - let mut made_a_step = false; - let mut hit_a_wall = false; - while !made_a_step && !hit_a_wall { - let peek = match self.facing { - Direction::Right => Point { - x: if next_point.x < map.0[next_point.y].len() - 1 { - next_point.x + 1 - } else { - 0 - }, - ..next_point - }, - Direction::Left => Point { - x: if next_point.x > 0 { - next_point.x - 1 - } else { - map.0[next_point.y].len() - 1 - }, - ..next_point - }, - Direction::Down => Point { - y: if next_point.y < map.0.len() - 1 { - next_point.y + 1 - } else { - 0 - }, - ..next_point - }, - Direction::Up => Point { - y: if next_point.y > 0 { - next_point.y - 1 - } else { - map.0.len() - 1 - }, - ..next_point - }, - }; - - let peek_value = map.0[peek.y].get(peek.x); - match peek_value { - Some(MapPoint::Empty) => { - next_point = peek; - made_a_step = true; - } - Some(MapPoint::Void) | None => { - next_point = peek; - } - Some(MapPoint::Wall) => { - hit_a_wall = true; - } - } - } - - if !hit_a_wall { - self.position = next_point; + if cube_wrapping { + let (next_position, next_facing) = self.step_with_cube_wrapping(&map); + self.position = next_position; + self.facing = next_facing; + } else { + self.position = self.step_with_wrapping(&map); } } } @@ -222,3 +391,111 @@ impl Direction { } } } + +#[derive(Debug, Clone)] +struct Portal { + src_boundary: LineSegment, + src_facing: Direction, + dest_boundary: LineSegment, + dest_facing: Direction, +} + +#[derive(Debug, Clone)] +struct LineSegment { + start: Point, + end: Point, +} + +impl Portal { + fn add_reverse_portals(mut portals: Vec<Portal>) -> Vec<Portal> { + let mut reverse = portals + .iter() + .map(|forward_portal| Portal { + src_boundary: forward_portal.dest_boundary.clone(), + src_facing: forward_portal.dest_facing.spin_left().spin_left(), + dest_boundary: forward_portal.src_boundary.clone(), + dest_facing: forward_portal.src_facing.spin_left().spin_left(), + }) + .collect(); + portals.append(&mut reverse); + portals + } +} + +impl LineSegment { + fn distance_from_start_on_line(&self, p: &Point) -> Option<usize> { + if self.start.x == self.end.x { + if self.start.x != p.x { + None + } else { + if self.start.y < self.end.y { + if self.start.y <= p.y && self.end.y >= p.y { + Some(p.y - self.start.y) + } else { + None + } + } else { + if self.start.y >= p.y && self.end.y <= p.y { + Some(self.start.y - p.y) + } else { + None + } + } + } + } else if self.start.y == self.end.y { + if self.start.y != p.y { + None + } else { + if self.start.x < self.end.x { + if self.start.x <= p.x && self.end.x >= p.x { + Some(p.x - self.start.x) + } else { + None + } + } else { + if self.start.x >= p.x && self.end.x <= p.x { + Some(self.start.x - p.x) + } else { + None + } + } + } + } else { + unimplemented!("Oh no, we only handle straight portals") + } + } + + fn find_point_on_line(&self, distance: usize) -> Point { + if self.start.x == self.end.x { + if self.start.y < self.end.y { + assert!(self.start.y + distance <= self.end.y); + Point { + x: self.start.x, + y: self.start.y + distance, + } + } else { + assert!(self.start.y - distance >= self.end.y); + Point { + x: self.start.x, + y: self.start.y - distance, + } + } + } else if self.start.y == self.end.y { + if self.start.x < self.end.x { + assert!(self.start.x + distance <= self.end.x); + Point { + y: self.start.y, + x: self.start.x + distance, + } + } else { + assert!(self.start.x - distance >= self.end.x); + Point { + y: self.start.y, + x: self.start.x - distance, + } + } + } else { + unimplemented!("Oh no, we only handle straight portals") + } + } +} |