Day 22 Part 2

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")
+        }
+    }
+}