# Advent of Code 2023 Day 25

## Day 25: Snowverload

https://adventofcode.com/2023/day/25

There is no snow, you decide to investigate the spot directly beneath the waterfall.

You find a buch of ~~lean, mean,~~ snow making machines connected with wires.

They don’t seem to be working, only displaying an error code on a screen. You call the technical snow-machine support and they tell you it’s a power overload error. That means there are too many machines connected and you should disconnect some.

You need to disconnect at least half of the equipment. There is not a lot of time left as it is almost Christmas, and you can only disconnect 3 wires.

Today’s input is a wiring diagram that shows how the machines are connected. An example input looks like this:

jqt: rhn xhk nvdrsh: frs pzl lsrxhk: hfxcmg: qnr nvd lhk bvbrhn: xhk bvb hfxbvb: xhk hfxpzl: lsr hfx nvdqnr: nvdntq: jqt hfx bvb xhknvd: lhklsr: lhkrzs: qnr cmg lsr rshfrs: qnr lhk lsr

Each line shows the name of a machine, a colon `:`

, and a list of the machines it is connected to that’s separated by spaces.

## Parsing

I represented the network of machines and cables as a graph in the form of a map. A key in that map is the name of a machine, the value is a list of machines it is connected to.

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})}

## Part 1

Disconnect 3 wires to split the network of machines into 2 groups. Count the amount of machines in each group.

The question asks what number you get if you multiply the amount of machines in those 2 groups.

In pseudo/skeleton-code:

let mut graph = parse(input);// find and remove the 3 separating edgesdelete_separating_edges(&mut graph);// count the amount of nodes reachable from a random starting node, that's the size of 1 halflet start = graph.keys().next().unwrap()let half1 = reachable_nodes(&graph, start);// derive the size of the other halflet half2 = graph.len() - half1;half1 * half2

## Option 1: count ALL the paths!

Find the path between every pair of nodes. We can assume the 3 most used edges (cables) are the 3 separating the 2 groups of nodes.

The reason for this is that every node in one half will have to use one of those 3 edges to reach any node in the other half. That magic number 3 is given in the question.

I used BFS to find the path from one node to all other nodes in one loop. Incrementing a count for each specific edge that was used.

### Helpers

The function that counts how many times each edge was used.

The order of the nodes does not matter, going from `abc`

to `xyz`

uses the same edge as going from `xyz`

to `abc`

.
That is why before incrementing the edge count, I sort those 2 strings first.

fn edge_usage<'a>(graph: &HashMap<&'a str, HashSet<&'a str>>) -> HashMap<(&'a str, &'a str), u32> {// key: ("from", "to"), value: amount of times usedlet 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 matterfor &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 nodefor 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 edgelet [min, max] = cmp::minmax(prev, curr);*edges.entry((min, max)).or_default() += 1;curr = prev;}}}edges}

In this version of the same function, I eliminated the nested loop that does the backtracking.

I did not increment the counts in `edges`

for a path between all possible pairs of nodes.
Instead, I incremented the count for an edge as the BFS was running.
This means some edges that are used in a buch of paths will only be counted once.

Because one of the 3 separating edges has to be used in every path that goes from one half to the other, the 3 most used edges will still be the separating 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 usedlet 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 matterfor &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 edgelet [min, max] = cmp::minmax(neighbour, node);*edges.entry((min, max)).or_default() += 1;}}}}edges}

A helper that takes in the original graph, computes the edge usage counts using the previous helper, then sorts those counts and returns the 3 most used 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()}

Finally a helper that counts the amount of nodes that are reachable when starting from a given node:

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()}

Now it’s time to put these 3 helpers together into the form of the skeletoncode I started with!

### Code

#![feature(cmp_minmax)]#![feature(iter_next_chunk)]pub fn part_1(input: &str) -> usize {// key: "from", value: list of "to"let mut graph = parse(input);// list of the 3 ("from", "to") edges that separate the graphlet separating_edges = most_used_edges(&graph);// remove the 3 separating edgesfor (node1, node2) in separating_edges {graph.entry(node1).or_default().remove(node2);graph.entry(node2).or_default().remove(node1);}// pick a random nodelet start = graph.keys().next().unwrap();// count how many nodes are reachable from that node now the separating edges are removedlet half1 = reachable_nodes(&graph, start);let half2 = graph.len() - half1;half1 * half2}

## Option 2: deleting until victorious

For this solution, pick 2 nodes and assume they are in separate halves. If they are not, that’s not a problem because eventually the code will know they’re not and move on until it finds a pair that is.

This solution finds a path from the starting node to the ending node. It has to have travelled across one of those 3 separating edges.

Then it deletes all edges along that path. It will delete one of the 3 separating edges, leaving 2.

The next path from that same starting node to the same ending node now has to travel across one of those 2 edges. The third time, all 3 separating nodes have been deleted, separating the graph in 2 halves.

The other edges that got deleted during this procedure have no impact, all nodes in a half will still be reachable.

Because from the problem statement we know it will be impossible to sever the graph with any other 3 cuts.

This means all nodes in a half are still reachable when starting from a random node in that half.

### Helpers

A helper function that finds a route between 2 nodes, and deletes all edges it used. It first finds a path while keeping track of the route it took, then it backtracks along that route while severing the edges it used:

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 waylet 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;}}

The `reachable_nodes`

helper from the previous solution is reused with some slight changes.
It now returns nothing if the graph wasn’t cut in 2.
In Rust, this is done with the `Option`

type.
The function either returns a count of a half, or it returns nothing:

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 2return None;}if seen.insert(neighbour) {q.push_back(neighbour);}}}Some(seen.len())}

These 2 helpers are then put together in the final code. It checks every combination of 2 nodes until it finds 2 that are in separate halves.

### Code

pub fn part_1(input: &str) -> usize {let graph = parse(input);graph.keys().tuple_combinations().find_map(|(from, to)| {let mut copy = graph.clone();// delete 3 routes starting at "from" and ending in "to"for _ in 0..3 {delete_route(&mut copy, from, to)}// if "from" and "to" were in 2 halves, the connecting edges were deleted and "to" will not be reachable starting at "from"// if this is the case, count how many nodes were reachable, this is one half. If not, move on to an other "from"-"to" pairlet half1 = reachable_nodes(©, from, to)?;let half2 = copy.len() - half1;Some(half1 * half2)}).unwrap()}

## Part 2

This part is very secret.

It started snowing, have a great year, and see you next year for more Advent of Come!

## Final code

1use std::collections::{HashMap, HashSet, VecDeque};23use itertools::Itertools;45fn parse(input: &str) -> HashMap<&str, HashSet<&str>> {6 input7 .lines()8 .map(|line| line.split_once(": ").unwrap())9 .fold(HashMap::new(), |mut acc, (from, rhs)| {10 for to in rhs.split_whitespace() {11 acc.entry(from).or_default().insert(to);12 acc.entry(to).or_default().insert(from);13 }14 acc15 })16}1718fn delete_route<'a>(graph: &mut HashMap<&'a str, HashSet<&'a str>>, from: &'a str, to: &'a str) {19 let mut q = VecDeque::from([from]);20 let mut seen = HashSet::from([from]);21 let mut prev_map = HashMap::new();2223 'outer: while let Some(node) = q.pop_front() {24 for &neighbour in graph.get(node).unwrap() {25 if seen.insert(neighbour) {26 q.push_back(neighbour);27 prev_map.insert(neighbour, node);28 if neighbour == to {29 break 'outer;30 }31 }32 }33 }3435 // delete every edge on the path "from"-"to"36 // if "from" and "to" were in the 2 halves, one of the connecting edges is guaranteed to be deleted this way37 let mut curr = to;38 while curr != from {39 let prev = prev_map.get(curr).unwrap();40 graph.entry(curr).or_default().remove(prev);41 graph.entry(prev).or_default().remove(curr);42 curr = prev;43 }44}4546fn reachable_nodes(graph: &HashMap<&str, HashSet<&str>>, from: &str, to: &str) -> Option<usize> {47 let mut q = VecDeque::from([from]);48 let mut seen = HashSet::from([from]);4950 while let Some(node) = q.pop_front() {51 for neighbour in graph.get(node).unwrap() {52 if *neighbour == to {53 // the graph was not cut in 254 return None;55 }56 if seen.insert(neighbour) {57 q.push_back(neighbour);58 }59 }60 }6162 Some(seen.len())63}6465pub fn part_1(input: &str) -> usize {66 let graph = parse(input);6768 graph69 .keys()70 .tuple_combinations()71 .find_map(|(from, to)| {72 let mut copy = graph.clone();7374 // delete 3 routes starting at "from" and ending in "to"75 for _ in 0..3 {76 delete_route(&mut copy, from, to)77 }7879 // if "from" and "to" were in 2 halves, the connecting edges were deleted and "to" will not be reachable starting at "from"80 // if this is the case, count how many nodes were reachable, this is one half. If not, move on to an other "from"-"to" pair81 let half1 = reachable_nodes(©, from, to)?;82 let half2 = copy.len() - half1;8384 Some(half1 * half2)85 })86 .unwrap()87}

Series navigation for: Advent of Code 2023