5 votes

Day 23: LAN Party

Automatically posted

Today's problem description: https://adventofcode.com/2024/day/23

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

2 comments

  1. scarecrw
    (edited )
    Link
    I'm sure at some point I knew some proper clique finding algorithm, but I couldn't remember anything. IIRC a generalized solution is NP-hard, but I took a look at the graph and noticed all the...

    I'm sure at some point I knew some proper clique finding algorithm, but I couldn't remember anything. IIRC a generalized solution is NP-hard, but I took a look at the graph and noticed all the nodes have the same degree, and just counted down from this upper bound on the clique size.

    Similar to yesterday, I think one of the most useful skills I've most developed for these types of problems is being able to quickly eyeball what approaches are going to fit the input size. I can definitely see myself in the past getting lost in the weeds on an approach that was never going to be efficient enough.

    I didn't do much refactoring, so code's pretty ugly today, with some goofy deep nesting.

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

Day23Solver >> isClique: aCollection [
   aCollection withIndexDo: [ :v :i |
      ((aCollection allButFirst: i) allSatisfy: [ :n | (computers at: n) includes: v ]) 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 [
   | count seen testing |
   count := 0.
   seen := Set new.
   computers keysAndValuesDo: [ :comp :neighbors |
      (seen includes: comp) ifFalse: [
         seen add: comp.
         neighbors combinations: 2 atATimeDo: [ :comb |
            testing := comb , { comp }.
            (self isClique: testing) & (testing anySatisfy: [ :x | x first = $t ]) ifTrue: [
               count := count + 1 ] ] ] ].
   ^ count // 3
]

Day23Solver >> solvePart2 [
   | seen testing maxSize |
   maxSize := computers values first size + 1.
   maxSize to: 1 by: -1 do: [ :size |
      seen := Set new.
      computers keysAndValuesDo: [ :comp :neighbors |
         (seen includes: comp) ifFalse: [
            seen add: comp.
            neighbors combinations: size - 1 atATimeDo: [ :comb |
               testing := comb asOrderedCollection , { comp }.
               (self isClique: testing) ifTrue: [
                  ^ ',' join: testing sorted ] ] ] ] ].
   ^ nil
]
    2 votes
  2. lily
    Link
    I do not know graph theory especially well, and of course Jai has no available libraries to do it for me, so I had to implement everything myself. Part 1 was easy enough, at least, though my...

    I do not know graph theory especially well, and of course Jai has no available libraries to do it for me, so I had to implement everything myself. Part 1 was easy enough, at least, though my original method for finding all 3-length cliques was pretty slow, and I had to go back afterwards to speed it up. I cannot claim to understand everything that's going on in part 2 all that well - I just searched online for algorithms and picked what seemed to be the most common one. Thankfully, implementing it wasn't too bad. The performance of part 2 could definitely stand to be improved a little, but I'm not sure how I would go about doing that, so I'll just leave it as-is.

    Solution (Jai) 
    /* 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), ","));
}