aoc::year2024

Module day23

Source
Expand description

§LAN Party

This is the Clique problem. For part one we find triangles (cliques of size 3) for each node by checking if there’s an edge between any distinct pair of neighbouring nodes.

Part two asks to find the maximum clique, for which we could use the Bron–Kerbosch algorithm. However the input has a specific structure that enables a simpler approach of finding the largest maximal clique using a greedy algorithm. Nodes are arranged in clusters of 13 and the maximum clique is size 14. This approach will not necessarily work for any general graph, but will work for the inputs provided.

Functions§

  • parse
    Convert each character pair xy to an index from 0..676 so that we can use much faster array lookup instead of a HashMap.
  • part1
  • part2
  • to_char 🔒
  • to_usize 🔒

Type Aliases§