use nom::{
    bytes::complete::tag,
    character::complete::{alpha1, line_ending, space1},
    combinator::map,
    multi::separated_list1,
    sequence::separated_pair,
    IResult,
};
use std::{collections::BTreeMap, fs};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let input = fs::read_to_string("inputs/day_25.txt")?;
    let parsed = Circuit::parser(&input).unwrap().1;
    let three_cut_partition_sizes = parsed.find_non_zero_three_cut_partition_sizes();
    dbg!(&three_cut_partition_sizes);
    dbg!(three_cut_partition_sizes.0 * three_cut_partition_sizes.1);

    Ok(())
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct VertexId(usize);

#[derive(Debug)]
struct Circuit {
    wires: Vec<Vec<VertexId>>,
}

#[derive(Debug, Clone, Eq)]
struct Edge {
    a: VertexId,
    b: VertexId,
}

impl PartialEq for Edge {
    fn eq(&self, other: &Self) -> bool {
        (self.a == other.a && self.b == other.b) || (self.a == other.b && self.b == other.a)
    }
}

impl Circuit {
    fn parser(input: &str) -> IResult<&str, Self> {
        map(
            separated_list1(
                line_ending,
                separated_pair(
                    map(alpha1, |s: &str| s.to_owned()),
                    tag(": "),
                    separated_list1(space1, map(alpha1, |s: &str| s.to_owned())),
                ),
            ),
            |vertices| {
                let mut vertex_id_mapping = BTreeMap::new();
                let mut wires = Vec::new();

                for (from, tos) in vertices {
                    let from_id = vertex_id_mapping
                        .entry(from)
                        .or_insert_with(|| {
                            let new_id = VertexId(wires.len());
                            wires.push(Vec::new());
                            new_id
                        })
                        .clone();
                    for to in tos {
                        let to_id = vertex_id_mapping
                            .entry(to)
                            .or_insert_with(|| {
                                let new_id = VertexId(wires.len());
                                wires.push(Vec::new());
                                new_id
                            })
                            .clone();
                        wires[from_id.0].push(to_id);
                        wires[to_id.0].push(from_id);
                    }
                }
                Circuit { wires }
            },
        )(input)
    }

    fn find_non_zero_three_cut_partition_sizes(&self) -> (usize, usize) {
        let cut1s = self.edges_to_traverse_everything([]);
        for (cut1i, cut1) in cut1s.iter().enumerate() {
            let cut2s = self.edges_to_traverse_everything([cut1.clone()]);
            for (cut2i, cut2) in cut2s.iter().enumerate() {
                if cut1s[0..cut1i].contains(&cut2) {
                    continue;
                }
                for cut3 in self.edges_to_traverse_everything([cut1.clone(), cut2.clone()]) {
                    if cut1s[0..cut1i].contains(&cut3) || cut2s[0..cut2i].contains(&cut3) {
                        // if (cut2, *) didn't work, then (*, cut2) also wouldn't work.
                        continue;
                    }
                    let (size1, size2) = self.partition_sizes([cut1.clone(), cut2.clone(), cut3]);
                    if size2 > 0 {
                        return (size1, size2);
                    }
                }
            }
        }
        panic!("No partitions with three cuts");
    }

    fn partition_sizes(&self, cuts: [Edge; 3]) -> (usize, usize) {
        let mut visited = vec![false; self.wires.len()];
        let mut frontier = Vec::new();

        visited[0] = true;
        frontier.push(VertexId(0));
        let mut visited_count = 1;

        while let Some(from) = frontier.pop() {
            for to in &self.wires[from.0] {
                let edge = Edge::new(from, *to);
                if !cuts.contains(&edge) && !visited[to.0] {
                    visited[to.0] = true;
                    visited_count += 1;
                    frontier.push(*to);
                }
            }
        }

        (visited_count, self.wires.len() - visited_count)
    }

    fn edges_to_traverse_everything<const N: usize>(&self, cuts: [Edge; N]) -> Vec<Edge> {
        let mut visited = vec![false; self.wires.len()];
        let mut frontier = Vec::new();

        visited[0] = true;
        frontier.push(VertexId(0));
        let mut used_edges = Vec::new();

        while let Some(from) = frontier.pop() {
            for to in &self.wires[from.0] {
                let edge = Edge::new(from, *to);
                if !cuts.contains(&edge) && !visited[to.0] {
                    visited[to.0] = true;
                    used_edges.push(edge);
                    frontier.push(*to);
                }
            }
        }
        used_edges
    }
}

impl Edge {
    fn new(a: VertexId, b: VertexId) -> Edge {
        Edge { a, b }
    }
}