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