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