use std::collections::{HashMap, HashSet};
use regex::Regex;
use itertools::Itertools;

fn main() {
    let input = advent::read_lines(9);
    println!("9a: {}", shortest_route(&input));
    println!("9b: {}", longest_route(&input));
}

fn parse_routes<T: AsRef<str>>(input: &[T]) -> HashMap<String, HashMap<String, u32>> {
    let re = Regex::new(r"^([A-Za-z]+) to ([A-Za-z]+) = ([0-9]+)$").unwrap();

    let mut routes = HashMap::new();

    for line in input {
        let cap = re.captures(line.as_ref()).unwrap();
        let from = cap[1].to_string();
        let to = cap[2].to_string();
        let distance = cap[3].parse::<u32>().unwrap();

        let entry = routes.entry(from.clone()).or_insert_with(HashMap::new);
        entry.insert(to.clone(), distance);

        let entry = routes.entry(to).or_insert_with(HashMap::new);
        entry.insert(from, distance);
    }

    routes
}

fn distances<T: AsRef<str>>(input: &[T]) -> HashSet<u32> {
    let routes = parse_routes(input);

    let mut distances = HashSet::new();
    for route in routes.keys().permutations(routes.keys().len()) {
        let mut distance = 0;
        let mut prev_city = (*route.first().unwrap()).clone();
        for city in route.iter().skip(1).cloned().cloned() {
            let reachable_from_prev = routes.get(&prev_city).unwrap();
            distance += reachable_from_prev.get(&city).unwrap();
            prev_city = city;
        }
        distances.insert(distance);
    }

    distances
}

fn shortest_route<T: AsRef<str>>(input: &[T]) -> u32 {
    *distances(input).iter().min().unwrap()
}

fn longest_route<T: AsRef<str>>(input: &[T]) -> u32 {
    *distances(input).iter().max().unwrap()
}

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

    #[test]
    fn test() {
        let input = [
            "London to Dublin = 464",
            "London to Belfast = 518",
            "Dublin to Belfast = 141",
        ];
        assert_eq!(shortest_route(&input), 605);
        assert_eq!(longest_route(&input), 982);
    }
}