Line data Source code
1 : #include "PuzzleImpl.h"
2 :
3 : #include "Grid2d.h"
4 : #include "LinewiseInput.h"
5 : #include "Parsing.h"
6 : #include "Views.h"
7 :
8 : #include <format>
9 : #include <queue>
10 : #include <ranges>
11 : #include <string_view>
12 : #include <vector>
13 :
14 : using namespace std::literals;
15 :
16 : namespace {
17 : int constexpr mapSize = 71;
18 : int constexpr numBytes = 1024;
19 :
20 : using VertexId = Vec2<int>;
21 : int constexpr numDirections = 4;
22 : std::array<Vec2<int>, numDirections> constexpr dirs{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
23 :
24 : struct VertexScore {
25 48816 : constexpr bool operator<(VertexScore const &other) const { return score > other.score; }
26 :
27 : VertexId id;
28 : int64_t score;
29 : };
30 :
31 : VertexId constexpr InvalidVertexId{-1, -1};
32 :
33 1 : Grid2d<char> parseMap(std::string_view const input) {
34 1 : Grid2d<char> map(mapSize, mapSize, '#', 1);
35 1 : map.fill('.');
36 1 : LinewiseInput linewise(input);
37 1024 : for (auto l : linewise | views::take(numBytes)) {
38 1024 : auto v = parseIntegerRange<int>(l);
39 1024 : map[v[0], v[1]] = '#';
40 1024 : }
41 :
42 1 : return map;
43 1 : }
44 :
45 1 : auto parseMap2(std::string_view const input) {
46 1 : Grid2d<char> map(mapSize, mapSize, '#', 1);
47 1 : map.fill('.');
48 1 : LinewiseInput linewise(input);
49 1024 : for (auto l : linewise | views::take(numBytes)) {
50 1024 : auto v = parseIntegerRange<int>(l);
51 1024 : map[v[0], v[1]] = '#';
52 1024 : }
53 :
54 1 : std::vector<Vec2<int>> remainingBytes;
55 2426 : for (auto l : linewise | views::drop(numBytes)) {
56 2426 : auto v = parseIntegerRange<int>(l);
57 2426 : remainingBytes.emplace_back(v[0], v[1]);
58 2426 : }
59 :
60 1 : return std::make_tuple(std::move(map), std::move(remainingBytes));
61 1 : }
62 :
63 : } // namespace
64 :
65 1 : template <> std::string solvePart1<2024, 18>(std::string_view const input) {
66 1 : Grid2d<char> const map = parseMap(input);
67 :
68 1 : VertexId const start{0, 0};
69 1 : VertexId const goal{mapSize - 1, mapSize - 1};
70 :
71 1 : Grid2d<VertexId> pred(map.xSize(), map.ySize(), InvalidVertexId);
72 1 : Grid2d<int64_t> gScore(map.xSize(), map.ySize(), std::numeric_limits<int64_t>::max());
73 1 : Grid2d<int64_t> fScore(map.xSize(), map.ySize(), std::numeric_limits<int64_t>::max());
74 1 : std::priority_queue<VertexScore> queue;
75 1 : std::vector<VertexId> shortestPath;
76 :
77 3960 : auto h = [&](VertexId const &v) {
78 3960 : return std::abs(v.x() - goal.x()) + std::abs(v.y() - goal.y());
79 3960 : };
80 :
81 1 : auto reconstructPath = [&](VertexId v) {
82 1 : shortestPath.clear();
83 277 : while (v != start) {
84 276 : shortestPath.push_back(v);
85 276 : ASSUME(pred[v] != InvalidVertexId);
86 276 : v = pred[v];
87 276 : }
88 1 : };
89 :
90 1 : gScore[start] = 0;
91 1 : fScore[start] = h(start);
92 1 : queue.emplace(start, fScore[start]);
93 :
94 3944 : while (!queue.empty()) {
95 3944 : auto [cur, oldFscore] = queue.top();
96 3944 : queue.pop();
97 3944 : if (oldFscore != fScore[cur])
98 298 : continue;
99 :
100 3646 : if (cur == goal) {
101 1 : reconstructPath(cur);
102 1 : break;
103 1 : }
104 :
105 14580 : for (auto d : dirs) {
106 14580 : VertexId neighbor = cur + d;
107 14580 : if (map[neighbor] == '#')
108 2413 : continue;
109 12167 : int64_t tentiative_gScore = gScore[cur] + 1;
110 12167 : if (tentiative_gScore < gScore[neighbor]) {
111 3959 : pred[neighbor] = cur;
112 3959 : gScore[neighbor] = tentiative_gScore;
113 3959 : fScore[neighbor] = tentiative_gScore + h(neighbor);
114 3959 : queue.emplace(neighbor, fScore[neighbor]);
115 3959 : }
116 12167 : }
117 3645 : }
118 :
119 1 : return std::to_string(shortestPath.size());
120 1 : }
121 :
122 1 : template <> std::string solvePart2<2024, 18>(std::string_view const input) {
123 1 : auto [map, remainingBytes] = parseMap2(input);
124 :
125 1 : VertexId const start{0, 0};
126 1 : VertexId const goal{mapSize - 1, mapSize - 1};
127 :
128 1 : Grid2d<VertexId> pred(map.xSize(), map.ySize(), InvalidVertexId);
129 1 : Grid2d<int64_t> gScore(map.xSize(), map.ySize(), std::numeric_limits<int64_t>::max());
130 1 : Grid2d<int64_t> fScore(map.xSize(), map.ySize(), std::numeric_limits<int64_t>::max());
131 1 : std::priority_queue<VertexScore> queue;
132 1 : std::vector<VertexId> shortestPath;
133 :
134 6659 : auto h = [&](VertexId const &v) {
135 6659 : return std::abs(v.x() - goal.x()) + std::abs(v.y() - goal.y());
136 6659 : };
137 :
138 7 : auto reconstructPath = [&](VertexId v) {
139 7 : shortestPath.clear();
140 3691 : while (v != start) {
141 3684 : shortestPath.push_back(v);
142 3684 : ASSUME(pred[v] != InvalidVertexId);
143 3684 : v = pred[v];
144 3684 : }
145 7 : };
146 :
147 1 : auto left = remainingBytes.begin();
148 1 : auto right = remainingBytes.end();
149 12 : while (left != right) {
150 11 : auto it = std::next(left, std::distance(left, right) / 2);
151 :
152 11 : Grid2d<char> updatedMap = map;
153 20727 : for (auto it2 = remainingBytes.begin(); it2 <= it; ++it2)
154 20716 : updatedMap[*it2] = '#';
155 :
156 11 : pred.fill(InvalidVertexId);
157 11 : gScore.fill(std::numeric_limits<int64_t>::max());
158 11 : fScore.fill(std::numeric_limits<int64_t>::max());
159 11 : shortestPath.clear();
160 :
161 11 : gScore[start] = 0;
162 11 : fScore[start] = h(start);
163 11 : queue.emplace(start, fScore[start]);
164 :
165 6663 : while (!queue.empty()) {
166 6659 : auto [cur, oldFscore] = queue.top();
167 6659 : queue.pop();
168 6659 : if (oldFscore != fScore[cur])
169 67 : continue;
170 :
171 6592 : if (cur == goal) {
172 7 : reconstructPath(cur);
173 7 : break;
174 7 : }
175 :
176 26340 : for (auto d : dirs) {
177 26340 : VertexId neighbor = cur + d;
178 26340 : if (updatedMap[neighbor] == '#')
179 12763 : continue;
180 13577 : int64_t tentiative_gScore = gScore[cur] + 1;
181 13577 : if (tentiative_gScore < gScore[neighbor]) {
182 6648 : pred[neighbor] = cur;
183 6648 : gScore[neighbor] = tentiative_gScore;
184 6648 : fScore[neighbor] = tentiative_gScore + h(neighbor);
185 6648 : queue.emplace(neighbor, fScore[neighbor]);
186 6648 : }
187 13577 : }
188 6585 : }
189 11 : if (shortestPath.empty())
190 4 : right = it;
191 7 : else
192 7 : left = std::next(it);
193 11 : }
194 :
195 1 : return std::format("{},{}", left->x(), left->y());
196 1 : }
|
