Day 23: LAN Party

Class {
	#name : 'Day23Solver',
	#superclass : 'AoCSolver',
	#instVars : [ 'computers' ],
	#category : 'AoCDay23',
	#package : 'AoCDay23'
}

Day23Solver >> cliquesOfSize: size [
   | potentialCliques |
   potentialCliques := OrderedCollection new.
   computers keysAndValuesDo: [ :comp :neighbors |
      neighbors combinations: size - 1 atATimeDo: [ :comb |
         potentialCliques add: comb asOrderedCollection , { comp } ] ].
   ^ potentialCliques select: [ :x | self isClique: x ]
]

Day23Solver >> isClique: aCollection [
   aCollection withIndexDo: [ :v :i |
      ((computers at: v) includesAll: (aCollection allButFirst: i)) ifFalse: [ ^ false ] ].
   ^ true
]

Day23Solver >> parseRawData [
   | comps |
   computers := Dictionary new.
   rawData lines do: [ :line |
      comps := line splitOn: '-'.
      (computers at: comps first ifAbsentPut: OrderedCollection new) add: comps second.
      (computers at: comps second ifAbsentPut: OrderedCollection new) add: comps first ]
]

Day23Solver >> solvePart1 [
   ^ ((self cliquesOfSize: 3) count: [ :clique | clique anySatisfy: [ :x | x first = $t ] ]) // 3
]

Day23Solver >> solvePart2 [
   | maxSize cliques |
   maxSize := computers values first size + 1.
   maxSize to: 1 by: -1 do: [ :size |
      cliques := self cliquesOfSize: size.
      cliques ifNotEmpty: [ ^ ',' join: cliques first sorted ] ].
]

/* Advent of Code 2024
 * Day 23: LAN Party
 */

#import "Basic";
#import "File";
#import "Hash_Table";
#import "Sort";
#import "String";

Connection_Table :: Table(string, [..] string);

// Finds all maximal cliques using the Bron-Kerbosch algorithm.
bron_kerbosch :: (
    r: [] string,
    p: [] string,
    x: [] string,
    connections: Connection_Table,
    cliques: *[..][..] string
) {
    if p.count == 0 && x.count == 0 {
        // We've found a maximal clique.
        clique: [..] string;
        array_copy(*clique, r);
        array_add(cliques, clique);
    }

    // p and x are passed as array views, but we need to modify them.
    mutable_p: [..] string;
    array_copy(*mutable_p, p);
    defer array_free(mutable_p);

    mutable_x: [..] string;
    array_copy(*mutable_x, x);
    defer array_free(mutable_x);

    for mutable_p {
        new_r: [..] string;
        new_p: [..] string;
        new_x: [..] string;

        defer array_free(new_r);
        defer array_free(new_p);
        defer array_free(new_x);

        array_copy(*new_r, r);
        array_add(*new_r, it);

        // The connections table is guaranteed to contain all computers.
        individual_connections, _ := table_find(*connections, it);

        for mutable_p {
            if array_find(individual_connections, it) {
                array_add(*new_p, it);
            }
        }

        for mutable_x {
            if array_find(individual_connections, it) {
                array_add(*new_x, it);
            }
        }

        bron_kerbosch(new_r, new_p, new_x, connections, cliques);

        array_add(*mutable_x, it);
        remove it;
    }
}

main :: () {
    input, success := read_entire_file("inputs/day_23.txt");
    assert(success);

    lines := split(input, "\n");
    defer array_free(lines);

    connections: Connection_Table;
    defer {
        for connections {
            array_free(it);
        }

        deinit(*connections);
    }

    for lines {
        if it == "" {
            continue;
        }

        computers := split(it, "-");
        defer array_free(computers);

        for computers {
            individual_connections := table_find_pointer(*connections, it);
            if individual_connections == null {
                individual_connections: [..] string;
                array_add(*individual_connections, computers[xx !it_index]);
                table_add(*connections, it, individual_connections);
            } else {
                array_add(individual_connections, computers[xx !it_index]);
            }
        }
    }

    computers: [..] string;
    defer array_free(computers);

    for connections {
        array_add(*computers, it_index);
    }

    triangles_with_t := 0;
    for computer_a, index_a: computers {
        connections_a, _ := table_find(*connections, computer_a);
        for computer_b: connections_a {
            _, index_b := array_find(computers, computer_b);
            if index_b <= index_a {
                continue;
            }

            connections_b, _ := table_find(*connections, computer_b);
            for computer_c: connections_b {
                _, index_c := array_find(computers, computer_c);
                if index_c <= index_b {
                    continue;
                }

                if array_find(connections_a, computer_c) && (
                    computer_a[0] == #char "t"
                    || computer_b[0] == #char "t"
                    || computer_c[0] == #char "t"
                ) {
                    triangles_with_t += 1;
                }
            }
        }
    }

    print("Part 1: %\n", triangles_with_t);

    cliques: [..][..] string;
    defer {
        for cliques {
            array_free(it);
        }

        array_free(cliques);
    }

    bron_kerbosch(.[], computers, .[], connections, *cliques);

    lan_party: [..] string;
    largest_count := 0;

    for cliques {
        if it.count > largest_count {
            lan_party = it;
            largest_count = it.count;
        }
    }

    print("Part 2: %\n", join(.. quick_sort(lan_party, compare), ","));
}

This uses the petgraph library. I found it somewhat hard to use in the past, but it worked out nicely here.

pub fn parser(input: &'static str) -> PuzzleInput {
    let mut graph = UnGraphMap::new();

    for line in input.lines() {
        let (a, b) = line.split_once("-").unwrap();
        graph.add_edge(a, b, ());
    }

    PuzzleInput { graph }
}

pub fn part1(input: &PuzzleInput) -> String {
    // This is a bit of a mouthful, but petgraph makes this surprisingly easy.
    //
    // 1. Iterate over all nodes that start with "t"
    // 2. Get all neighbors of the node
    // 3. Check all combinations of two neighbors if they are connected -- if so, we have a three-connected set
    // 4. Sort the three-connected set and return it as a vector
    // 5. At this point, we have a vector of vectors for each node that starts with "t",
    //    so we need to flatten it to remove one level of nesting
    // 6. Then we remove duplicates using .unique() and return the length of the result
    input
        .graph
        .nodes()
        .filter(|n| n.starts_with("t"))
        .map(|n| {
            input
                .graph
                .neighbors(n)
                .tuple_combinations()
                .filter(|(a, b)| input.graph.contains_edge(a, b))
                .map(|(a, b)| {
                    let mut triplet = vec![n, a, b];
                    triplet.sort();
                    triplet
                })
                .collect_vec()
        })
        .flatten()
        .unique()
        .count()
        .to_string()
}

pub fn part2(input: &PuzzleInput) -> String {
    let mut visited = HashSet::new();
    let mut best_clique = Vec::new();

    // This is pretty much a brute-force approach that follows directly from the
    // definition of a clique.
    //
    // We start with a single-node clique and try to grow it. To do that, we
    // iterate over all nodes that have not been processed yet and check if they
    // are connected to all nodes in the current clique.
    //
    // If they are connected to everyone in the clique, they are part of the
    // clique by definition, so we add them to the set and continue.
    //
    // Once a node is part of a clique, we add it to the visited set to avoid
    // processing it again -- it can't be part of another, larger clique: either
    // the current clique grows to be the largest possible, or another, larger
    // clique is found which will not contain the node because it is part of
    // the current clique.
    //
    // Not 100% sure if this is just fast because the input is benign, or if it's
    // actually a sound algorithm...
    for start in input.graph.nodes() {
        if visited.contains(start) {
            continue;
        }

        let mut clique = Vec::from([start]);

        'outer: for node in input.graph.neighbors(start) {
            for c in clique.iter() {
                if !input.graph.contains_edge(c, node) {
                    continue 'outer;
                }
            }

            clique.push(node);
            visited.insert(node);
        }

        if clique.len() > best_clique.len() {
            best_clique = clique;
        }
    }

    best_clique.iter().sorted().join(",")
}

day_23    fastest       │ slowest       │ median        │ mean          │ samples │ iters
├─ part1  1.167 ms      │ 1.548 ms      │ 1.225 ms      │ 1.22 ms       │ 100     │ 100
╰─ part2  1.184 ms      │ 1.229 ms      │ 1.201 ms      │ 1.201 ms      │ 100     │ 100