use itertools::Itertools;
use std::ops::{Index, IndexMut};

/// Represents a position on the "map", from a top-down perspective. A
/// Position is given as (row, column).
#[derive(Debug, Default, Copy, Clone, PartialEq, Eq)]
struct Position(usize, usize);

/// Indicates the heading of the current movement on the map, from a
/// top-down perspective.
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
enum Heading {
    Up,
    Right,
    Down,
    Left,
}

/// Represents the links from one point on the map to another. This way, each
/// point on the map knows what the heading and position will be for someone
/// who moves in a given direction from that point.
#[derive(Debug, Default, Copy, Clone, PartialEq, Eq)]
struct Links {
    up: Option<(Heading, Position)>,
    right: Option<(Heading, Position)>,
    down: Option<(Heading, Position)>,
    left: Option<(Heading, Position)>,
}

/// Represents a tile on the map
#[derive(Debug, Default, Copy, Clone, PartialEq, Eq)]
enum Tile {
    #[default]
    Void,
    Path(Links),
    Wall,
}

impl Tile {
    /// Sometimes, it's nice to have a function to let us know if the current
    /// Tile is a Tile::Path or not.
    fn is_path(&self) -> bool {
        matches!(self, Tile::Path(_))
    }
}

/// Represents a movement direction, given on the last line of the input file.
#[derive(Debug, Copy, Clone)]
enum Direction {
    TurnLeft,
    TurnRight,
    Forward(u32),
}

/// Represents the tiles on the map given to us by the monkeys, with the added
/// metadata from us added in.
#[derive(Debug, Clone)]
struct MonkeyMap(Vec<Vec<Tile>>);

/// Namespacing for the parsers used in today's puzzle.
mod parser {
    use super::*;
    use anyhow::{anyhow, Result};
    use nom::{
        branch::alt,
        bytes::complete::{tag, take_till, take_while},
        character::complete::{alphanumeric0, newline, u32},
        combinator::{map, value},
        multi::{many0, many1, separated_list0},
        sequence::{pair, separated_pair},
        Finish, IResult,
    };

    /// Nom parser for " " -> Tile::Void
    fn void(s: &str) -> IResult<&str, Tile> {
        value(Tile::Void, tag(" "))(s)
    }

    /// Nom parser for "." -> Tile::Path()
    fn passable(s: &str) -> IResult<&str, Tile> {
        value(Tile::Path(Links::default()), tag("."))(s)
    }

    /// Nom parser for "#" -> Tile::Wall
    fn wall(s: &str) -> IResult<&str, Tile> {
        value(Tile::Wall, tag("#"))(s)
    }

    /// Nom parser for all Tile variants
    fn tile(s: &str) -> IResult<&str, Tile> {
        alt((void, passable, wall))(s)
    }

    /// Nom parser for a line of Tiles in the input
    fn tile_line(s: &str) -> IResult<&str, Vec<Tile>> {
        many1(tile)(s)
    }

    /// Nom parser for all the tiles in the input
    fn monkey_map(s: &str) -> IResult<&str, MonkeyMap> {
        map(separated_list0(newline, tile_line), MonkeyMap)(s)
    }

    /// Nom parser for "10" -> Direction::Forward(10)
    fn forward(s: &str) -> IResult<&str, Direction> {
        map(u32, Direction::Forward)(s)
    }

    /// Nom parser for "L" -> Direction::TurnLeft
    fn left(s: &str) -> IResult<&str, Direction> {
        value(Direction::TurnLeft, tag("L"))(s)
    }

    /// Nom parser for "R" -> Direction::TurnRight
    fn right(s: &str) -> IResult<&str, Direction> {
        value(Direction::TurnRight, tag("R"))(s)
    }

    /// Nom parser for all Direction variants
    fn direction(s: &str) -> IResult<&str, Direction> {
        alt((forward, left, right))(s)
    }

    /// Nom parser for the entire list of Directions given in the last line of
    /// the input.
    fn directions(s: &str) -> IResult<&str, Vec<Direction>> {
        many0(direction)(s)
    }

    /// Nom parser for both parts of the input, separated by an empty line.
    fn both_parts(s: &str) -> IResult<&str, (MonkeyMap, Vec<Direction>)> {
        separated_pair(monkey_map, tag("\n\n"), directions)(s)
    }

    /// Entrypoint for parser combinators, parses the input file into a
    /// MonkeyMap and list of Directions.
    pub fn parse(s: &str) -> Result<(MonkeyMap, Vec<Direction>)> {
        let (_, result) = both_parts(s).finish().map_err(|e| anyhow!("{e}"))?;
        Ok(result)
    }
}

/// It's convenient to be able to index into the MonkeyMap using a Position,
/// since Position is used to represent a point on the MonkeyMap.
impl Index<Position> for MonkeyMap {
    type Output = Tile;

    fn index(&self, index: Position) -> &Self::Output {
        let Position(row, col) = index;
        &self.0[row][col]
    }
}

/// It's also convenient to be able to access these indices mutably.
impl IndexMut<Position> for MonkeyMap {
    fn index_mut(&mut self, index: Position) -> &mut Self::Output {
        let Position(row, col) = index;
        &mut self.0[row][col]
    }
}

impl MonkeyMap {
    /// Build up the links to other Tiles on each Tile::Path in the MonkeyMap. This
    /// way, we can check a given Tile for the heading and position of the tile in
    /// each of the four cardinal directions.
    fn map_positions(&mut self) {
        let rows = self.0.len();

        // Iterating over the indices keeps borrow checker wrangling to a minimum
        // here. We need to get the number of columns individually for each row,
        // since each row has a variable number of columns. The input doesn't have
        // spaces at the ends of lines where the map doesn't span to the end of the
        // line.
        for row in 0..rows {
            let cols = self.0.get(row).map(|v| v.len()).unwrap_or_default();
            for col in 0..cols {
                if let Tile::Path(mut links) = self.0[row][col] {
                    let position = Position(row, col);
                    links.up = self.find_next_up(position);
                    links.right = self.find_next_right(position);
                    links.down = self.find_next_down(position);
                    links.left = self.find_next_left(position);
                    self[position] = Tile::Path(links);
                }
            }
        }
    }

    /// From a given position, identify the Heading/Position of the Tile that can
    /// be achieved by moving up from the current position. Accounts for wrapping
    /// around the map when moving up into an unmarked space.
    fn find_next_up(&self, position: Position) -> Option<(Heading, Position)> {
        let Position(row, col) = position;
        let inner_iter = self.0.iter();

        // This is a bit of a gnarly iterator chain, but the ultimate outcome is that
        // it produces an iterator that starts at the current position and moves along
        // the current column by row, in reverse, and returns the first position found
        // that isn't a Tile::Void, which provides the wrapping functionality. This
        // is probably the gnarliest of the four functions, since it requires iterating
        // by column and in reverse. The rest of the `find_next_*()` functions are
        // all variations on this one.
        let (found_row, found_tile) = inner_iter
            .enumerate()
            .rev()
            .map(|(row_idx, row)| (row_idx, row.get(col).unwrap_or(&Tile::Void)))
            .cycle()
            .skip(self.0.len() - row)
            .find(|(_, tile)| !matches!(tile, Tile::Void))?;
        if found_tile.is_path() {
            return Some((Heading::Up, Position(found_row, col)));
        }
        None
    }

    /// From a given position, identify the Heading/Position of the Tile that can
    /// be achieved by moving down from the current position. Accounts for wrapping
    /// around the map when moving up into an unmarked space.
    fn find_next_down(&self, position: Position) -> Option<(Heading, Position)> {
        let Position(row, col) = position;
        let inner_iter = self.0.iter();
        let (found_row, found_tile) = inner_iter
            .enumerate()
            .map(|(row_idx, row)| (row_idx, row.get(col).unwrap_or(&Tile::Void)))
            .cycle()
            .skip(row + 1)
            .find(|(_, tile)| **tile != Tile::Void)?;
        if found_tile.is_path() {
            return Some((Heading::Down, Position(found_row, col)));
        }
        None
    }

    /// From a given position, identify the Heading/Position of the Tile that can
    /// be achieved by moving left from the current position. Accounts for wrapping
    /// around the map when moving up into an unmarked space.
    fn find_next_left(&self, position: Position) -> Option<(Heading, Position)> {
        let Position(row, col) = position;
        let row_of_tiles = self.0.get(row)?;
        let (found_col, found_tile) = row_of_tiles
            .iter()
            .enumerate()
            .rev()
            .cycle()
            .skip(row_of_tiles.len() - col)
            .find(|(_, tile)| **tile != Tile::Void)?;
        if found_tile.is_path() {
            return Some((Heading::Left, Position(row, found_col)));
        }
        None
    }

    fn find_next_right(&self, position: Position) -> Option<(Heading, Position)> {
        let Position(row, col) = position;
        let row_of_tiles = self.0.get(row)?;

        // And this one is probably the least gnarly. Which obviously means it was
        // the one I wrote last. I really should have written these in reverse,
        // because writing the "up" iterator chain as a PITA and I could have
        // used this one as a template. Ah, well.
        let (found_col, found_tile) = row_of_tiles
            .iter()
            .enumerate()
            .cycle()
            .skip(col + 1)
            .find(|(_, tile)| **tile != Tile::Void)?;
        if found_tile.is_path() {
            return Some((Heading::Right, Position(row, found_col)));
        }
        None
    }
}

const INPUT: &str = include_str!("../../input/22/input.txt");

/// Parse that input!
fn read() -> (MonkeyMap, Vec<Direction>) {
    let (mut map, directions) = parser::parse(INPUT).unwrap();
    map.map_positions();
    (map, directions)
}

/// Solve Day 22, Part 1
fn solve(input: &(MonkeyMap, Vec<Direction>)) -> u32 {
    // This bit is just so I can convert the reference to the input into a
    // mutable map. I pass in the input as a reference because it keeps me from
    // accidentally mutating it in Part 1 and spending hours wondering why
    // my solution for Part 2 doesn't work on the input I forgot I had mutated.
    let (monkey_map, directions) = input;
    let mut board = monkey_map.clone();

    // Start at the first path Tile on the first row, facing right
    let Some(start_pos) = board.first_path_position() else { 
        panic!("Cannot find start position!"); 
    };
    let mut walker = Walker::new(start_pos);

    // Follow each direction
    directions
        .iter()
        .for_each(|direction| walker.follow(&board, *direction));

    // Let the walker calculate its own score and return it
    walker.score()
}

impl MonkeyMap {
    /// Finds the position of the first Tile::Path in the MonkeyMap,
    /// in reading order (left to right, top to bottom), if there is
    /// one.
    fn first_path_position(&self) -> Option<Position> {
        let first_row = self.0.first()?;
        let first_col = first_row
            .iter()
            .position(|tile| matches!(tile, Tile::Path(_)))?;
        Some(Position(0, first_col))
    }
}

impl Tile {
    /// Get the links associated with the Tile. If it's a Tile::Void
    /// or Tile::Wall, the default is a Links with no links filled in.
    /// That doesn't actually come up much, though.
    fn links(&self) -> Links {
        match self {
            Tile::Path(links) => *links,
            _ => Links::default(),
        }
    }
}

/// Represents a "walker" walking the path on the MonkeyMap.
#[derive(Debug)]
struct Walker(Heading, Position);

impl Walker {
    fn new(position: Position) -> Self {
        Walker(Heading::Right, position)
    }

    /// Lets the Walker calculate it's own score according to the puzzle description.
    fn score(&self) -> u32 {
        let Walker(heading, position) = self;
        let Position(row, col) = position;
        let heading_mod = match heading {
            Heading::Right => 0,
            Heading::Down => 1,
            Heading::Left => 2,
            Heading::Up => 3,
        };
        ((*row as u32 + 1) * 1000) + ((*col as u32 + 1) * 4) + heading_mod
    }

    /// Given a direction and a reference to the map, attempt to follow the
    /// direction by moving or turning the Walker.
    fn follow(&mut self, map: &MonkeyMap, direction: Direction) {
        let Walker(heading, position) = self;
        let tile = map[*position];
        let Tile::Path(links) = tile else { return; };

        use Direction::*;
        use Heading::*;
        match (heading, direction) {
            // Turning is easy, just match and update the Walker with the new heading
            (Up, TurnLeft) => *self = Walker(Left, *position),
            (Up, TurnRight) => *self = Walker(Right, *position),

            (Right, TurnLeft) => *self = Walker(Up, *position),
            (Right, TurnRight) => *self = Walker(Down, *position),

            (Down, TurnLeft) => *self = Walker(Right, *position),
            (Down, TurnRight) => *self = Walker(Left, *position),

            (Left, TurnLeft) => *self = Walker(Down, *position),
            (Left, TurnRight) => *self = Walker(Up, *position),

            // Moving forward is a bit tougher, but not too serious.
            (heading, Forward(n)) => {
                // As many times as we're suppose to move forward...
                for _ in 0..n {
                    // Unpack the walker again since we're going to modify it
                    // directly in subsequent loops.
                    let Walker(heading, position) = self;

                    // Here's where having the Links stored on the Tiles comes in
                    // handy. We can just query the links on the current Tile for
                    // the heading and position we should be at if we move in the
                    // indicated direction from the current Tile.
                    let mut links = map[*position].links();
                    let link = match heading {
                        Up => links.up,
                        Right => links.right,
                        Down => links.down,
                        Left => links.left,
                    };

                    // If there's no link in the indicated direction, just stop.
                    // Otherwise, update the Walker and keep going.
                    let Some((heading, position)) = link else { break; };
                    *self = Walker(heading, position)
                }
            }
        };
    }
}

/// Solve Day 22, Part 2
fn solve(input: &(MonkeyMap, Vec<Direction>)) -> u32 {
    let (board, directions) = input;
    let mut board = board.clone();
    board.wrap(); // This is the difference!
    let Some(start_pos) = board.first_path_position() else { 
        panic!("Cannot find start position!"); 
    };
    let mut walker = Walker::new(start_pos);
    directions
        .iter()
        .for_each(|direction| walker.follow(&board, *direction));
    walker.score()
}

impl MonkeyMap {
    /// My map looks like this, where the pairs of letters indicate pairs of edges
    /// that line up to form the cube if this shape were folded.
    ///
    ///            _______ _______
    ///           |   A   |   B   |
    ///           |C      |      D|
    ///           |_______|___F___|
    ///           |       |
    ///           |E     F|
    ///    _______|_______|
    ///   |   E   |       |
    ///   |C      |      D|
    ///   |_______|___G___|
    ///   |       |
    ///   |A     G|
    ///   |___B___|
    ///
    /// Yours probably doesn't. This function re-maps the connections on the linkss
    /// on the outside edges to the correct matching edge. The hard part is making
    /// sure you match up the right edges in the right order. I recommend cutting
    /// out the shape of your map on a sheet of paper, folding it into a cube, and
    /// using that cube to determine how to match up the sides. This was an incredibly
    /// tedious bit of code to write because the various joins between the open face
    /// pairs all had their own bits of uniqueness that prevented me from doing this
    /// in a loop. So, each pair of faces is being joined manually.
    fn wrap(&mut self) {
        let inner = &self.0;

        // Match up the (A) sides. All the faces are joined this way, where I
        // iterate along the positions from the matching faces in the order that
        // they match up and modify their links as needed to have each edge direct
        // the Walker to the corresponding Tile on the other face. This was made
        // even more tedious by the fact that this approach is completely different
        // that the one I'd need to take to do this for the example input, since
        // the example map is shaped differently from my input.
        let side1 = (50..100).map(|col| Position(0, col));
        let side2 = (150..200).map(|row| Position(row, 0));
        for (p1, p2) in std::iter::zip(side1, side2) {
            if self[p1].is_path() {
                let mut links = self[p1].links();
                links.up = if self[p2].is_path() {
                    Some((Heading::Right, p2))
                } else {
                    None
                };
                self[p1] = Tile::Path(links);
            }

            if self[p2].is_path() {
                let mut links = self[p2].links();
                links.left = if self[p1].is_path() {
                    Some((Heading::Down, p1))
                } else {
                    None
                };
                self[p2] = Tile::Path(links);
            }
        }

        // Match up the (B) sides.
        let side1 = (100..150).map(|col| Position(0, col));
        let side2 = (0..50).map(|col| Position(199, col));
        for (p1, p2) in std::iter::zip(side1, side2) {
            if self[p1].is_path() {
                let mut links = self[p1].links();
                links.up = if self[p2].is_path() {
                    Some((Heading::Up, p2))
                } else {
                    None
                };
                self[p1] = Tile::Path(links);
            }

            if self[p2].is_path() {
                let mut links = self[p2].links();
                links.down = if self[p1].is_path() {
                    Some((Heading::Down, p1))
                } else {
                    None
                };
                self[p2] = Tile::Path(links);
            }
        }

        // Match up the (C) sides.
        let side1 = (0..50).map(|row| Position(row, 50));
        let side2 = (100..150).map(|row| Position(row, 0)).rev();
        for (p1, p2) in std::iter::zip(side1, side2) {
            if self[p1].is_path() {
                let mut links = self[p1].links();
                links.left = if self[p2].is_path() {
                    Some((Heading::Right, p2))
                } else {
                    None
                };
                self[p1] = Tile::Path(links);
            }

            if self[p2].is_path() {
                let mut links = self[p2].links();
                links.left = if self[p1].is_path() {
                    Some((Heading::Right, p1))
                } else {
                    None
                };
                self[p2] = Tile::Path(links);
            }
        }

        // Match up the (D) sides.
        let side1 = (0..50).map(|row| Position(row, 149));
        let side2 = (100..150).map(|row| Position(row, 99)).rev();
        for (p1, p2) in std::iter::zip(side1, side2) {
            if self[p1].is_path() {
                let mut links = self[p1].links();
                links.right = if self[p2].is_path() {
                    Some((Heading::Left, p2))
                } else {
                    None
                };
                self[p1] = Tile::Path(links);
            }

            if self[p2].is_path() {
                let mut links = self[p2].links();
                links.right = if self[p1].is_path() {
                    Some((Heading::Left, p1))
                } else {
                    None
                };
                self[p2] = Tile::Path(links);
            }
        }

        // Match up the (E) sides.
        let side1 = (50..100).map(|row| Position(row, 50));
        let side2 = (0..50).map(|col| Position(100, col));
        for (p1, p2) in std::iter::zip(side1, side2) {
            if self[p1].is_path() {
                let mut links = self[p1].links();
                links.left = if self[p2].is_path() {
                    Some((Heading::Down, p2))
                } else {
                    None
                };
                self[p1] = Tile::Path(links);
            }

            if self[p2].is_path() {
                let mut links = self[p2].links();
                links.up = if self[p1].is_path() {
                    Some((Heading::Right, p1))
                } else {
                    None
                };
                self[p2] = Tile::Path(links);
            }
        }

        // Match up the (F) sides.
        let side1 = (100..150).map(|col| Position(49, col));
        let side2 = (50..100).map(|row| Position(row, 99));
        for (p1, p2) in std::iter::zip(side1, side2) {
            if self[p1].is_path() {
                let mut links = self[p1].links();
                links.down = if self[p2].is_path() {
                    Some((Heading::Left, p2))
                } else {
                    None
                };
                self[p1] = Tile::Path(links);
            }

            if self[p2].is_path() {
                let mut links = self[p2].links();
                links.right = if self[p1].is_path() {
                    Some((Heading::Up, p1))
                } else {
                    None
                };
                self[p2] = Tile::Path(links);
            }
        }

        // Match up the (G) sides.
        let side1 = (50..100).map(|col| Position(149, col));
        let side2 = (150..200).map(|row| Position(row, 49));
        for (p1, p2) in std::iter::zip(side1, side2) {
            if self[p1].is_path() {
                let mut links = self[p1].links();
                links.down = if self[p2].is_path() {
                    Some((Heading::Left, p2))
                } else {
                    None
                };
                self[p1] = Tile::Path(links);
            }

            if self[p2].is_path() {
                let mut links = self[p2].links();
                links.right = if self[p1].is_path() {
                    Some((Heading::Up, p1))
                } else {
                    None
                };
                self[p2] = Tile::Path(links);
            }
        }

        // And that's that! Seven slightly different edge-to-edge joins! I can't
        // tell you how many small "typo" bugs I made in these seven blocks. The
        // good news is that once the edges are forwarding correctly, walking the
        // "cube" is exactly the same as walking the map in part one.
    }
}