Line data Source code
1 : #include "Grid2d.h"
2 : #include "LinewiseInput.h"
3 : #include "PuzzleImpl.h"
4 : #include "Vector.h"
5 :
6 : #include <absl/container/flat_hash_map.h>
7 : #include <absl/container/flat_hash_set.h>
8 : #include <libassert/assert.hpp>
9 :
10 : #include <algorithm>
11 : #include <cstdint>
12 : #include <iterator>
13 : #include <limits>
14 : #include <queue>
15 : #include <stack>
16 : #include <string>
17 : #include <string_view>
18 : #include <utility>
19 : #include <vector>
20 :
21 : namespace {
22 : using Coord = Grid2d<char>::Coord;
23 : enum Dir : uint8_t { N = 0, E = 1, S = 2, W = 3 };
24 : constexpr std::array<Dir, 4u> directions = {N, E, S, W};
25 : constexpr std::array<Dir, 4u> op = {S, W, N, E};
26 : constexpr std::array<Coord, 4u> stencil = {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
27 :
28 : class DAG {
29 : public:
30 : using Vertex = Coord;
31 :
32 1 : DAG(Grid2dSpan<char const> const map) {
33 :
34 1 : std::queue<std::tuple<DAG::Vertex, Dir>> queue;
35 :
36 1 : absl::flat_hash_set<Vertex> visited;
37 :
38 1 : _start = Coord{0, map.ySize() - 1};
39 2 : while (map[_start] != '.' && _start.x() < map.xSize())
40 1 : ++_start.x();
41 1 : DEBUG_ASSERT(_start.x() < map.xSize());
42 1 : visited.insert(_start);
43 1 : queue.emplace(_start, S);
44 :
45 86 : while (!queue.empty()) {
46 85 : auto [vertex, dir] = queue.front();
47 85 : queue.pop();
48 :
49 85 : Coord coord = vertex;
50 85 : int edgeWeight = 0;
51 85 : bool vertexFound = false;
52 85 : Dir newDir = N;
53 9514 : while (!vertexFound) {
54 9429 : coord += stencil[dir];
55 9429 : ++edgeWeight;
56 9429 : DEBUG_ASSERT(map[coord] != '#', coord, dir);
57 :
58 9429 : if (coord.y() == 0) {
59 1 : DEBUG_ASSERT(map[coord] == '.');
60 1 : _end = coord;
61 1 : visited.insert(coord);
62 1 : _edges[vertex].push_back(coord);
63 1 : _edgeWeights.emplace(std::pair{vertex, coord}, edgeWeight);
64 1 : vertexFound = true;
65 1 : continue;
66 1 : }
67 :
68 9428 : int pathCtr = 0;
69 9428 : switch (map[coord]) {
70 0 : case '^':
71 0 : if (dir == S)
72 0 : vertexFound = true;
73 0 : dir = N;
74 0 : break;
75 79 : case '>':
76 79 : if (dir == W)
77 21 : vertexFound = true;
78 79 : dir = E;
79 79 : break;
80 64 : case 'v':
81 64 : if (dir == N)
82 4 : vertexFound = true;
83 64 : dir = S;
84 64 : break;
85 0 : case '<':
86 0 : if (dir == E)
87 0 : vertexFound = true;
88 0 : dir = W;
89 0 : break;
90 9285 : case '.':
91 9285 : pathCtr = 0;
92 37140 : for (auto d : directions) {
93 37140 : if (d == op[dir])
94 9285 : continue;
95 27855 : if (map[coord + stencil[d]] != '#') {
96 9376 : ++pathCtr;
97 9376 : newDir = d;
98 9376 : }
99 27855 : }
100 9285 : DEBUG_ASSERT(pathCtr > 0, coord);
101 9285 : if (pathCtr == 1) {
102 9226 : dir = newDir;
103 9226 : } else {
104 59 : vertexFound = true;
105 59 : DEBUG_ASSERT(std::ranges::find(_edges[vertex], coord) == _edges[vertex].end());
106 59 : _edges[vertex].push_back(coord);
107 59 : _edgeWeights.emplace(std::pair{vertex, coord}, edgeWeight);
108 59 : if (!visited.insert(coord).second)
109 25 : continue;
110 136 : for (auto d : directions) {
111 136 : if (d == op[dir])
112 34 : continue;
113 102 : if (map[coord + stencil[d]] != '#') {
114 84 : queue.emplace(coord, d);
115 84 : }
116 102 : }
117 34 : }
118 9260 : break;
119 9260 : case '#':
120 0 : default:
121 0 : UNREACHABLE(map[coord], coord);
122 9428 : }
123 9428 : }
124 85 : }
125 :
126 1 : absl::flat_hash_map<Vertex, absl::flat_hash_set<Vertex>> inEdges;
127 1 : for (auto const &[v, us] : _edges)
128 35 : for (auto const &u : us)
129 60 : inEdges[u].insert(v);
130 :
131 1 : absl::flat_hash_set<Vertex> vertices;
132 1 : vertices.insert(_start);
133 37 : while (!vertices.empty()) {
134 36 : Vertex v = *vertices.begin();
135 36 : vertices.erase(v);
136 36 : _vertices.push_back(v);
137 60 : for (auto &u : _edges[v]) {
138 60 : inEdges[u].erase(v);
139 60 : if (inEdges[u].empty())
140 35 : vertices.insert(u);
141 60 : }
142 36 : }
143 1 : ASSERT(std::ranges::all_of(inEdges,
144 1 : [](auto const &us) { return us.second.empty(); })); // Check if DAG
145 1 : }
146 :
147 1 : [[nodiscard]] int longestPath() const {
148 1 : absl::flat_hash_map<Vertex, int> distances;
149 1 : absl::flat_hash_map<Vertex, Vertex> pred;
150 1 : for (auto const &v : _vertices)
151 36 : distances[v] = std::numeric_limits<int>::max();
152 1 : distances[_start] = 0;
153 36 : for (auto const &u : _vertices) {
154 36 : auto vIt = _edges.find(u);
155 36 : if (vIt == _edges.end())
156 0 : continue;
157 60 : for (auto const &v : vIt->second) {
158 60 : auto eIt = _edgeWeights.find(std::pair{u, v});
159 60 : DEBUG_ASSERT(eIt != _edgeWeights.end());
160 60 : if (distances[v] > distances[u] - eIt->second) {
161 42 : distances[v] = distances[u] - eIt->second;
162 42 : pred[v] = u;
163 42 : }
164 60 : }
165 36 : }
166 :
167 1 : return -distances[_end];
168 1 : }
169 :
170 : private:
171 : std::vector<Vertex> _vertices;
172 : Vertex _start;
173 : Vertex _end;
174 : absl::flat_hash_map<Vertex, std::vector<Vertex>> _edges;
175 : absl::flat_hash_map<std::pair<Vertex, Vertex>, int> _edgeWeights;
176 : };
177 :
178 : class Graph {
179 : public:
180 1 : Graph(Grid2dSpan<char const> const map) {
181 :
182 1 : std::queue<std::tuple<DAG::Vertex, Dir>> queue;
183 :
184 1 : absl::flat_hash_map<Coord, size_t> foundVertices;
185 :
186 36 : auto addVertex = [&](Coord const &c) {
187 36 : DEBUG_ASSERT(_outEdges.size() == _numVertices);
188 36 : DEBUG_ASSERT(_edgeWeights.size() == _numVertices);
189 36 : foundVertices[c] = _numVertices;
190 36 : _outEdges.emplace_back();
191 36 : _edgeWeights.emplace_back();
192 36 : return _numVertices++;
193 36 : };
194 :
195 85 : auto addEdge = [&](size_t const v1, size_t v2, int const edgeWeight) {
196 85 : DEBUG_ASSERT(v1 < _edgeWeights.size());
197 85 : DEBUG_ASSERT(v2 < _edgeWeights.size());
198 85 : DEBUG_ASSERT(_edgeWeights.size() == _outEdges.size());
199 :
200 85 : auto it = std::ranges::find(_outEdges[v1], v2);
201 85 : if (it == _outEdges[v1].end()) {
202 60 : DEBUG_ASSERT(!std::ranges::contains(_outEdges[v2], v1));
203 60 : _outEdges[v1].push_back(v2);
204 60 : _outEdges[v2].push_back(v1);
205 60 : _edgeWeights[v1].push_back(edgeWeight);
206 60 : _edgeWeights[v2].push_back(edgeWeight);
207 60 : } else {
208 25 : auto idx = std::distance(_outEdges[v1].begin(), it);
209 25 : if (_edgeWeights[v1][idx] >= edgeWeight)
210 25 : return;
211 0 : _edgeWeights[v1][idx] = edgeWeight;
212 0 : it = std::ranges::find(_outEdges[v2], v1);
213 0 : DEBUG_ASSERT(it != _outEdges[v2].end());
214 0 : idx = std::distance(_outEdges[v2].begin(), it);
215 0 : DEBUG_ASSERT(_edgeWeights[v2][idx] < edgeWeight);
216 0 : _edgeWeights[v2][idx] = edgeWeight;
217 0 : }
218 85 : };
219 :
220 1 : Coord start{0, map.ySize() - 1};
221 2 : while (map[start] != '.' && start.x() < map.xSize())
222 1 : ++start.x();
223 1 : DEBUG_ASSERT(start.x() < map.xSize());
224 1 : _start = addVertex(start);
225 1 : queue.emplace(start, S);
226 :
227 86 : while (!queue.empty()) {
228 85 : auto [vertexCoord, dir] = queue.front();
229 85 : size_t vertex = foundVertices[vertexCoord];
230 85 : queue.pop();
231 :
232 85 : Coord coord = vertexCoord;
233 85 : int edgeWeight = 0;
234 85 : bool vertexFound = false;
235 85 : Dir newDir = N;
236 12708 : while (!vertexFound) {
237 12708 : coord += stencil[dir];
238 12708 : ++edgeWeight;
239 12708 : DEBUG_ASSERT(map[coord] != '#', coord, dir);
240 :
241 12708 : if (coord.y() == 0) {
242 1 : DEBUG_ASSERT(map[coord] == '.');
243 1 : _end = addVertex(coord);
244 1 : addEdge(vertex, _end, edgeWeight);
245 1 : break;
246 1 : }
247 :
248 12707 : int pathCtr = 0;
249 12707 : if (map[coord] != '#') {
250 12707 : pathCtr = 0;
251 50828 : for (auto d : directions) {
252 50828 : if (d == op[dir])
253 12707 : continue;
254 38121 : if (map[coord + stencil[d]] != '#') {
255 12843 : ++pathCtr;
256 12843 : newDir = d;
257 12843 : }
258 38121 : }
259 12707 : DEBUG_ASSERT(pathCtr > 0, coord);
260 12707 : if (pathCtr == 1) {
261 12623 : dir = newDir;
262 12623 : } else {
263 84 : auto it = foundVertices.find(coord);
264 84 : bool newVertex = it == foundVertices.end();
265 84 : size_t foundVertex = newVertex ? addVertex(coord) : it->second;
266 84 : addEdge(vertex, foundVertex, edgeWeight);
267 84 : if (newVertex)
268 136 : for (auto d : directions) {
269 136 : if (d == op[dir])
270 34 : continue;
271 102 : if (map[coord + stencil[d]] != '#') {
272 84 : queue.emplace(coord, d);
273 84 : }
274 102 : }
275 84 : break;
276 84 : }
277 12707 : }
278 12707 : }
279 85 : }
280 1 : }
281 :
282 1 : int longestPath() {
283 1 : ASSERT(_numVertices <= 64);
284 1 : int maxWeight = 0;
285 1 : longestPathImpl(_start, 0, 0, maxWeight);
286 1 : return maxWeight;
287 1 : }
288 :
289 : private:
290 : void longestPathImpl(size_t const node, uint64_t const visited, int const weight,
291 102288677 : int &maxWeight) {
292 102288677 : uint64_t const nodeMask = uint64_t(1) << node;
293 :
294 102288677 : if ((visited & nodeMask) != 0u)
295 71708383 : return;
296 :
297 30580294 : if (node == _end) {
298 1262816 : maxWeight = std::max(weight, maxWeight);
299 1262816 : return;
300 1262816 : }
301 :
302 131606154 : for (size_t i = 0; i < _outEdges[node].size(); ++i)
303 102288676 : longestPathImpl(_outEdges[node][i], visited | nodeMask, weight + _edgeWeights[node][i],
304 102288676 : maxWeight);
305 29317478 : }
306 :
307 : size_t _numVertices = 0u;
308 : std::vector<std::vector<size_t>> _outEdges;
309 : std::vector<std::vector<int>> _edgeWeights;
310 : size_t _start;
311 : size_t _end;
312 : };
313 :
314 : } // namespace
315 :
316 1 : template <> std::string solvePart1<2023, 23>(std::string_view const input) {
317 1 : LinewiseInput lines(input);
318 1 : Grid2d<char> map = lines.makeCharGrid2dWithGhostLayers(1, '#');
319 1 : DAG dag(map);
320 1 : return std::to_string(dag.longestPath());
321 1 : }
322 :
323 1 : template <> std::string solvePart2<2023, 23>(std::string_view const input) {
324 1 : LinewiseInput lines(input);
325 1 : Grid2d<char> map = lines.makeCharGrid2dWithGhostLayers(1, '#');
326 :
327 1 : Graph g(map);
328 :
329 1 : return std::to_string(g.longestPath());
330 1 : }
|
