Zadanie

Dzisiejsze zadanie jest klasycznym zadaniem z teorii grafów. W naszym zadaniu komputery to wierzchołki, oznaczone są one jako stringi składające się z dwóch znaków, w danych wejściowych dostajemy listę krawędzi grafu w postaci:

Mamy znaleźć takie zbiory trzech komputerów że każdy jest połączony z każdym. Jest to problem znalezienia kliki w grafie. Problem ten jest NP-trudny, jednak dla klik o rozmiarach 3 nawet rozwiązanie typu brute force nie powinno sprawić większego problemu.

Dodatkowo mamy zwrócić tylko te kliki które posiadają choć jeden wierzchołek który zaczyna się na literę t.

Rozwiązanie

import sys
from collections import defaultdict
from itertools import combinations

graph = defaultdict(list)

# tworzymy listę sąsiedztwa reperezentującą graf
for line in sys.stdin.readlines():
    a, b = line.strip().split("-")
    graph[a].append(b)
    graph[b].append(a)

# zliczymy ile razy dana trójka wierzchołków się powtarza
counts = defaultdict(int)
for k, v in graph.items():
    for x, y in combinations(v, 2): # wszystkie pary sąsiadów
        counts[frozenset([k, x, y])] += 1

# filtrujemy tylko te trójki które trafiły się 3 razy
# i jeśli choć jeden z nich się zaczyna na literę t
part1 = 0
for s, count in counts.items():
    if count == 3 and any(l.startswith("t") for l in s):
        part1 += 1

print(part1)

Po uruchomieniu dostajemy poprawną odpowiedź

Część druga

Do zdobycia drugiej gwiazdki musimy się bardziej postarać, teraz musimy znaleźć największą możliwą klikę! W tym przypadku brute force nie zadziała gdyż ilośc kombinacji robi się zbyt duża, jak wspominałem problem jest NP-trudny, ale istnieją różne algorytmy które znajdują rozwiązanie w krótkim czasie o ile input nie jest za duży a w tym przypadku nie jest.

Jestem trochę zmęczony po 22 dniach pisania więc uznałem że pójdę na łatwiznę i użyję gotowej implementacji z paczki networkx:

import sys

import networkx as nx

G = nx.Graph()
for l in sys.stdin.readlines():
    a, b = l.strip().split("-")
    G.add_edge(a, b)

print(",".join(sorted(max(nx.find_cliques(G), key=lambda c: len(c)))))

Podsumowanie

Dzisiaj kluczowym było rozpoznanie problemu jako problemu znalezienia klik w grafie i użycie odpowiedniej paczki lub zaimplementowanie algorytmu który to robi. Myślę że warto się lepiej zaznajomić z paczką networkx bo wczytując się w nią powierzchownie widziałem że jest ona dosyć rozbudowana i posiada wiele ciekawych funkcji.