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('-')
        nodes.sort()
        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(['',''])
    # 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 2
        for i in range(len(neighbors), len(best_connected_set)-1, -1):
            # we don't check smaller cliques because they will be smaller than the current best connected set
            if i < len(best_connected_set):
                break
            for comb in itertools_combinations(neighbors, r=i):
                if all_connected(comb, adj):
                    best_connected_set = max(
                        (*comb, vertex), best_connected_set, key=len
                    )
                    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])