Advent of Code 2024 - Day 23: LAN Party

Advent of Code 2024 – C# and Python (23 Part Series)

Day 23: LAN Party

Github Repo – Solutions

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:


<span>connections</span> <span>=</span> <span>{</span>
    <span>'</span><span>kh</span><span>'</span><span>:</span> <span>{</span><span>'</span><span>tc</span><span>'</span><span>,</span> <span>'</span><span>dr</span><span>'</span><span>},</span>
    <span>'</span><span>tc</span><span>'</span><span>:</span> <span>{</span><span>'</span><span>kh</span><span>'</span><span>,</span> <span>'</span><span>dr</span><span>'</span><span>,</span> <span>'</span><span>zx</span><span>'</span><span>},</span>
    <span>'</span><span>dr</span><span>'</span><span>:</span> <span>{</span><span>'</span><span>kh</span><span>'</span><span>,</span> <span>'</span><span>tc</span><span>'</span><span>,</span> <span>'</span><span>xy</span><span>'</span><span>},</span>
    <span>'</span><span>zx</span><span>'</span><span>:</span> <span>{</span><span>'</span><span>tc</span><span>'</span><span>},</span>
    <span>'</span><span>xy</span><span>'</span><span>:</span> <span>{</span><span>'</span><span>dr</span><span>'</span><span>,</span> <span>'</span><span>tz</span><span>'</span><span>},</span>
    <span>'</span><span>tz</span><span>'</span><span>:</span> <span>{</span><span>'</span><span>xy</span><span>'</span><span>}</span>
<span>}</span>
<span>connections</span> <span>=</span> <span>{</span>
    <span>'</span><span>kh</span><span>'</span><span>:</span> <span>{</span><span>'</span><span>tc</span><span>'</span><span>,</span> <span>'</span><span>dr</span><span>'</span><span>},</span>
    <span>'</span><span>tc</span><span>'</span><span>:</span> <span>{</span><span>'</span><span>kh</span><span>'</span><span>,</span> <span>'</span><span>dr</span><span>'</span><span>,</span> <span>'</span><span>zx</span><span>'</span><span>},</span>
    <span>'</span><span>dr</span><span>'</span><span>:</span> <span>{</span><span>'</span><span>kh</span><span>'</span><span>,</span> <span>'</span><span>tc</span><span>'</span><span>,</span> <span>'</span><span>xy</span><span>'</span><span>},</span>
    <span>'</span><span>zx</span><span>'</span><span>:</span> <span>{</span><span>'</span><span>tc</span><span>'</span><span>},</span>
    <span>'</span><span>xy</span><span>'</span><span>:</span> <span>{</span><span>'</span><span>dr</span><span>'</span><span>,</span> <span>'</span><span>tz</span><span>'</span><span>},</span>
    <span>'</span><span>tz</span><span>'</span><span>:</span> <span>{</span><span>'</span><span>xy</span><span>'</span><span>}</span>
<span>}</span>
connections = {
    'kh': {'tc', 'dr'},
    'tc': {'kh', 'dr', 'zx'},
    'dr': {'kh', 'tc', 'xy'},
    'zx': {'tc'},
    'xy': {'dr', 'tz'},
    'tz': {'xy'}
}

Enter fullscreen mode Exit fullscreen mode

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


<span>triangles_with_t</span> <span>=</span> <span>[</span><span>triangle</span> <span>for</span> <span>triangle</span> <span>in</span> <span>triangles</span> <span>if</span> <span>any</span><span>(</span>
    <span>node</span><span>.</span><span>startswith</span><span>(</span><span>'</span><span>t</span><span>'</span><span>)</span> <span>for</span> <span>node</span> <span>in</span> <span>triangle</span><span>)]</span>
<span>triangles_with_t</span> <span>=</span> <span>[</span><span>triangle</span> <span>for</span> <span>triangle</span> <span>in</span> <span>triangles</span> <span>if</span> <span>any</span><span>(</span>
    <span>node</span><span>.</span><span>startswith</span><span>(</span><span>'</span><span>t</span><span>'</span><span>)</span> <span>for</span> <span>node</span> <span>in</span> <span>triangle</span><span>)]</span>
triangles_with_t = [triangle for triangle in triangles if any(
    node.startswith('t') for node in triangle)]

Enter fullscreen mode Exit fullscreen mode

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].”

Advent of Code 2024 – C# and Python (23 Part Series)

原文链接：Advent of Code 2024 – Day 23: LAN Party

展开阅读全文

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END