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])

the basic Bron-Kerbosch algorithm

class Day23 : Puzzle {

    private val connections = ArrayList<Pair<String, String>>()

    private val tripleCache = HashSet<Triple<String, String, String>>()

    override fun readFile() {
        val input = readInputFromFile("src/main/resources/day23.txt")
        for (line in input.lines()) {
            val parts = line.split("-")
            connections.add(Pair(parts[0], parts[1]))
        }
    }

    override fun solvePartOne(): String {
        val triples = getConnectionTriples(connections)
        tripleCache.addAll(triples) // for part 2
        val res = triples.count { it.first.startsWith("t") || it.second.startsWith("t") || it.third.startsWith("t") }
        return res.toString()
    }

    private fun getConnectionTriples(connectionList: List<Pair<String, String>>): List<Triple<String, String, String>> {
        val triples = ArrayList<Triple<String, String, String>>()
        for (connection in connectionList) {
            val connectionListTemp = getAllConnections(connection.first, connectionList)
            for (i in connectionListTemp.indices) {
                for (j in i + 1 until connectionListTemp.size) {
                    val con1 = connectionListTemp[i]
                    val con2 = connectionListTemp[j]
                    if (Pair(con1, con2) in connectionList || Pair(con2, con1) in connectionList) {
                        val tripleList = mutableListOf(connection.first, con1, con2)
                        tripleList.sort()
                        triples.add(Triple(tripleList[0], tripleList[1], tripleList[2]))
                    }
                }
            }
        }
        return triples.distinct()
    }

    private fun getAllConnections(connection: String, connectionList: List<Pair<String, String>>): List<String> {
        val res = HashSet<String>()
        for (entry in connectionList) {
            when (connection) {
                entry.first -> res.add(entry.second)
                entry.second -> res.add(entry.first)
            }
        }
        return res.toList()
    }

    override fun solvePartTwo(): String {
        val pools = getPools(connections)
        println(pools)
        val res = pools.maxByOrNull { it.size }!!
        return res.joinToString(",")
    }

    // will get all pools with a minimum size of 4
    // this method makes some naive assumptions, but works for the example and my puzzle input
    private fun getPools(connectionList: List<Pair<String, String>>): List<List<String>> {
        val pools = ArrayList<List<String>>()
        val triples = tripleCache
        val nodes = connectionList.map { listOf(it.first, it.second) }.flatten().toHashSet()

        for (node in nodes) {
            val contenders = triples.filter { it.first == node || it.second == node || it.third == node }
            if (contenders.size < 2) continue // expect the minimum result to be 4, for efficiency

            // if *all* nodes within *all* triples are interconnected, add to pool
            // this may not work for all inputs!
            val contenderList = contenders.map { listOf(it.first, it.second, it.third) }.flatten().distinct()
            if (checkAllConnections(contenderList, connectionList)) {
                pools.add(contenderList.sorted())
            }
        }

        return pools.distinct()
    }

    private fun checkAllConnections(pool: List<String>, connectionList: List<Pair<String, String>>): Boolean {
        for (i in pool.indices) {
            for (j in i + 1 until pool.size) {
                val con1 = pool[i]
                val con2 = pool[j]
                if (Pair(con1, con2) !in connectionList && Pair(con2, con1) !in connectionList) {
                    return false
                }
            }
        }
        return true
    }
}

use rustc_hash::{FxHashMap, FxHashSet};

fn parse(input: &str) -> (Vec<Vec<usize>>, FxHashMap<&str, usize>) {
    let mut graph = Vec::new();
    let mut names: FxHashMap<&str, usize> = FxHashMap::default();
    for l in input.lines() {
        let (vs, ws) = l.split_once('-').unwrap();
        let v = *names.entry(vs).or_insert_with(|| {
            graph.push(vec![]);
            graph.len() - 1
        });
        let w = *names.entry(ws).or_insert_with(|| {
            graph.push(vec![]);
            graph.len() - 1
        });
        graph[v].push(w);
        graph[w].push(v);
    }
    (graph, names)
}

fn part1(input: String) {
    let (graph, names) = parse(&input);
    let mut triples: FxHashSet<[usize; 3]> = FxHashSet::default();
    for (_, &v) in names.iter().filter(|(name, _)| name.starts_with('t')) {
        for (i, &u) in graph[v].iter().enumerate().skip(1) {
            for w in graph[v].iter().take(i) {
                if graph[u].contains(w) {
                    let mut triple = [u, v, *w];
                    triple.sort();
                    triples.insert(triple);
                }
            }
        }
    }
    println!("{}", triples.len());
}

// Bron-Kerbosch algorithm for finding all maximal cliques in a graph
fn bron_kerbosch(
    graph: &[Vec<usize>],
    r: &mut Vec<usize>,
    mut p: FxHashSet<usize>,
    mut x: FxHashSet<usize>,
) -> Vec<Vec<usize>> {
    if p.is_empty() && x.is_empty() {
        return vec![r.to_vec()];
    }
    let mut maximal_cliques = Vec::new();
    let Some(&u) = p.iter().next() else {
        return maximal_cliques;
    };
    let mut p_pivot = p.clone();
    for w in &graph[u] {
        p_pivot.remove(w);
    }
    for v in p_pivot {
        let pn = graph[v].iter().filter(|w| p.contains(w)).copied().collect();
        let xn = graph[v].iter().filter(|w| x.contains(w)).copied().collect();
        r.push(v);
        let new_cliques = bron_kerbosch(graph, r, pn, xn);
        r.pop();
        maximal_cliques.extend(new_cliques);
        p.remove(&v);
        x.insert(v);
    }
    maximal_cliques
}

fn part2(input: String) {
    let (graph, names) = parse(&input);
    let p = (0..graph.len()).collect();
    let mut r = Vec::new();
    let maximal_cliques = bron_kerbosch(&graph, &mut r, p, FxHashSet::default());
    let maximum_clique = maximal_cliques
        .iter()
        .max_by_key(|clique| clique.len())
        .unwrap();
    let mut lan_names: Vec<&str> = names
        .iter()
        .filter(|(_, v)| maximum_clique.contains(v))
        .map(|(name, _)| *name)
        .collect();
    lan_names.sort_unstable();
    println!("{}", lan_names.join(","));
}

util::aoc_main!();

#include "common.h"

#define VZ 520	/* max no. vertices */
#define SZ 32	/* max set size */

static char names[VZ][3];
static char adj[VZ][VZ];
static int nvert;

static int
to_id(const char *name)
{
	int i;

	for (i=0; i<nvert; i++)
		if (!strcmp(name, names[i]))
			return i;

	assert(nvert < VZ);
	assert(strlen(name) < LEN(*names));

	snprintf(names[nvert++], sizeof(*names), "%s", name);
	return i;
}

static int
cmp_id(const void *a, const void *b)
{
	return strcmp(names[*(int*)a], names[*(int*)b]);
}

/*
 * Construct all unique combinations of nodes, with every extension,
 * confirm they're all connected. Essentally this but recursive:
 *
 *   for (a=0; a<nvert; a++)
 *   for (b=a+1; b<nvert; b++)
 *   for (c=b+1; c<nvert; c++)
 *     ...
 *
 * Note the inner loops continue forward from the point of the outside
 * loop, avoiding duplicate combinations.
 *
 * 'set' and 'best' are arrays of size SZ, length 'sz' and 'bz'. 'set'
 * is the current working state; 'best' is a copy of the longest known
 * set.
 */
static int
max_set(int *set, int sz, int *best, int bz)
{
	int bz1, v,i;

	assert(sz < SZ);

	/* for each potential candidate */
	for (v = sz ? set[sz-1]+1 : 0; v < nvert; v++) {
		 /* adjacent to all in current set? */
		for (i=0; i<sz && adj[set[i]][v]; i++) ;
		if (i != sz) continue;
		 /* recur and update 'best size' if needed */
		set[sz] = v;
		if (bz < (bz1 = max_set(set, sz+1, best, bz))) bz = bz1;
	}

	/* store longest known set in 'best' */
	if (sz > bz)
		memcpy(best, set, (bz = sz) * sizeof(*best));

	return bz;
}

int
main(int argc, char **argv)
{
	static int set[SZ], best[SZ];
	char buf[8];
	int p1=0, a,b,c, i, bz;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));
	
	while (fgets(buf, sizeof(buf), stdin)) {
		assert(strlen(buf) >= 5);
		buf[2] = buf[5] = '\0';
		a = to_id(buf);
		b = to_id(buf+3);
		adj[a][b] = adj[b][a] = 1;
	}

	for (a=0; a<nvert; a++)
	for (b=a+1; b<nvert; b++)
	for (c=b+1; c<nvert; c++)
		p1 += adj[a][b] && adj[a][c] && adj[b][c] && (
		      names[a][0] == 't' || names[b][0] == 't' ||
		      names[c][0] == 't');

	printf("23: %d ", p1);

	bz = max_set(set, 0, best, 0);
	qsort(best, bz, sizeof(*best), cmp_id);

	for (i=0; i<bz; i++)
		printf(i ? ",%s" : "%s", names[best[i]]);

	putchar('\n');
	return 0;
}