Advent of code 2023 day 25 fast

def day25(s, num_random_edges=100):
  graph = networkx.Graph()
  for line in s.splitlines():
    node, other_nodes = line.split(':')
    for node2 in other_nodes.split():
      graph.add_edge(node, node2)

  # The graph in the puzzle input has a dumbbell connectivity structure.
  # Therefore, a heuristic algorithm is to examine the shortest paths between
  # many random pairs of nodes and find the most common edges.

  rng = np.random.default_rng(0)
  edge_counts = collections.Counter()
  nodes = np.array(list(graph.nodes()))

  for _ in range(num_random_edges):
    node_pair = rng.choice(nodes, size=2, replace=False)
    path = networkx.shortest_path(graph, source=node_pair[0], target=node_pair[1])
    for edge in itertools.pairwise(path):
      edge_counts[tuple(sorted(edge))] += 1

  for (node1, node2), _ in edge_counts.most_common(3):
    graph.remove_edge(node1, node2)
  component1, component2 = networkx.connected_components(graph)
  return len(component1) * len(component2)