summaryrefslogtreecommitdiff
path: root/2022/src/bin/day_22.rs
diff options
context:
space:
mode:
Diffstat (limited to '2022/src/bin/day_22.rs')
-rw-r--r--2022/src/bin/day_22.rs501
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")
+ }
+ }
+}