use std::collections::{HashMap, HashSet, VecDeque};
use std::fmt::Debug;
use std::fmt::Formatter;

pub fn day12() {
    // 10 paths, 36
    // let input = r#"
    // start-A
    // start-b
    // A-c
    // A-b
    // b-d
    // A-end
    // b-end"#;
    // 19 paths, 103
    // let input = r#"
    // dc-end
    // HN-start
    // start-kj
    // dc-start
    // dc-HN
    // LN-dc
    // HN-end
    // kj-sa
    // kj-HN
    // kj-dc
    //     "#;
    // 226 paths, 3059
    // let input = r#"
    // fs-end
    // he-DX
    // fs-he
    // start-DX
    // pj-DX
    // end-zg
    // zg-sl
    // zg-pj
    // pj-he
    // RW-he
    // fs-DX
    // pj-RW
    // zg-RW
    // start-pj
    // he-WI
    // zg-he
    // pj-fs
    // start-RW
    //     "#;
    let input = include_str!("../input/day12.txt");

    let graph = parse_graph(&input);
    println!("{:?}", graph);

    println!("{:?}", count_paths(&graph, false));
    println!("{:?}", count_paths(&graph, true));
}

fn parse_graph(input: &'static str) -> Graph {
    let mut nodes = HashSet::new();
    let mut connections: HashMap<Node, Vec<Node>> = HashMap::new();
    for line in input.trim().lines() {
        let (a, b) = line.trim().split_once("-").unwrap();
        let first: Node = a.into();
        let second: Node = b.into();
        nodes.insert(first.clone());
        nodes.insert(second.clone());
        connections
            .entry(first.clone())
            .or_insert(vec![])
            .push(second.clone());
        connections.entry(second).or_insert(vec![]).push(first);
    }

    Graph { nodes, connections }
}

#[derive(PartialEq, Eq, Hash, Clone)]
enum Node {
    Start,
    End,
    Small(&'static str),
    Big(&'static str),
}

impl Node {
    fn big(&self) -> bool {
        match self {
            Self::Big(_) => true,
            _ => false,
        }
    }
}

impl Debug for Node {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Start => write!(f, "start"),
            Self::End => write!(f, "end"),
            Self::Small(s) | Self::Big(s) => write!(f, "{}", s),
        }
    }
}

impl From<&'static str> for Node {
    fn from(s: &'static str) -> Self {
        if s == "start" {
            Self::Start
        } else if s == "end" {
            Self::End
        } else if s.chars().all(|c| c.is_uppercase()) {
            Self::Big(s)
        } else {
            Self::Small(s)
        }
    }
}

#[derive(Debug)]
struct Graph {
    nodes: HashSet<Node>,
    connections: HashMap<Node, Vec<Node>>,
}

fn count_paths(g: &Graph, allow_visiting_small_twice: bool) -> usize {
    let mut queue: VecDeque<(Vec<&Node>, bool)> = VecDeque::new();
    queue.push_front((vec![&Node::Start], false));
    let mut count = 0;

    while let Some((path, mut seen_any_small_twice)) = queue.pop_front() {
        let last = path.last().unwrap().clone();

        if last == &Node::End {
            // println!("{:?}", path);
            count += 1;
            continue;
        }

        // current is small and seen current before
        if !last.big() && path.iter().rev().skip(1).any(|&n| n == last) {
            // if visting small twice is always prohibited (part 1), or we're revisting the start,
            // or visiting a _single_ small twice is allowed but we've already done it
            if !allow_visiting_small_twice || last == &Node::Start || seen_any_small_twice {
                continue;
            }
            // note that we've now seen a single small cave twice, so any paths descended from this
            // one can't do so themselves
            seen_any_small_twice = true;
        }

        for connected in &g.connections[last] {
            let mut new_path = path.clone();
            new_path.push(connected);
            queue.push_back((new_path, seen_any_small_twice));
        }
    }

    count
}