Advent of Code 2024 Day 23

Поділитися
Вставка
  • Опубліковано 23 гру 2024

КОМЕНТАРІ •

  • @Bundas102
    @Bundas102 День тому +1

    For part2 I also checked the degrees of nodes but then I concluded, that I'm fine with brute forcing 2^13 subsets for each node's neighborhood. Then I just intersected all neighbors of those nodes in the subset trying to find the biggest such result. It runs in ~18s, so I'm fine with that.

  • @ErrorThreeTwoThree
    @ErrorThreeTwoThree День тому +4

    What keyboard are you using? Sounds great!

  • @jfb-
    @jfb- 22 години тому

    for part 2 i checked each n-element subset of each node's adjacency list for each n >= the max clique found so far. runs in under a second.

  • @IulianYT
    @IulianYT 23 години тому

    For part 1 I built all the "triangles", and later filtered the ones where at least one started with 't'.
    So outer loop - all nodes, inner loop - all nodes connected to first one, compute intersection of neighbors, order alphabetically and add to a set. Fast enough.
    For part 2 - I didn't even knew about "clique", knew about networkx, but this year didn't use libraries (except re, of course).
    But, did a dumb bruteforce on top of part 1.
    So, part 1 gives all the triangles. Then, for each node, check which triangles it is connected to, and build a new set of "squares"
    and so on, in a loop, build all "cliques" with size N+1 until only 1 remained, and that was the answer.
    Not very efficient, but again - if it works - it is not dumb.

  • @NStripleseven
    @NStripleseven 17 годин тому

    Not a fan of the graph theory ones, tbh. It always just boils down to “do you remember that one specific algorithm?”

  • @frozenkale9675
    @frozenkale9675 День тому +1

    Lovely maximal clique problem

  • @rastislavsvoboda4363
    @rastislavsvoboda4363 День тому +1

    for a in E.keys():
    for b in E[a]:
    for c in E[b]:
    if a < b < c and c in E[a] and "t" in [a[0], b[0], c[0]]:
    res += 1

  • @Tresorthas
    @Tresorthas 19 годин тому +1

    Weird problem for day 23. Literally 6 lines of code for both parts with networkx.
    import networkx as nx
    G = nx.Graph()
    for line in open('input.txt').read().strip().split('
    '):
    G.add_edge(*line.split('-'))
    print(sum(1 for c in nx.enumerate_all_cliques(G) if len(c) == 3 and any(n.startswith('t') for n in c)))
    print(','.join(sorted(max(nx.enumerate_all_cliques(G), key=len))))

    • @NStripleseven
      @NStripleseven 17 годин тому

      Having a graph theory library definitely does help when your problem is exclusively graph theory.

    • @JamesSorenson
      @JamesSorenson 12 годин тому +1

      You can shave off a few lines with:
      G = nx.parse_edgelist(open('input.txt'), delimiter='-', create_using=nx.Graph(), nodetype=str)

  • @rastislavsvoboda4363
    @rastislavsvoboda4363 День тому

    I've manually expanded pairs...
    def solve2(text):
    E = defaultdict(set)
    P = []
    for line in text.splitlines():
    a, b = line.strip().split("-")
    E[a].add(b)
    E[b].add(a)
    P.append({a, b})
    groups = P
    seen = set()
    while True:
    new_groups = []
    for set_members in groups:
    possible_candidates = set.intersection(*(E[x] for x in set_members))
    for candidate in possible_candidates:
    new_grp = set_members | {candidate}
    key = tuple(sorted(new_grp))
    if key not in seen:
    seen.add(key)
    new_groups.append(new_grp)
    if not new_groups:
    break
    groups = new_groups
    assert len(groups) == 1
    res = ",".join(sorted(groups[0]))
    return res