Module aoc::year2023::day25

Snowverload

We need to find a minimum cut of 3 edges that divides the graph into 2 parts. Several general purpose algorithms exist:

• Deterministic Stoer–Wagner algorithm
• Probabilistic Karger’s algorithm

The max-flow min-cut theorem also allows the minimum cut to be expressed as a maximum flow problem. There are several general purpose algorithms:

• Ford–Fulkerson algorithm
• Edmonds–Karp algorithm

We can use a simplified version of the Edmonds–Karp algorithm taking advantage of two pieces of information and a special property of the input graph structure:

• The minimum cut size is already known to be 3.
• All edge weights (or flow capacity) are 1.
• The 3 edges to be cut are in the “middle” of the graph, that is the graph looks something like:

        * *       * *
      * * * * - * * * *
    * * * * * - * * * * *
      * * * * - * * * *
        * *       * *
  

Our high level approach is as follows:

• Pick any arbitrary node
• Find a start node furthest from it.
• Find a end node furthest from the start node.

The key insight is that the start and end nodes must be on opposite sides of the cut. We then BFS 3 times from the start to the end to find 3 different shortest paths. We keep track of the edges each time and only allow each edge to be used once so that each path has no common edges.

This will “saturate” the 3 edges across the middle. Finally we BFS from the start node a fourth time. As the middle links are already used, this will only be able to reach the nodes on start’s side of the graph and will find our answer.

The complexity of each BFS is O(V + E) and we perform a total of 6. To speed things up even further some low level optimizations are used:

• Numeric node and edge identifiers to allow vec to store previously seen values instead of HashMap.
• Linked list of path from start to end, stored in a vec using indices for simplicity and cache locality. This blog post series describes the complexity of using actual references.

Structs

• Input
  Store the graph as an adjacency list. Each node has a unique index in the nodes vec. Each directed edge has a unique index in the edges vec.

Functions

• flow 🔒
  Simplified approach based on Edmonds–Karp algorithm.
• furthest 🔒
  BFS across the graph to find the furthest nodes from start.
• parse
  Convert the input to use numeric indices instead of string keys for speed. Each node is assigned a unique index on a first come first served basis. Then the edges are gathered into a single vec so that each edge also has a unique index.
• part1
• part2
• perfect_minimal_hash 🔒
  Each node’s name is exactly 3 lowercase ASCII letters. First we calculate a perfect hash by converting to a base 26 number. Then we construct a perfect minimal hash by using the first index to lookup a contigous index into the nodes vec.