use std::{
    cmp::Ordering,
    collections::{BTreeMap, HashMap},
};

use anyhow::Context;

use crate::{Problem, Solution};

pub struct Day10;

impl Problem for Day10 {
    const DAY: u8 = 10;

    const INPUT: &'static str = include_str!("../input/day_10.txt");
}

impl Solution for Day10 {
    type Answer1 = usize;

    type Answer2 = usize;

    fn part_1(input: &str) -> anyhow::Result<Self::Answer1> {
        let mut graph: Graph = input.parse()?;

        Ok(graph.solve()? / 2)
    }

    fn part_2(input: &str) -> anyhow::Result<Self::Answer2> {
        let mut graph: Graph = input.parse()?;
        graph.solve()?;

        Ok(graph
            .inner
            .iter()
            .filter(|(pos, _)| graph.is_included(pos))
            .count())
    }
}

type Position = (usize, usize);

#[derive(Default)]
struct Graph {
    inner: HashMap<Position, char>,
    start: Position,
    path: BTreeMap<usize, BTreeMap<usize, char>>,
}

impl Graph {
    fn solve(&mut self) -> anyhow::Result<usize> {
        let mut steps = 0;
        let mut pos = self.start;
        let mut next_edge = Edge::ALL.into_iter().find(|e| {
            e.traverse(pos)
                .and_then(|p| self.inner.get(&p))
                .map(|c| e.valid_edge(c))
                .unwrap_or_default()
        });
        let mut c = &'S';
        let start_edge = next_edge.to_owned().unwrap();

        while let Some(edge) = next_edge {
            steps += 1;
            self.path
                .entry(pos.0)
                .and_modify(|v| {
                    v.insert(pos.1, *c);
                })
                .or_insert(BTreeMap::from([(pos.1, *c)]));
            pos = edge.traverse(pos).context("Out-of-bounds move")?;
            c = self.inner.get(&pos).context("Failed to get postion")?;
            if c == &'S' {
                self.path.entry(pos.0).and_modify(|v| {
                    assert_eq!(
                        Some('S'),
                        v.insert(pos.1, edge.as_char(&start_edge).unwrap())
                    );
                });
                break;
            }
            next_edge = edge.next(c);
        }

        Ok(steps)
    }

    fn is_included(&self, pos: &Position) -> bool {
        let mut seg_start = ' ';
        let mut left = 0;
        let mut right = 0;

        let line = match self.path.get(&pos.0) {
            Some(b) if b.get(&pos.1).is_none() => b,
            _ => return false,
        };

        for (col, c) in line.iter() {
            let count = match col.cmp(&pos.1) {
                Ordering::Less => &mut left,
                Ordering::Greater => &mut right,
                Ordering::Equal if left % 2 != 0 => return true,
                Ordering::Equal => continue,
            };

            match c {
                '|' => *count += 1,
                'F' => seg_start = 'F',
                'L' => seg_start = 'L',
                'J' if seg_start == 'F' => *count += 1,
                '7' if seg_start == 'L' => *count += 1,
                'J' if seg_start == 'L' => seg_start = ' ',
                '7' if seg_start == 'F' => seg_start = ' ',
                _ => {}
            }
        }

        left % 2 != 0 && right % 2 != 0
    }
}

impl std::str::FromStr for Graph {
    type Err = anyhow::Error;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let inner = s
            .trim()
            .lines()
            .enumerate()
            .flat_map(|(row, line)| {
                line.trim()
                    .chars()
                    .enumerate()
                    .map(move |(col, char)| ((row, col), char))
            })
            .collect::<HashMap<_, _>>();

        let start = inner
            .iter()
            .find_map(|(pos, c)| (c == &'S').then_some(pos))
            .context("Failed to find start")?;

        Ok(Graph {
            start: *start,
            inner,
            ..Default::default()
        })
    }
}

impl std::fmt::Debug for Graph {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let (height, width) = self.inner.keys().max().unwrap();
        for row in 0..height + 1 {
            write!(f, "{row:03}: ")?;
            let Some(btree) = self.path.get(&row) else {
                writeln!(f)?;
                continue;
            };
            let mut output = String::new();
            for col in 0..width + 1 {
                match btree.get(&col) {
                    Some(c) => output.push(*c),
                    None if self.is_included(&(row, col)) => output.push('I'),
                    None => output.push('O'),
                };
            }
            writeln!(f, "{output}")?
        }
        Ok(())
    }
}

impl std::fmt::Display for Graph {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let (height, width) = self.inner.keys().max().unwrap();
        for row in 0..height + 1 {
            write!(f, "{row:03}: ")?;
            let Some(btree) = self.path.get(&row) else {
                writeln!(f)?;
                continue;
            };
            let mut output = String::new();
            for col in 0..width + 1 {
                match btree.get(&col) {
                    Some('|') => output.push('│'),
                    Some('-') => output.push('─'),
                    Some('L') => output.push('└'),
                    Some('J') => output.push('┘'),
                    Some('7') => output.push('┐'),
                    Some('F') => output.push('┌'),
                    Some(c) => output.push(*c),
                    None if self.is_included(&(row, col)) => output.push('I'),
                    None => output.push('O'),
                };
            }
            writeln!(f, "{output}")?
        }
        Ok(())
    }
}

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

impl Edge {
    const ALL: [Edge; 4] = [Self::Up, Self::Down, Self::Left, Self::Right];

    fn traverse(&self, (row, col): Position) -> Option<Position> {
        Some(match self {
            Edge::Up => (row.checked_sub(1)?, col),
            Edge::Down => (row.checked_add(1)?, col),
            Edge::Left => (row, col.checked_sub(1)?),
            Edge::Right => (row, col.checked_add(1)?),
        })
    }

    fn valid_edge(&self, &c: &char) -> bool {
        match self {
            Edge::Up => c == '|' || c == '7' || c == 'F',
            Edge::Down => c == '|' || c == 'J' || c == 'L',
            Edge::Left => c == '-' || c == 'F' || c == 'L',
            Edge::Right => c == '-' || c == 'J' || c == '7',
        }
    }

    fn next(&self, &c: &char) -> Option<Self> {
        Some(match (self, c) {
            (Edge::Up, '|') => Edge::Up,
            (Edge::Up, '7') => Edge::Left,
            (Edge::Up, 'F') => Edge::Right,
            (Edge::Down, '|') => Edge::Down,
            (Edge::Down, 'J') => Edge::Left,
            (Edge::Down, 'L') => Edge::Right,
            (Edge::Left, '-') => Edge::Left,
            (Edge::Left, 'F') => Edge::Down,
            (Edge::Left, 'L') => Edge::Up,
            (Edge::Right, '-') => Edge::Right,
            (Edge::Right, 'J') => Edge::Up,
            (Edge::Right, '7') => Edge::Down,
            _ => None?,
        })
    }

    fn as_char(&self, other: &Edge) -> Option<char> {
        Some(match (self, other) {
            (Edge::Up, Edge::Down) | (Edge::Down, Edge::Up) => '|',
            (Edge::Left, Edge::Right) | (Edge::Right, Edge::Left) => '-',
            (Edge::Up, Edge::Left) => '7',
            (Edge::Left, Edge::Down) => 'F',
            (Edge::Left, Edge::Up) => 'L',
            (Edge::Down, Edge::Left) => 'J',
            (Edge::Up, Edge::Right) => 'F',
            (Edge::Right, Edge::Down) => '7',
            (Edge::Right, Edge::Up) => 'J',
            (Edge::Down, Edge::Right) => 'L',
            _ => None?,
        })
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_part_1() -> anyhow::Result<()> {
        const INPUT: &str = indoc::indoc! {"
            ..F7.
            .FJ|.
            SJ.L7
            |F--J
            LJ...
        "};

        Ok(assert_eq!(8, Day10::part_1(INPUT)?))
    }

    #[test]
    fn test_part_2_1() -> anyhow::Result<()> {
        const INPUT: &str = indoc::indoc! {"
            FF7FSF7F7F7F7F7F---7
            L|LJ||||||||||||F--J
            FL-7LJLJ||||||LJL-77
            F--JF--7||LJLJ7F7FJ-
            L---JF-JLJ.||-FJLJJ7
            |F|F-JF---7F7-L7L|7|
            |FFJF7L7F-JF7|JL---7
            7-L-JL7||F7|L7F-7F7|
            L.L7LFJ|||||FJL7||LJ
            L7JLJL-JLJLJL--JLJ.L
        "};

        Ok(assert_eq!(10, Day10::part_2(INPUT)?))
    }

    #[test]
    fn test_part_2_2() -> anyhow::Result<()> {
        const INPUT: &str = indoc::indoc! {"
            .F----7F7F7F7F-7....
            .|F--7||||||||FJ....
            .||.FJ||||||||L7....
            FJL7L7LJLJ||LJ.L-7..
            L--J.L7...LJS7F-7L7.
            ....F-J..F7FJ|L7L7L7
            ....L7.F7||L7|.L7L7|
            .....|FJLJ|FJ|F7|.LJ
            ....FJL-7.||.||||...
            ....L---J.LJ.LJLJ...
        "};

        Ok(assert_eq!(8, Day10::part_2(INPUT)?))
    }

    #[test]
    fn test_part_2_3() -> anyhow::Result<()> {
        const INPUT: &str = indoc::indoc! {"
            ...........
            .S-------7.
            .|F-----7|.
            .||.....||.
            .||.....||.
            .|L-7.F-J|.
            .|..|.|..|.
            .L--J.L--J.
            ...........
        "};

        Ok(assert_eq!(4, Day10::part_2(INPUT)?))
    }
}