diff options
Diffstat (limited to '2022/src/bin/day_22.rs')
-rw-r--r-- | 2022/src/bin/day_22.rs | 501 |
1 files changed, 501 insertions, 0 deletions
diff --git a/2022/src/bin/day_22.rs b/2022/src/bin/day_22.rs new file mode 100644 index 0000000..784a608 --- /dev/null +++ b/2022/src/bin/day_22.rs @@ -0,0 +1,501 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{line_ending, u32}, + combinator::{map, value}, + multi::{many1, separated_list1}, + sequence::tuple, + IResult, +}; +use std::fs; + +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, false).score()); + dbg!(State::walk_the_map(&parsed, true).score()); + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Input { + map: Map, + instructions: Vec<Instruction>, +} + +#[derive(Debug, Clone)] +struct Map { + grid: Vec<Vec<MapPoint>>, + portals: Vec<Portal>, +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +enum MapPoint { + Wall, + Empty, + Void, +} + +#[derive(Debug, Clone)] +enum Instruction { + TurnLeft, + TurnRight, + Walk(u32), +} + +impl Input { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple(( + Map::parser, + line_ending, + line_ending, + many1(Instruction::parser), + )), + |(map, _, _, instructions)| Input { map, instructions }, + )(input) + } +} + +impl Map { + fn parser(input: &str) -> IResult<&str, Self> { + 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) + } +} + +impl MapPoint { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + value(MapPoint::Wall, tag("#")), + value(MapPoint::Empty, tag(".")), + value(MapPoint::Void, tag(" ")), + ))(input) + } +} + +impl Instruction { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + value(Instruction::TurnLeft, tag("L")), + value(Instruction::TurnRight, tag("R")), + map(u32, Instruction::Walk), + ))(input) + } +} + +#[derive(Debug, Clone)] +struct State { + position: Point, + facing: Direction, +} + +#[derive(Debug, Clone)] +struct Point { + x: usize, + y: usize, +} + +#[derive(Debug, Clone, PartialEq, Eq)] +enum Direction { + Right, + Down, + Left, + Up, +} + +impl 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, cube_wrapping); + } + state + } + + fn spawn(map: &Map) -> State { + let y = 0; + let x = map.grid[y] + .iter() + .position(|p| p == &MapPoint::Empty) + .unwrap(); + State { + position: Point { x, y }, + facing: Direction::Right, + } + } + + 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(); + } + Instruction::TurnRight => { + self.facing = self.facing.spin_right(); + } + Instruction::Walk(amount) => { + for _ in 0..*amount { + 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); + } + } + } + } + } + + fn score(&self) -> usize { + (self.position.y + 1) * 1000 + (self.position.x + 1) * 4 + self.facing.score() + } +} + +impl Direction { + fn spin_left(&self) -> Direction { + match self { + Direction::Right => Direction::Up, + Direction::Down => Direction::Right, + Direction::Left => Direction::Down, + Direction::Up => Direction::Left, + } + } + + fn spin_right(&self) -> Direction { + self.spin_left().spin_left().spin_left() + } + + fn score(&self) -> usize { + match self { + Direction::Right => 0, + Direction::Down => 1, + Direction::Left => 2, + Direction::Up => 3, + } + } +} + +#[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") + } + } +} |