use std::collections::HashSet;

#[path = "../lib.rs"]
mod lib;

fn insert_node(name: &str, names: &mut Vec<String>, connections: &mut Vec<HashSet<usize>>) -> usize {
    if let Some(i) = names.iter().position(|n| n == name) {
        return i;
    } else {
        names.push(name.to_string());
        connections.push(HashSet::new());
        return names.len() - 1;
    }
}

fn parse_input() -> (Vec<String>, Vec<HashSet<usize>>) {
    let mut names = vec![];
    let mut connections = vec![];

    for line in lib::iter_input() {
        let (name1, name2) = line.split_once('-').unwrap();
        let i1 = insert_node(name1, &mut names, &mut connections);
        let i2 = insert_node(name2, &mut names, &mut connections);
        if i1 < i2 {
            connections[i1].insert(i2);
        } else {
            connections[i2].insert(i1);
        }
    }

    return (names, connections);
}

fn visit(stack: &mut Vec<usize>, names: &Vec<String>, connections: &Vec<HashSet<usize>>) -> (usize, Vec<usize>) {
    let mut part1 = 0;
    let mut part2 = stack.clone();

    if stack.len() == 3 && stack.iter().any(|j| names[*j].starts_with('t')) {
        part1 += 1;
    }

    let mut potential: Vec<usize> = vec![];
    if let Some(&l) = stack.last() {
        potential.extend(&connections[l]);
    } else {
        potential.extend(0..connections.len());
    };
    for i in potential {
        if !stack.iter().all(|j| connections[*j].contains(&i)) {
            continue;
        }

        stack.push(i);
        let (tmp1, tmp2) = visit(stack, names, connections);
        part1 += tmp1;
        if tmp2.len() > part2.len() {
            part2 = tmp2;
        }
        stack.pop();
    }

    return (part1, part2);
}

fn format_password(stack: Vec<usize>, names: &Vec<String>) -> String {
    let mut n: Vec<String> = stack.iter().map(|j| names[*j].clone()).collect();
    n.sort();
    return n.join(",");
}

fn main() {
    let (names, connections) = parse_input();

    let mut stack = vec![];
    let (part1, part2) = visit(&mut stack, &names, &connections);
    println!("part1: {}", part1);
    println!("part2: {}", format_password(part2, &names));
}