Advent of Code 2023 Day 25

fn parse(input: &str) -> HashMap<&str, HashSet<&str>> {
    input
        .lines()
        .map(|line| line.split_once(": ").unwrap())
        .fold(HashMap::new(), |mut acc, (from, rhs)| {
            for to in rhs.split_whitespace() {
                acc.entry(from).or_default().insert(to);
                acc.entry(to).or_default().insert(from);
            }
            acc
        })
}

let mut graph = parse(input);

// find and remove the 3 separating edges
delete_separating_edges(&mut graph);

// count the amount of nodes reachable from a random starting node, that's the size of 1 half
let start = graph.keys().next().unwrap()
let half1 = reachable_nodes(&graph, start);
// derive the size of the other half
let half2 = graph.len() - half1;

half1 * half2

fn edge_usage<'a>(graph: &HashMap<&'a str, HashSet<&'a str>>) -> HashMap<(&'a str, &'a str), u32> {
    // key: ("from", "to"), value: amount of times used
    let mut edges = HashMap::new();

    // starting at every node, follow a shortest path to every other node
    // count how many time each edge (from, to) was used. The order of (from, to) doesn't matter
    for &start in graph.keys() {
        let mut q = VecDeque::from([start]);
        let mut seen = HashSet::from([start]);
        let mut prev_map = HashMap::new();

        while let Some(node) = q.pop_front() {
            for &neighbour in graph.get(node).unwrap() {
                if seen.insert(neighbour) {
                    q.push_back(neighbour);
                    prev_map.insert(neighbour, node);
                }
            }
        }

        // count the amount of times an edge (connection between 2 nodes) was used by backtracking along the path taken to reach a node
        for node in graph.keys() {
            let mut curr = *node;
            while curr != start {
                let prev = *prev_map.get(curr).unwrap();
                // order of next and curr can be swapped, it remains the same edge
                let [min, max] = cmp::minmax(prev, curr);
                *edges.entry((min, max)).or_default() += 1;
                curr = prev;
            }
        }
    }

    edges
}

fn edge_usage<'a>(graph: &HashMap<&'a str, HashSet<&'a str>>) -> HashMap<(&'a str, &'a str), u32> {
    // key: ("from", "to"), value: amount of times used
    let mut edges = HashMap::new();

    // starting at every node, follow a shortest path to every other node
    // count how many time each edge (from, to) was used. The order of (from, to) doesn't matter
    for &start in graph.keys() {
        let mut q = VecDeque::from([start]);
        let mut seen = HashSet::from([start]);

        while let Some(node) = q.pop_front() {
            for &neighbour in graph.get(node).unwrap() {
                if seen.insert(neighbour) {
                    q.push_back(neighbour);
                    // increment usage number for the edge that was used
                    // the order of neighbour and node can be swapped, it remains the same edge
                    let [min, max] = cmp::minmax(neighbour, node);
                    *edges.entry((min, max)).or_default() += 1;
                }
            }
        }
    }

    edges
}

fn most_used_edges<'a>(graph: &HashMap<&'a str, HashSet<&'a str>>) -> [(&'a str, &'a str); 3] {
    edge_usage(&graph)
        .into_iter()
        .sorted_unstable_by_key(|(_, count)| *count)
        .rev()
        .map(|(edge, _)| edge)
        .next_chunk()
        .unwrap()
}

fn reachable_nodes(graph: &HashMap<&str, HashSet<&str>>, start: &str) -> usize {
    let mut q = VecDeque::from([start]);
    let mut seen = HashSet::from([start]);

    while let Some(node) = q.pop_front() {
        for next in graph.get(node).unwrap() {
            if seen.insert(next) {
                q.push_back(next);
            }
        }
    }

    seen.len()
}

fn delete_route<'a>(graph: &mut HashMap<&'a str, HashSet<&'a str>>, from: &'a str, to: &'a str) {
    let mut q = VecDeque::from([from]);
    let mut seen = HashSet::from([from]);
    let mut prev_map = HashMap::new();

    'outer: while let Some(node) = q.pop_front() {
        for &neighbour in graph.get(node).unwrap() {
            if seen.insert(neighbour) {
                q.push_back(neighbour);
                prev_map.insert(neighbour, node);
                if neighbour == to {
                    break 'outer;
                }
            }
        }
    }

    // delete every edge on the path "from"-"to"
    // if "from" and "to" were in the 2 halves, one of the connecting edges is guaranteed to be deleted this way
    let mut curr = to;
    while curr != from {
        let prev = prev_map.get(curr).unwrap();
        graph.entry(curr).or_default().remove(prev);
        graph.entry(prev).or_default().remove(curr);
        curr = prev;
    }
}

fn reachable_nodes(graph: &HashMap<&str, HashSet<&str>>, from: &str, to: &str) -> Option<usize> {
    let mut q = VecDeque::from([from]);
    let mut seen = HashSet::from([from]);

    while let Some(node) = q.pop_front() {
        for neighbour in graph.get(node).unwrap() {
            if *neighbour == to {
                // the graph was not cut in 2
                return None;
            }
            if seen.insert(neighbour) {
                q.push_back(neighbour);
            }
        }
    }

    Some(seen.len())
}