Line data    Source code

       1              : #include "PuzzleImpl.h"
       2              : 
       3              : #include "Grid2d.h"
       4              : #include "Views.h"
       5              : 
       6              : #include <boost/dynamic_bitset.hpp>
       7              : #include <re2/re2.h>
       8              : 
       9              : #include <algorithm>
      10              : #include <string_view>
      11              : #include <vector>
      12              : 
      13              : namespace {
      14              : 
      15              : using Vertex = uint16_t;
      16              : 
      17           13 : [[maybe_unused]] std::string toString(Vertex v) {
      18           13 :   std::string s = "  "s;
      19           13 :   s[0] = static_cast<char>('a' + (v % 26));
      20           13 :   s[1] = static_cast<char>('a' + (v / 26));
      21           13 :   return s;
      22           13 : }
      23              : 
      24        13524 : Vertex fromString(std::string_view const s) { return (s[0] - 'a') + ((s[1] - 'a') * 26); }
      25              : 
      26         6760 : std::pair<Vertex, Vertex> parseEdge(std::string_view const s) {
      27         6760 :   static RE2 const pattern = R"(([a-z]{2})-([a-z]{2}))";
      28         6760 :   std::string_view v0, v1;
      29         6760 :   RE2::FullMatch(s, pattern, &v0, &v1);
      30         6760 :   return {fromString(v0), fromString(v1)};
      31         6760 : }
      32              : 
      33            2 : auto parse(std::string_view const input) {
      34            2 :   std::vector<Vertex> vertices;
      35            2 :   Grid2d<uint8_t> adjacency(fromString("zz") + 1, fromString("zz") + 1, 0u);
      36              : 
      37         6760 :   for (std::string_view const s : input | views::splitLines) {
      38         6760 :     auto [v0, v1] = parseEdge(s);
      39         6760 :     vertices.push_back(v0);
      40         6760 :     vertices.push_back(v1);
      41         6760 :     adjacency[v0, v1] = 1u;
      42         6760 :     adjacency[v1, v0] = 1u;
      43         6760 :   }
      44            2 :   std::ranges::sort(vertices);
      45            2 :   vertices.erase(std::ranges::unique(vertices).begin(), vertices.end());
      46              : 
      47            2 :   return std::make_tuple(std::move(vertices), std::move(adjacency));
      48            2 : }
      49              : 
      50              : class BronKerbosch {
      51              : private:
      52              :   using VertexSet = boost::dynamic_bitset<>;
      53              : 
      54              : public:
      55              :   BronKerbosch(std::vector<Vertex> const &vertices, Grid2d<uint8_t> const &adjacency)
      56            1 :       : _vertices(vertices), _adjMap(_vertices.size(), VertexSet(_vertices.size())) {
      57          521 :     for (unsigned i = 0; i < _vertices.size(); ++i)
      58       135460 :       for (unsigned j = i + 1; j < _vertices.size(); ++j)
      59       134940 :         if (adjacency[_vertices[i], _vertices[j]]) {
      60         3380 :           _adjMap[i][j] = true;
      61         3380 :           _adjMap[j][i] = true;
      62         3380 :         }
      63            1 :   }
      64              : 
      65            1 :   std::vector<Vertex> operator()() const {
      66              : 
      67            1 :     VertexSet allVertices(_vertices.size());
      68            1 :     allVertices.set();
      69            1 :     VertexSet maximumClique;
      70            1 :     run(VertexSet(_vertices.size()), allVertices, VertexSet(_vertices.size()), maximumClique);
      71              : 
      72            1 :     std::vector<Vertex> resultVertices;
      73            1 :     resultVertices.reserve(maximumClique.count());
      74           14 :     for (size_t i = maximumClique.find_first(); i < maximumClique.size();
      75           13 :          i = maximumClique.find_next(i))
      76           13 :       resultVertices.push_back(_vertices[i]);
      77            1 :     return resultVertices;
      78            1 :   }
      79              : 
      80              : private:
      81         1298 :   void run(VertexSet const &r, VertexSet p, VertexSet x, VertexSet &maximumClique) const {
      82         1298 :     size_t const pCount = p.count();
      83         1298 :     size_t const rCount = r.count();
      84         1298 :     size_t const maximumCliqueCount = maximumClique.count();
      85         1298 :     if (rCount + pCount <= maximumCliqueCount)
      86         1218 :       return;
      87           80 :     if (pCount == 0u && x.none()) {
      88            2 :       if (rCount > maximumCliqueCount)
      89            2 :         maximumClique = r;
      90            2 :       return;
      91            2 :     }
      92         1375 :     for (size_t i = p.find_first(); i < p.size(); i = p.find_next(i)) {
      93         1297 :       VertexSet rNew = r;
      94         1297 :       rNew.set(i);
      95         1297 :       run(rNew, p & _adjMap[i], x & _adjMap[i], maximumClique);
      96         1297 :       p.reset(i);
      97         1297 :       x.set(i);
      98         1297 :     }
      99           78 :   }
     100              : 
     101              :   std::vector<Vertex> _vertices;
     102              :   std::vector<VertexSet> _adjMap;
     103              : };
     104              : 
     105              : } // namespace
     106              : 
     107            1 : template <> std::string solvePart1<2024, 23>(std::string_view const input) {
     108            1 :   auto [vertices, adjacency] = parse(input);
     109              : 
     110          520 :   auto notStartingWithT = std::ranges::partition(vertices, [](Vertex const v) {
     111          520 :     constexpr uint16_t t = 't' - 'a';
     112          520 :     return v % 26 == t;
     113          520 :   });
     114              : 
     115            1 :   uint64_t ctr = 0;
     116           23 :   for (auto it0 = vertices.begin(); it0 != notStartingWithT.begin(); ++it0)
     117        11209 :     for (auto it1 = std::next(it0); it1 != vertices.end(); ++it1)
     118        11187 :       if (adjacency[*it0, *it1])
     119        71767 :         for (auto it2 = std::next(it1); it2 != vertices.end(); ++it2)
     120        71489 :           if (adjacency[*it0, *it2] && adjacency[*it1, *it2])
     121         1327 :             ++ctr;
     122              : 
     123            1 :   return std::to_string(ctr);
     124            1 : }
     125              : 
     126            1 : template <> std::string solvePart2<2024, 23>(std::string_view const input) {
     127            1 :   auto const [vertices, adjacency] = parse(input);
     128              : 
     129            1 :   BronKerbosch bk(vertices, adjacency);
     130              : 
     131            1 :   std::vector<Vertex> maxClique = bk();
     132              : 
     133           13 :   auto maxCliqueStr = maxClique | views::transform([](Vertex const v) { return toString(v); }) |
     134            1 :                       std::ranges::to<std::vector<std::string>>();
     135            1 :   std::ranges::sort(maxCliqueStr);
     136              : 
     137            1 :   return maxCliqueStr | views::join_with(',') | std::ranges::to<std::string>();
     138            1 : }