Python3
Another day solved with optimized logic
Method build_graph took : 1.327543 milliseconds
Method count_unique_triads took : 903.221 microseconds
Method find_largest_clique took : 926.006 microseconds
Method solver took : 3.570724 milliseconds
Again, Linux handles python better with a final solve time of a combined ~3.6 ms. still it is quite fast on windows with only 0.5 ms increase.
Still having fun adding typing and comments with VSCode + Qwen-coder 1.5B running locally. feels so nice to be proud of readable and optimized code.
Code
from os.path import dirname,realpath,join
from itertools import combinations as itertools_combinations
from collections import defaultdict
from collections.abc import Callable
def profiler(method) -> Callable[..., any]:
from time import perf_counter_ns
def wrapper_method(*args: any, **kwargs: any) -> any:
start_time = perf_counter_ns()
ret = method(*args, **kwargs)
stop_time = perf_counter_ns() - start_time
time_len = min(9, ((len(str(stop_time))-1)//3)*3)
time_conversion = {9: 'seconds', 6: 'milliseconds', 3: 'microseconds', 0: 'nanoseconds'}
print(f"Method {method.__name__} took : {stop_time / (10**time_len)} {time_conversion[time_len]}")
return ret
return wrapper_method
@profiler
def build_graph(connections: list[str]) -> defaultdict[set[str]]:
"""
Builds an adjacency list from the list of connections.
"""
adj = defaultdict(set)
for conn in connections:
nodes = conn.strip().split('-')
node1, node2 = nodes
adj[node1].add(node2)
adj[node2].add(node1)
return adj
@profiler
def count_unique_triads(adj: defaultdict[set[str]]) -> int:
"""
Counts the number of unique triads where a 't_node' is connected to two other nodes
that are also directly connected to each other. Ensures that each triad is counted only once.
"""
unique_triads = set()
# Identify all nodes starting with 't' (case-insensitive)
t_nodes = [node for node in adj if node.lower().startswith('t')]
for t_node in t_nodes:
neighbors = adj[t_node]
if len(neighbors) < 2:
continue # Need at least two neighbors to form a triad
# Generate all unique unordered pairs of neighbors
for node1, node2 in itertools_combinations(neighbors, 2):
if node2 in adj[node1]:
# Create a sorted tuple to represent the triad uniquely
triad = tuple(sorted([t_node, node1, node2]))
unique_triads.add(triad)
return len(unique_triads)
def all_connected(nodes: tuple, adj: defaultdict[set[str]]) -> bool:
"""
Determines if all nodes are connected to each other by checking if every node is reachable from any other node.
Effectively determines if a clique exists.
"""
for i,node in enumerate(nodes):
for j in range(i + 1, len(nodes)):
if nodes[j] not in adj[node]:
return False
return True
@profiler
def find_largest_clique(adj: defaultdict[set[str]]) -> list[str]:
"""
Iterates over each vertex and its neighbors to find the largest clique. A clique is a subset of nodes where every pair of nodes is connected by an edge.
The function returns the vertices of the largest clique found. If no clique is found, it returns an empty list.
"""
# Keep track of the largest connected set found so far
best_connected_set = tuple(['',''])
best_connected_set_len = len(best_connected_set)
# Iterate over each vertex in the graph with the neighbors
for vertex, neighbors in adj.items():
# Since the clique must have all nodes share similar neighbors,
# then we can start with the size of the neighbors and iterate down to a clique size of the best connected set size
for i in range(len(neighbors), best_connected_set_len-1, -1):
# Iterate over all combinations of neighbors with size i
for comb in itertools_combinations(neighbors, r=i):
if all_connected(comb, adj):
if len((*comb, vertex)) > best_connected_set_len:
best_connected_set = (*comb, vertex)
best_connected_set_len = len(best_connected_set)
break
return sorted(best_connected_set)
# Solve Part 1 and Part 2 of the challenge at the same time
@profiler
def solver(connections: str) -> tuple[int, str]:
# Build the graph
adj = build_graph(connections.splitlines())
# return the count of unique triads and the largest clique found
return count_unique_triads(adj),','.join(find_largest_clique(adj))
if __name__ == "__main__":
BASE_DIR = dirname(realpath(__file__))
with open(join(BASE_DIR, r'input'), 'r') as f:
input_data = f.read().replace('\r', '').strip()
result = solver(input_data)
print("Part 1:", result[0], "\nPart 2:", result[1])