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_view>
      23              : #include <vector>
      24              : 
      25              : namespace {
      26              : 
      27              : using UndirectedGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
      28              : 
      29            1 : UndirectedGraph parseGraph(std::string_view const input) {
      30            1 :   LinewiseInput lines(input);
      31              : 
      32            1 :   std::vector<std::pair<unsigned, unsigned>> edges;
      33              : 
      34            1 :   absl::flat_hash_map<std::string_view, unsigned> vertices;
      35              : 
      36            1 :   unsigned vertexId = 0;
      37         1214 :   for (std::string_view const line : lines) {
      38         1214 :     static const RE2 pattern = R"((.{3}): (.+))";
      39         1214 :     std::string_view fromVertex;
      40         1214 :     std::string_view toVerticesStr;
      41         1214 :     ASSUME(RE2::FullMatch(line, pattern, &fromVertex, &toVerticesStr));
      42         1214 :     std::vector<std::string_view> toVertices = split(toVerticesStr, ' ');
      43         1214 :     if (vertices.emplace(fromVertex, vertexId).second)
      44          589 :       ++vertexId;
      45         3297 :     for (auto const toVertex : toVertices) {
      46         3297 :       if (vertices.emplace(toVertex, vertexId).second)
      47          886 :         ++vertexId;
      48         3297 :       edges.emplace_back(vertices[fromVertex], vertices[toVertex]);
      49         3297 :     }
      50         1214 :   }
      51              : 
      52            1 :   return {edges.begin(), edges.end(), vertices.size(), edges.size()};
      53            1 : }
      54              : 
      55              : } // namespace
      56              : 
      57            1 : template <> size_t part1<2023, 25>(std::string_view const input) {
      58            1 :   UndirectedGraph g = parseGraph(input);
      59            1 :   auto parities = boost::make_one_bit_color_map(num_vertices(g), get(boost::vertex_index, g));
      60            1 :   auto weights = boost::make_constant_property<UndirectedGraph::edge_descriptor>(1);
      61              : 
      62            1 :   int w = boost::stoer_wagner_min_cut(g, weights, boost::parity_map(parities));
      63              : 
      64            1 :   ASSERT(w == 3);
      65            1 :   size_t clusterASize = std::count_if(vertices(g).first, vertices(g).second,
      66         1475 :                                       [&](auto const &i) { return get(parities, i) != 0; });
      67            1 :   size_t clusterBSize = num_vertices(g) - clusterASize;
      68            1 :   return clusterASize * clusterBSize;
      69            1 : }
      70              : 
      71            1 : template <> size_t part2<2023, 25>(std::string_view const /*input*/) { return 0; }