Advent of Code Day LAN-Party

Tag 23: LAN-Party

Github Repo – Lösungen

Die heutige Herausforderung war eher gelaufen und einigermaßen einfach (zumindest war Teil 1).

Teil 1:

Sammeln Sie alle Verbindungen in Trios, bei denen einer der Dreieckscomputer mit t beginnt. So einfach ist das eigentlich, dann zählen Sie die Anzahl der Dreiecke.

Um dies zu erreichen, erstellen wir eine Zuordnung von Knoten -> Verbindungen (Nachbarn), sodass unser Verbindungsobjekt etwa so aussehen würde:

connections = {
    'kh': {'tc', 'dr'},
    'tc': {'kh', 'dr', 'zx'},
    'dr': {'kh', 'tc', 'xy'},
    'zx': {'tc'},
    'xy': {'dr', 'tz'},
    'tz': {'xy'}
}

Um die Trios zu erhalten, können wir über die Verbindungen iterieren und ihre Nachbarn abrufen – denken Sie daran, dass Knoten in Verbindungen in Python eine Schleife über die Schlüssel durchführen und die Werte nicht zurückgeben. Um auf die Werte zuzugreifen, müssen wir die Schlüssel (Knoten) verwenden, um über einen Indexverbindungen[Knoten] darauf zuzugreifen.

Für jedes Paar von Knotennachbarn werden Kombinationen generiert. Zum Beispiel:

Wenn Knoten = 'kh' und Nachbarn = {'tc', 'dr'}, sind die Paare ('tc', 'dr'). Es prüft, ob die beiden Nachbarn (Nachbar1 und Nachbar2) auch miteinander verbunden sind (über Verbindungen[Nachbar1]).

Wenn sie verbunden sind, besteht ein Dreieck zwischen Knoten, Nachbar1 und Nachbar2.
Das Dreieck wird sortiert und einem Satz hinzugefügt, um Duplikate zu vermeiden.

Suchen Sie dann alle Verbindungen, bei denen einer der Knoten mit t beginnt, indem Sie
verwenden

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

Teil 2

In Teil 2 müssen wir den größten Satz miteinander verbundener Computer finden. Wenn wir mit einem graphenähnlichen Setup arbeiten, nennen wir miteinander verbundene Knoten eine Clique.

Lassen Sie uns dies mithilfe des Bron-Kerbosch-Algorithmus aufschlüsseln. Der Bron-Kerbosch-Algorithmus wird verwendet, um die größten Gruppen (Cliquen genannt) in einem Diagramm zu finden. In diesem Zusammenhang ist ein Graph lediglich eine Ansammlung von Knoten (wie Computern), die durch Kanten (Verbindungen) verbunden sind. Hier erfahren Sie, wie der Algorithmus funktioniert und wie er sich auf die Lösung unseres Rätsels auswirkt.

Was ist eine Clique?

Eine Clique ist eine Gruppe von Knoten, bei der jeder Knoten direkt mit jedem anderen Knoten verbunden ist.

Stellen Sie sich vor, Sie sind auf einer Party, jeder kennt jeden in der Gruppe. Wenn auch nur eine Person jemand anderen nicht kennt, handelt es sich nicht um eine Clique.

In unserem Puzzle besteht das Ziel darin, die größte Gruppe miteinander verbundener Computer auf der LAN-Party zu finden. Diese Gruppe ist die größte Clique.

Was ist eine Teilmenge?

Eine Teilmenge ist ein kleinerer Teil einer größeren Gruppe, zum Beispiel:

Wenn die größte Clique (A,B,C,D) ist, könnten die kleineren Teilmengen A,B,CorB C D` sein, wo sie alle verbunden sind. Diese Teilmengen sind immer noch Cliquen, da alle Knoten in der Teilmenge verbunden sind.

Warum den Bron-Kerbosch-Algorithmus verwenden?

Das Finden der größten Clique mit roher Gewalt (Ausprobieren aller möglichen Gruppen) ist bei großen Eingaben langsam. Wenn es beispielsweise 3.000 Computer gibt, müssen Milliarden möglicher Gruppen überprüft werden.

Der Bron-Kerbosch-Algorithmus beschleunigt diesen Prozess durch:

• Beginnen Sie mit kleineren Gruppen (Teilmengen) und erweitern Sie diese.

• Früh aufhören, wenn eine Gruppe nicht zu einer größeren Clique heranwachsen kann.

• Vermeidung wiederholter Überprüfungen derselben Teilmengen.

Wie funktioniert es?

Der Bron-Kerbosch-Algorithmus arbeitet rekursiv, das heißt, er ruft sich immer wieder selbst auf, um Schritt für Schritt Cliquen aufzubauen. So funktioniert es:

Eingabe:
R: Eine Gruppe von Knoten, die eine Clique bilden könnten (beginnt leer).
P: Eine Liste von Knoten, die der Clique noch beitreten können (beginnt mit allen Knoten).
X: Eine Liste der Knoten, die wir bereits überprüft haben (beginnt leer).

Schritte:
Wenn P und X beide leer sind:
R ist eine maximale Clique (Sie können ihr keine weiteren Knoten hinzufügen). Speichern Sie dadurch R.

Sonst:
Wählen Sie einen Knoten aus P und fügen Sie ihn zu R hinzu.
Aktualisieren ? Und ? um nur Knoten einzubeziehen, die mit dem neuen R verbunden sind.

Rufen Sie den Algorithmus erneut mit dem neuen R,P und
auf X.

Wenn Sie fertig sind, verschieben Sie den Knoten von P nach X (er wird verarbeitet).

Dies wird wiederholt, bis alle Knoten verarbeitet sind, um sicherzustellen, dass alle Cliquen ohne redundante Prüfungen gefunden werden.

Wie löst dies das Rätsel?

Eingabe: Angenommen, wir haben eine Liste von Computerverbindungen, etwa:

Python
A-B
A-C
B-C
B-D
C-D

Diese Verbindungen stellen einen Graphen dar, in dem Knoten (Computer) durch Kanten (Drähte) verbunden sind.

Ziel: Finden Sie die größte Gruppe von Computern, bei denen jeder direkt mit jedem anderen Computer verbunden ist.

Prozess:

Der Algorithmus beginnt mit kleineren Gruppen (Teilmengen) und versucht, diese zu Cliquen zu vergrößern.
Es stoppt, wenn eine Gruppe nicht weiter wachsen kann (maximale Cliquen).

Unter allen Cliquen wird die größte identifiziert.

Ausgabe:
Die größte Clique ist beispielsweise
{B,C,D}.

Was ist mit Teilmengen?
Im Zusammenhang mit dem Rätsel:

Teilmengen einer Clique (z. B. {B,C} aus {B,C,D}) sind nicht interessant, da sie kleiner als die größte Clique sind.

Der Algorithmus vermeidet redundante Prüfungen von Teilmengen, indem er die verarbeiteten Knoten (X) verfolgt.

Rekapitulieren:

Clique: Eine Gruppe, in der jeder Knoten mit jedem anderen Knoten verbunden ist.

Teilmenge: Eine kleinere Gruppe aus einer größeren Clique.

Bron-Kerbosch:
Findet alle Cliquen in einem Diagramm.
Konzentriert sich auf die größten Cliquen, ohne Zeit mit kleineren Untergruppen zu verschwenden.

Rätsellösung:
Verwenden Sie den Algorithmus, um die größte Gruppe miteinander verbundener Computer auf der LAN-Party zu finden.

Ich hoffe, dies hat Ihnen geholfen, die Lösung zu verstehen, mehr über den Bron-Kerbosch-Algorithmus zu erfahren und etwas Neues über die Python-Syntax zu erfahren.

Wie immer können Sie mir gerne folgen oder mich auf Twitter erreichen.

Das Ergebnis ist die größte Clique, die die Lösung des Rätsels darstellt.

Weitere hilfreiche Python-Punkte:

Der rekursive Aufruf von Bron-Kerbosch übergibt einige modifizierte Eigenschaften r | Knoten, P & Verbindungen[Knoten].

In Python

r | Knoten – erstellt einen neuen Satz mit allen Knoten aus dem aktuellen Knotensatz in der Clique, die wir erstellen (r), plus einem weiteren Knoten, den wir hinzufügen.

p & Verbindungen[Knoten] – Dadurch wird ein neuer Satz erstellt, der nur die Knoten enthält, die:

• Befinden sich in beiden p (der Menge der Knoten, die noch Teil der Clique sein können).

• Sind auch im Verbindungsknoten.

Erklärung:
& ist der Schnittoperator für Mengen.
Verbindungen[Knoten] ist die Menge der Knoten, die direkt mit Knoten verbunden sind.

p & Verbindungen[Knoten] bedeutet „die gemeinsamen Knoten zwischen p und Verbindungen[Knoten] finden.“

Das obige ist der detaillierte Inhalt vonAdvent of Code Day LAN-Party. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!