Line data    Source code

       1              : #include "LinewiseInput.h"
       2              : #include "Parsing.h"
       3              : #include "PuzzleImpl.h"
       4              : 
       5              : #include <absl/container/flat_hash_map.h>
       6              : #include <algorithm>
       7              : #include <libassert/assert.hpp>
       8              : #include <re2/re2.h>
       9              : 
      10              : #if defined(__GNUC__) && !defined(__clang__)
      11              : #pragma GCC diagnostic push
      12              : #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
      13              : #endif
      14              : #include <boost/graph/adjacency_list.hpp>
      15              : #include <boost/graph/one_bit_color_map.hpp>
      16              : #include <boost/graph/stoer_wagner_min_cut.hpp>
      17              : #include <boost/property_map/property_map.hpp>
      18              : #if defined(__GNUC__) && !defined(__clang__)
      19              : #pragma GCC diagnostic pop
      20              : #endif
      21              : 
      22              : #include <string>
      23              : #include <string_view>
      24              : #include <vector>
      25              : 
      26              : namespace {
      27              : 
      28              : using UndirectedGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
      29              : 
      30            1 : UndirectedGraph parseGraph(std::string_view const input) {
      31            1 :   LinewiseInput lines(input);
      32              : 
      33            1 :   std::vector<std::pair<unsigned, unsigned>> edges;
      34              : 
      35            1 :   absl::flat_hash_map<std::string_view, unsigned> vertices;
      36              : 
      37            1 :   unsigned vertexId = 0;
      38         1214 :   for (std::string_view const line : lines) {
      39         1214 :     static const RE2 pattern = R"((.{3}): (.+))";
      40         1214 :     std::string_view fromVertex;
      41         1214 :     std::string_view toVerticesStr;
      42         1214 :     ASSUME(RE2::FullMatch(line, pattern, &fromVertex, &toVerticesStr));
      43         1214 :     std::vector<std::string_view> toVertices = split(toVerticesStr, ' ');
      44         1214 :     if (vertices.emplace(fromVertex, vertexId).second)
      45          589 :       ++vertexId;
      46         3297 :     for (auto const toVertex : toVertices) {
      47         3297 :       if (vertices.emplace(toVertex, vertexId).second)
      48          886 :         ++vertexId;
      49         3297 :       edges.emplace_back(vertices[fromVertex], vertices[toVertex]);
      50         3297 :     }
      51         1214 :   }
      52              : 
      53            1 :   return {edges.begin(), edges.end(), vertices.size(), edges.size()};
      54            1 : }
      55              : 
      56              : } // namespace
      57              : 
      58            1 : template <> std::string solvePart1<2023, 25>(std::string_view const input) {
      59            1 :   UndirectedGraph g = parseGraph(input);
      60            1 :   auto parities = boost::make_one_bit_color_map(num_vertices(g), get(boost::vertex_index, g));
      61            1 :   auto weights = boost::make_constant_property<UndirectedGraph::edge_descriptor>(1);
      62              : 
      63            1 :   int w = boost::stoer_wagner_min_cut(g, weights, boost::parity_map(parities));
      64              : 
      65            1 :   ASSERT(w == 3);
      66            1 :   size_t clusterASize = std::count_if(vertices(g).first, vertices(g).second,
      67         1475 :                                       [&](auto const &i) { return get(parities, i) != 0; });
      68            1 :   size_t clusterBSize = num_vertices(g) - clusterASize;
      69            1 :   return std::to_string(clusterASize * clusterBSize);
      70            1 : }
      71              : 
      72            1 : template <> std::string solvePart2<2023, 25>(std::string_view const /*input*/) { return ""; }