main.rs

use std::fmt::Display;

pub fn main() {
    let data = include_str!("input.txt");
    println!("Part 1: {}", part_one::<200, 150>(data, false));
    println!("Part 2: {}", part_two::<200, 150>(data, false));
}

fn part_one<const R: usize, const C: usize>(data: &'static str, test: bool) -> usize {
    let mut gps = Gps::<R, C>::new(data, 1, test);
    gps.step_all();
    println!("{gps}");
    gps.password()
}

fn part_two<const R: usize, const C: usize>(data: &'static str, test: bool) -> usize {
    let mut gps = Gps::<R, C>::new(data, 2, test);
    gps.step_all();
    println!("{gps}");
    gps.password()
}

#[derive(Debug)]
struct Gps<const R: usize, const C: usize> {
    map: [[MapSquare; C]; R],
    edges: [EdgeMapping; 14],
    location: Location,
    directions: &'static [u8],
    direction_index: usize,
}

impl<const R: usize, const C: usize> Display for Gps<R, C> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        for (i, row) in self.map.iter().enumerate() {
            for (j, elem) in row.iter().enumerate() {
                if [j, i] == self.location.point {
                    match self.location.direction {
                        Direction::Up => write!(f, "^")?,
                        Direction::Down => write!(f, "v")?,
                        Direction::Right => write!(f, ">")?,
                        Direction::Left => write!(f, "<")?,
                    }
                } else {
                    match elem {
                        MapSquare::Blank => write!(f, " ")?,
                        MapSquare::Open => write!(f, ".")?,
                        MapSquare::Wall => write!(f, "#")?,
                    }
                }
            }
            writeln!(f)?;
        }
        Ok(())
    }
}

impl<const R: usize, const C: usize> Gps<R, C> {
    fn new(data: &'static str, part: u8, test: bool) -> Self {
        let mut map = [[MapSquare::Blank; C]; R];
        let mut found = false;
        let mut loc = 0;

        let (map_data, directions) = data.split_once("\n\n").unwrap();
        for (row, line) in map_data.lines().enumerate() {
            for (i, c) in line.char_indices() {
                match c {
                    ' ' => (),
                    '.' => {
                        if row == 0 && !found {
                            loc = i;
                            found = true;
                        }
                        map[row][i] = MapSquare::Open;
                    }
                    '#' => map[row][i] = MapSquare::Wall,
                    _ => unreachable!(),
                }
            }
        }
        Self {
            map,
            location: Location {
                point: [loc, 0],
                direction: Direction::Right,
            },
            edges: Self::build_edges(part, test),
            directions: directions.trim().as_bytes(),
            direction_index: 0,
        }
    }

    fn build_edges(part: u8, test: bool) -> [EdgeMapping; 14] {
        if test {
            Self::build_edges_test(part)
        } else {
            Self::build_edges_full(part)
        }
    }

    fn build_edges_test(part: u8) -> [EdgeMapping; 14] {
        let e1 = Edge {
            from: [8, 0],
            to: [11, 0],
            direction: Direction::Up,
        };
        let e2 = Edge {
            from: [11, 0],
            to: [11, 3],
            direction: Direction::Right,
        };
        let e3 = Edge {
            from: [11, 4],
            to: [11, 7],
            direction: Direction::Right,
        };
        let e4 = Edge {
            from: [12, 8],
            to: [15, 8],
            direction: Direction::Up,
        };
        let e5 = Edge {
            from: [15, 8],
            to: [15, 11],
            direction: Direction::Right,
        };
        let e6 = Edge {
            from: [15, 11],
            to: [12, 11],
            direction: Direction::Down,
        };
        let e7 = Edge {
            from: [11, 11],
            to: [8, 11],
            direction: Direction::Down,
        };
        let e8 = Edge {
            from: [8, 11],
            to: [8, 8],
            direction: Direction::Left,
        };
        let e9 = Edge {
            from: [7, 7],
            to: [4, 7],
            direction: Direction::Down,
        };
        let e10 = Edge {
            from: [3, 7],
            to: [0, 7],
            direction: Direction::Down,
        };
        let e11 = Edge {
            from: [0, 7],
            to: [0, 4],
            direction: Direction::Left,
        };
        let e12 = Edge {
            from: [0, 4],
            to: [3, 4],
            direction: Direction::Up,
        };
        let e13 = Edge {
            from: [4, 4],
            to: [7, 4],
            direction: Direction::Up,
        };
        let e14 = Edge {
            from: [8, 3],
            to: [8, 0],
            direction: Direction::Left,
        };
        if part == 1 {
            [
                EdgeMapping::new(e1, e7),
                EdgeMapping::new(e2, e14),
                EdgeMapping::new(e3, e11),
                EdgeMapping::new(e4, e6),
                EdgeMapping::new(e5, e8),
                EdgeMapping::new(e6, e4),
                EdgeMapping::new(e7, e1),
                EdgeMapping::new(e8, e5),
                EdgeMapping::new(e9, e13),
                EdgeMapping::new(e10, e12),
                EdgeMapping::new(e11, e3),
                EdgeMapping::new(e12, e10),
                EdgeMapping::new(e13, e9),
                EdgeMapping::new(e14, e2),
            ]
        } else {
            [
                EdgeMapping::new(e1, e12),
                EdgeMapping::new(e2, e5),
                EdgeMapping::new(e3, e4),
                EdgeMapping::new(e4, e3),
                EdgeMapping::new(e5, e2),
                EdgeMapping::new(e6, e11),
                EdgeMapping::new(e7, e10),
                EdgeMapping::new(e8, e9),
                EdgeMapping::new(e9, e8),
                EdgeMapping::new(e10, e7),
                EdgeMapping::new(e11, e6),
                EdgeMapping::new(e12, e1),
                EdgeMapping::new(e13, e14),
                EdgeMapping::new(e14, e13),
            ]
        }
    }

    fn build_edges_full(part: u8) -> [EdgeMapping; 14] {
        let e1 = Edge {
            from: [50, 0],
            to: [99, 0],
            direction: Direction::Up,
        };
        let e2 = Edge {
            from: [100, 0],
            to: [149, 0],
            direction: Direction::Up,
        };
        let e3 = Edge {
            from: [149, 0],
            to: [149, 49],
            direction: Direction::Right,
        };
        let e4 = Edge {
            from: [149, 49],
            to: [100, 49],
            direction: Direction::Down,
        };
        let e5 = Edge {
            from: [99, 50],
            to: [99, 99],
            direction: Direction::Right,
        };
        let e6 = Edge {
            from: [99, 100],
            to: [99, 149],
            direction: Direction::Right,
        };
        let e7 = Edge {
            from: [99, 149],
            to: [50, 149],
            direction: Direction::Down,
        };
        let e8 = Edge {
            from: [49, 150],
            to: [49, 199],
            direction: Direction::Right,
        };
        let e9 = Edge {
            from: [49, 199],
            to: [0, 199],
            direction: Direction::Down,
        };
        let e10 = Edge {
            from: [0, 199],
            to: [0, 150],
            direction: Direction::Left,
        };
        let e11 = Edge {
            from: [0, 149],
            to: [0, 100],
            direction: Direction::Left,
        };
        let e12 = Edge {
            from: [0, 100],
            to: [49, 100],
            direction: Direction::Up,
        };
        let e13 = Edge {
            from: [50, 99],
            to: [50, 50],
            direction: Direction::Left,
        };
        let e14 = Edge {
            from: [50, 49],
            to: [50, 0],
            direction: Direction::Left,
        };
        if part == 1 {
            [
                EdgeMapping::new(e1, e7),
                EdgeMapping::new(e2, e4),
                EdgeMapping::new(e3, e14),
                EdgeMapping::new(e4, e2),
                EdgeMapping::new(e5, e13),
                EdgeMapping::new(e6, e11),
                EdgeMapping::new(e7, e1),
                EdgeMapping::new(e8, e10),
                EdgeMapping::new(e9, e12),
                EdgeMapping::new(e10, e8),
                EdgeMapping::new(e11, e6),
                EdgeMapping::new(e12, e9),
                EdgeMapping::new(e13, e5),
                EdgeMapping::new(e14, e3),
            ]
        } else {
            [
                EdgeMapping::new(e1, e10),
                EdgeMapping::new(e2, e9),
                EdgeMapping::new(e3, e6),
                EdgeMapping::new(e4, e5),
                EdgeMapping::new(e5, e4),
                EdgeMapping::new(e6, e3),
                EdgeMapping::new(e7, e8),
                EdgeMapping::new(e8, e7),
                EdgeMapping::new(e9, e2),
                EdgeMapping::new(e10, e1),
                EdgeMapping::new(e11, e14),
                EdgeMapping::new(e12, e13),
                EdgeMapping::new(e13, e12),
                EdgeMapping::new(e14, e11),
            ]
        }
    }

    fn password(&self) -> usize {
        let x = self.location.point[0] + 1;
        let y = self.location.point[1] + 1;
        match self.location.direction {
            Direction::Right => 1_000 * y + 4 * x,
            Direction::Down => 1_000 * y + 4 * x + 1,
            Direction::Left => 1_000 * y + 4 * x + 2,
            Direction::Up => 1_000 * y + 4 * x + 3,
        }
    }

    fn step_all(&mut self) {
        while self.direction_index < self.directions.len() {
            self.step();
        }
    }

    fn step(&mut self) {
        match self.get_next_direction() {
            DirectionNum::Dir(d) => self.location.direction = d,
            DirectionNum::Num(v) => {
                for _ in 0..v {
                    let next = self.get_next_cell();
                    let point = next.point;
                    if self.map[point[1]][point[0]] == MapSquare::Wall {
                        return;
                    }
                    self.location = next;
                }
            }
        }
    }

    fn get_next_cell(&self) -> Location {
        for mapping in self.edges {
            if mapping.from.on_edge(self.location) {
                return mapping.jump(self.location.point);
            }
        }
        let x = self.location.point[0];
        let y = self.location.point[1];
        match self.location.direction {
            Direction::Up => Location {
                point: [x, y - 1],
                direction: Direction::Up,
            },
            Direction::Right => Location {
                point: [x + 1, y],
                direction: Direction::Right,
            },
            Direction::Down => Location {
                point: [x, y + 1],
                direction: Direction::Down,
            },
            Direction::Left => Location {
                point: [x - 1, y],
                direction: Direction::Left,
            },
        }
    }

    fn get_next_direction(&mut self) -> DirectionNum {
        match self.directions[self.direction_index] {
            b'R' => {
                self.direction_index += 1;
                match self.location.direction {
                    Direction::Up => DirectionNum::Dir(Direction::Right),
                    Direction::Right => DirectionNum::Dir(Direction::Down),
                    Direction::Down => DirectionNum::Dir(Direction::Left),
                    Direction::Left => DirectionNum::Dir(Direction::Up),
                }
            }
            b'L' => {
                self.direction_index += 1;
                match self.location.direction {
                    Direction::Up => DirectionNum::Dir(Direction::Left),
                    Direction::Right => DirectionNum::Dir(Direction::Up),
                    Direction::Down => DirectionNum::Dir(Direction::Right),
                    Direction::Left => DirectionNum::Dir(Direction::Down),
                }
            }
            _ => {
                let mut i = self.direction_index + 1;
                while i < self.directions.len()
                    && self.directions[i] != b'R'
                    && self.directions[i] != b'L'
                {
                    i += 1;
                }
                let val = self.directions[self.direction_index..i]
                    .iter()
                    .fold(0, |acc, v| acc * 10 + usize::try_from(*v - b'0').unwrap());
                self.direction_index = i;
                DirectionNum::Num(val)
            }
        }
    }
}

#[derive(Debug, Clone, Copy)]
struct Edge {
    from: Point,
    to: Point,
    direction: Direction,
}

impl Edge {
    fn to(&self, rev: bool) -> Self {
        let direction = match self.direction {
            Direction::Up => Direction::Down,
            Direction::Down => Direction::Up,
            Direction::Right => Direction::Left,
            Direction::Left => Direction::Right,
        };
        if rev {
            Self {
                from: self.to,
                to: self.from,
                direction,
            }
        } else {
            Self {
                from: self.from,
                to: self.to,
                direction,
            }
        }
    }

    fn on_edge(&self, location: Location) -> bool {
        if self.direction != location.direction {
            return false;
        }
        let from;
        let to;
        let test;
        if self.from[0] == self.to[0] {
            if location.point[0] != self.from[0] {
                return false;
            }
            from = self.from[1];
            to = self.to[1];
            test = location.point[1];
        } else {
            if location.point[1] != self.from[1] {
                return false;
            }
            from = self.from[0];
            to = self.to[0];
            test = location.point[0];
        }
        test >= std::cmp::min(from, to) && test <= std::cmp::max(from, to)
    }

    fn distance(&self, point: Point) -> usize {
        let from;
        let target;
        if self.from[0] == self.to[0] {
            from = self.from[1];
            target = point[1];
        } else {
            from = self.from[0];
            target = point[0];
        }
        if from > target {
            from - target
        } else {
            target - from
        }
    }

    fn get_point(&self, distance: usize) -> Point {
        let from;
        let to;
        if self.from[0] == self.to[0] {
            from = self.from[1];
            to = self.to[1];
        } else {
            from = self.from[0];
            to = self.to[0];
        }
        let target = if to > from {
            from + distance
        } else {
            from - distance
        };
        if self.from[0] == self.to[0] {
            [self.from[0], target]
        } else {
            [target, self.from[1]]
        }
    }
}

#[derive(Debug, Clone, Copy)]
struct EdgeMapping {
    from: Edge,
    to: Edge,
}

impl EdgeMapping {
    fn new(from: Edge, to: Edge) -> Self {
        Self {
            from,
            to: to.to(true),
        }
    }

    // TODO: don't assume start is on the from edge
    fn jump(&self, start: Point) -> Location {
        let dist = self.from.distance(start);
        Location {
            point: self.to.get_point(dist),
            direction: self.to.direction,
        }
    }
}

#[derive(Debug, PartialEq, Eq, Clone, Copy)]
enum MapSquare {
    Blank,
    Open,
    Wall,
}

#[derive(Debug, Clone, Copy)]
struct Location {
    point: Point,
    direction: Direction,
}

type Point = [usize; 2];

#[derive(Debug, PartialEq, Eq, Clone, Copy)]
enum Direction {
    Right,
    Up,
    Left,
    Down,
}

enum DirectionNum {
    Dir(Direction),
    Num(usize),
}

#[cfg(test)]
mod tests {

    use super::*;

    #[test]
    fn one() {
        let data = include_str!("test.txt");
        assert_eq!(6032, part_one::<12, 16>(data, true));
    }

    #[test]
    fn two() {
        let data = include_str!("test.txt");
        assert_eq!(5031, part_two::<12, 16>(data, true));
    }
}