Day 25: Snowverload

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • hades@lemm.ee
    link
    fedilink
    arrow-up
    1
    ·
    10 months ago

    Python

    import networkx as nx
    
    from .solver import Solver
    
    
    class Day25(Solver):
    
      def __init__(self):
        super().__init__(25)
    
      def presolve(self, input: str):
        self.graph = nx.Graph()
        for line in input.splitlines():
          from_, to_line = line.split(': ')
          for to in to_line.split(' '):
            self.graph.add_edge(from_, to)
    
      def solve_first_star(self) -> int | str:
        cut_value, partition = nx.algorithms.stoer_wagner(self.graph)
        return len(partition[0]) * len(partition[1])