Advent of Code 2024 - Day 23: LAN Party

:: programming, python, puzzle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
 
from advent import parse, words, nx, combinations

G = nx.Graph(parse(23, words))

part1 = lambda: len({ tuple(sorted((v, neighbors[0], neighbors[1])))
                      for v, _ in nx.triangles(G).items() if v[0] == 't'
                      for neighbors in combinations(G[v], 2) if G.has_edge(neighbors[0], neighbors[1]) })

part2 = lambda: ",".join(sorted(nx.max_weight_clique(G, weight=None)[0]))

# ---------------------------------------------------------------------------------------------

assert part1() == 1151
assert part2() == 'ar,cd,hl,iw,jm,ku,qo,rz,vo,xe,xm,xv,ys'

Graph Clique

A clique in a graph is a set of nodes that are fully connected. For example, in the following graph, the set of nodes { A, B, D, E } form a clique.

Here’s the code used to create that image. I had to use custom positioning to get a nice layout.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
 
from advent import nx, plt

G = nx.Graph([ ('A','B'), ('A','C'), ('A','D'),
               ('A','E'), ('B','D'), ('B','E'),
               ('C','F'), ('D','E'), ('E','F') ])

clique_edges = [ ('A','B'), ('A','D'), ('A','E'), ('B','D'), ('B','E'), ('D','E') ]

pos = { 'A' : (-1, -5), 'B' : (0, 10), 'C' : (-1, -10),
        'D' : ( 0,  0), 'E' : (1, -5), 'F':  ( 1, -10) }
plt.figure(figsize=(8, 8))
nx.draw(G, pos, with_labels=True, node_color="lightblue", node_size=5000, font_size=30)
nx.draw_networkx_edges(G, pos, edgelist=clique_edges, edge_color="green", width=4)
plt.show()

Solution

As I mentioned before in this series, I chose Python this year to become more proficient with both the language and the ecosystem, so I simply used the networkx graph library to solve both parts of today’s puzzle.

For part 1 the algorithm is:

  • Iterate over all the nodes in triangles that start with t
  • For each combination of 2 neighbors that are connected to each other…
  • Sort the 3-tuple for uniqueness, and add to a set
  • Return the number of unique 3-tuples

For part 2 the algorithm is:

  • Compute the maximum clique (set of nodes that are connected to every other node in the set)
  • Sort the list of nodes
  • Join with commas

New Python Concepts

  • Graph().has_edge()
  • nx.max_weight_clique()
  • nx.triangles()

Conclusion

Python delivers with a very functional graph library and comprehensions!