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