use std::collections::HashMap;
use std::collections::BTreeSet;
use std::collections::VecDeque;
use std::iter::once;
use std::ops::Deref;

fn main() {
    use std::io::BufRead;
    let filename = std::env::args().nth(1).expect("Expected filename");
    let graph = build_graph(&mut parse_edges(
        &mut std::io::BufReader::new(
            std::fs::File::open(filename.deref()).unwrap(),
        )
        .lines()
        .flat_map(Result::ok),
    ));
    println!("{} paths", count_paths(&graph));
}

fn count_paths(graph: &HashMap<usize, HashMap<usize, u128>>) -> u128 {
    let mut q: VecDeque<(usize, BTreeSet<usize>)> = once((0, BTreeSet::new())).collect();
    let mut r: HashMap<usize, HashMap<BTreeSet<usize>, u128>> = once((0, once((BTreeSet::new(), 1)).collect())).collect();
    while let Some((n, p)) = q.pop_front() {
        match (r.get(&n).and_then(|s| s.get(&p)), graph.get(&n)) {
            (Some(c), Some(e)) => {
                let c = *c;
                let mut next_p = p.clone();
                next_p.insert(n);
                for (t, w) in e.iter().filter(|(t,_)| !p.contains(t)) {
                    let d = c * *w;
                    r.entry(*t).or_insert_with(|| HashMap::new()).entry(next_p.clone()).and_modify(|g| *g += d).or_insert(d);
                    q.push_back((*t, next_p.clone()));
                }
            }
            _ => {}
        }
    }
    r.get(&1).map(|z| z.iter().map(|(_,n)| *n).sum()).unwrap_or(0)
}

fn parse_edges<I: Iterator<Item = S>, S: Deref<Target = str>>(
    source: &mut I,
) -> impl Iterator<Item = (String, String)> + '_ {
    source.filter_map(|l| {
        let mut s = l
            .split('-')
            .map(str::trim)
            .map(std::borrow::ToOwned::to_owned);
        let lhs = s.next()?;
        let rhs = s.next()?;
        match s.next() {
            None => Some(()),
            Some(_) => None,
        }?;
        Some((lhs, rhs))
    })
}

fn build_graph<
    I: Iterator<Item = (S, T)>,
    S: Deref<Target = str>,
    T: Deref<Target = str>,
>(
    source: &mut I,
) -> HashMap<usize, HashMap<usize, u128>> {
    let mut large = HashMap::new();
    let mut small = HashMap::new();
    number(&mut small, String::from("start"));
    number(&mut small, String::from("end"));
    let mut result = HashMap::new();
    for (s, t) in source
        .flat_map(|(s, t)| {
            let s = s.deref();
            let t = t.deref();
            let (l, s, t) = if upper(s) {
                (true, s, t)
            } else if upper(t) {
                (true, t, s)
            } else {
                (false, s, t)
            };
            if l {
                let v = large.entry(s.to_owned()).or_insert_with(Vec::new);
                let t = number(&mut small, t.to_owned());
                let d = v.clone();
                v.push(t);
                Box::new(d.into_iter().map(move |s| (s, t)))
                    as Box<dyn Iterator<Item = (usize, usize)>>
            } else {
                let s = number(&mut small, s.to_owned());
                let t = number(&mut small, t.to_owned());
                Box::new(once((s, t)))
                    as Box<dyn Iterator<Item = (usize, usize)>>
            }
        })
        .flat_map(|(s, t)| [(s, t), (t, s)])
        .filter(|(s, t)| *s != 1 && *t != 0)
    {
        result
            .entry(s)
            .or_insert_with(HashMap::new)
            .entry(t)
            .and_modify(|v| *v += 1)
            .or_insert(1);
    }
    result
}

fn upper(x: &str) -> bool {
    x.chars().next().map(char::is_uppercase).unwrap_or(false)
}

fn number<K: Eq + std::hash::Hash>(
    repo: &mut HashMap<K, usize>,
    name: K,
) -> usize {
    let s = repo.len();
    *repo.entry(name).or_insert(s)
}