Advent of Code

The setup here is that we have a list of connections between computers, such as:

Where each computer is identified by two letters, and the connections are biderectional. From the connections we can determine a graph of the network. I decided to store it in a dict, mapping each computer name to a set of its neighbours.

Network = dict[str, set[str]]

def parse_input() -> Network:
    with open("day23", 'r') as fp:
        data = [l.strip().split('-') for l in fp.readlines()]

    network = defaultdict(set)
    for c1, c2 in data:
        network[c1].add(c2)
        network[c2].add(c1)

    return network

Part 1 - triplets

For part 1, we need to find all triplets of computers which are all connected to each others, and contain at least one computer whose name starts with a t.

We can find those triplets very easily in our graph: starting from each computer (whose name starts with t), we look at all their neighbours. If we start from A, and B is in their list of neighbour, then they form a triplet with every computer C that is in the neighbour list of both A and B. Since we store those neighbours as sets, we can use intersect to get those common neighbours.

def find_triplets(network: Network, predicate: Callable[[str], bool] = lambda x: True) -> list[tuple[str, str, str]]:
    triplets = set()
    for key, neighbours in network.items():
        if not predicate(key):
            continue
        for n in neighbours:
            if len((intersect := neighbours.intersection(network[n]))) >= 1:
                t = {tuple(sorted([key, n, x])) for x in intersect}
                triplets = triplets.union(t)
    return triplets

I made the “filter computers starting with t” part unecessarily generic with a predicate lambda function, which by default doesn’t filter anything. The triplets are stored in a set to avoid duplicates (as long as we sort the computer names before putting them in a tuple). And that’s about it for part 1, we just need to call the function with the appropriate predicate and we’re done. The answer for part 1 is the number of triplets we found.

network = parse_input()
triplets = find_triplets(network, lambda x: x.startswith('t'))
print(f"Part 1 answer: {len(triplets)}")

Part 2 - dense subnetwork

For part 2, we need to find the largest “dense” subnetwork, i.e. a part of the network where every node is connected to every other node. The answer is the list of the computers in that subnetwork, sorted alphabetically.

def get_dense(connectivity, network: Network, keys: list[str], key: str):
    # get largest dense network from a seed key

    # get connectivity matrix with only neighbours from the seed
    keep = [(k in network[key] or k == key) for k in keys]
    connectivity_ = [[c for i, c in enumerate(row) if keep[i]] for j,row in enumerate(connectivity) if keep[j]]
    keys_ = [k for i,k in enumerate(keys) if keep[i]]

    # remove key with fewest connection with the others until we have a fully connected network
    while sum(sum(not v for v in row) for row in connectivity_) > 0:
        most_false_id = -1
        most_false = 0
        for r, row in enumerate(connectivity_):
            if (n_false := sum(not v for v in row)) > most_false:
                most_false = n_false
                most_false_id = r
        if most_false_id == -1:
            break
        connectivity_ = [[v for c, v in enumerate(row) if c != most_false_id] for r, row in enumerate(connectivity_) if r != most_false_id]
        keys_ = [k for i,k in enumerate(keys_) if i != most_false_id]
    return keys_

def find_largest_dense(network: Network) -> list[str]:
    # sort by most connections
    connections = [(key, len(neighbours)) for key, neighbours in network.items()]
    connections = sorted(connections, key=lambda x: x[1], reverse=True)
    # connectivity matrix with keys sorted alphabetically
    keys = sorted(network.keys())
    connectivity = [[(k2 in network[k] or k2 == k) for k2 in keys] for k in keys]
    
    most_connected = 0
    keys_in_most_connected = []
    for key, n in connections:
        # if we have fewer neighbours than the current largest subnetwork, we can stop
        if n < most_connected:
            break
        keys_ = get_dense(connectivity, network, keys, key)
        # update largest subnetwork
        if len(keys_) > most_connected:
            most_connected = len(keys_)
            keys_in_most_connected = keys_

    return keys_in_most_connected