Day 23: LAN Party
Today's challenge was rather run, and somewhat simple (or at least Part 1 was).
Part 1:
Collect all the connections in trios where any of the triangles computers begin with t. Simple as that really, then count the number of triangles.
To achieve this we create a mapping of node -> connections (neighbors) , so our connections object would look something resembling:
connections = {
'kh': {'tc', 'dr'},
'tc': {'kh', 'dr', 'zx'},
'dr': {'kh', 'tc', 'xy'},
'zx': {'tc'},
'xy': {'dr', 'tz'},
'tz': {'xy'}
}
To gain the trios, we can iterate over the connections, and retrieve their neighbours - remember in Python for node in connections will loop over the keys, and not return the values. To access the values, we need to use the keys (node) to to access them via an index connections[node].
For each pair of neighbour's of node, it generates combinations. For example:
If node = 'kh' and neighbours = {'tc', 'dr'}, the pairs are ('tc', 'dr'). It checks if the two neighbours (neighbor1 and neighbor2) are also connected to each other (via connections[neighbor1]).
If they are connected, a triangle exists between node, neighbor1, and neighbor2.
The triangle is sorted and added to a set to avoid duplicates.
Then find all the connections where any of the nodes begin with t using
triangles_with_t = [triangle for triangle in triangles if any(
node.startswith('t') for node in triangle)]
Part 2
On part 2 we need to find the largest set of inter-connected computers. When working with a graph like setup, interconnected nodes we call a clique.
Let's break this down using the Bron-Kerbosch algorithm. The Bron-Kerbosch algorithm is used to find the largest groups (called cliques) in a graph. In this context, a graph is just a collection of nodes (like computers) connected by edges (connections). Here's how the algorithm works and how it relates to solving our puzzle.
What’s a Clique?
A clique is a group of nodes where every node is directly connected to every other node.
Imagine you're at a party, everyone knows everyone else in the group. If even one person doesn’t know someone else, it’s not a clique.
In our puzzle, the goal is to find the largest group of interconnected computers at the LAN party. This group is the largest clique.
What is a subset?
A subset is a smaller piece of a larger group, for example:
If the largest clique is (A,B,C,D), then the smaller subsets could beA,B,CorB C D` where they're all connected. These subset are still cliques because all the nodes in the subset are connected.
Why Use the Bron-Kerbosch Algorithm?
Finding the largest clique by brute force (trying every possible group) is slow for large inputs. For example, if there are 3,000+ computers, there are billions of possible groups to check.
The Bron-Kerbosch algorithm makes this process faster by:
Starting with smaller groups (subsets) and expanding them.
Stopping early when a group can’t grow into a larger clique.
Avoiding repeated checks of the same subsets.
How does it work ?
The Bron-Kerbosch algorithm works recursively, meaning it keeps calling itself to build up cliques step by step. Here’s how it works:
Input:
R: A group of nodes that might form a clique (starts empty).
P: A list of nodes that can still join the clique (starts with all nodes).
X: A list of nodes we’ve already checked (starts empty).
Steps:
If P and X are both empty:
R is a maximal clique (you can’t add more nodes to it). Save R as a result.
Otherwise:
Pick a node from P and add it to R.
Update 𝑃 and 𝑋 to only include nodes connected the new R.
Call the algorithm again with the new R,P, and
X.
When finished, move the node from P to X (it’s processed).
This repeats until all nodes are processed, ensuring all cliques are found without redundant checks.
How Does This Solve the Puzzle?
Input: Say we have a list of computer connections, like:
python
A-B
A-C
B-C
B-D
C-D
These connections represent a graph where nodes (computers) are connected by edges (wires).
Goal: Find the largest group of computers where each one is directly connected to every other computer.
Process:
The algorithm starts with smaller groups (subsets) and tries to grow them into cliques.
It stops if a group can’t grow any further (maximal cliques).
Among all cliques, it identifies the largest one.
Output:
For the example, the largest clique is
{B,C,D}.
What About Subsets?
In the context of the puzzle:
Subsets of a clique (e.g. {B,C} from {B,C,D}) are not interesting because they’re smaller than the largest clique.
The algorithm avoids redundant checks of subsets by keeping track of processed nodes (X).
Recap:
Clique: A group where every node is connected to every other node.
Subset: A smaller group taken from a larger clique.
Bron-Kerbosch:
Finds all cliques in a graph.
Focuses on the largest cliques without wasting time on smaller subsets.
Puzzle Solution:
Use the algorithm to find the largest group of interconnected computers at the LAN party.
I hope this has helped you understand the solution, learn about the Bron-Kerbosch algorithm, and learn something new about Python syntax.
As always feel free to drop me a follow, or reach out on Twitter.
The result is the largest clique, which is the answer to the puzzle.
Other helpful Python points:
The Bron-Kerbosch recursive call, passes in some modified properties r | node, p & connections[node].
In Python
r | node - creates a new set with all the nodes from the current set of nodes in the clique we're building (r), plus another node we're adding.
p & connections[node] - This creates a new set that contains only the nodes that:
Are in both p (the set of nodes that can still be part of the clique).
Are also in connectionsnode.
Explanation:
& is the intersection operator for sets.
connections[node] is the set of nodes directly connected to node.
p & connections[node] means “find the common nodes between p and connections[node].”
Top comments (0)