Line data Source code
1 : #include "PuzzleImpl.h"
2 :
3 : #include "Grid2d.h"
4 : #include "LinewiseInput.h"
5 :
6 : #include <experimental/mdspan>
7 :
8 : #include <algorithm>
9 : #include <cstddef>
10 : #include <queue>
11 : #include <ranges>
12 : #include <set>
13 : #include <string_view>
14 :
15 : using namespace std::literals;
16 :
17 : namespace {
18 :
19 : using VertexId = std::array<int, 3u>;
20 :
21 : int constexpr numDirections = 4;
22 : std::array<Vec2<int>, numDirections> constexpr dirs{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
23 :
24 80896 : constexpr VertexId turnRight(VertexId const vid) {
25 80896 : auto [x, y, d] = vid;
26 80896 : return {x, y, d == 3 ? 0 : d + 1};
27 80896 : }
28 :
29 80896 : constexpr VertexId turnLeft(VertexId const vid) {
30 80896 : auto [x, y, d] = vid;
31 80896 : return {x, y, d == 0 ? 3 : d - 1};
32 80896 : }
33 :
34 80896 : constexpr VertexId moveForward(VertexId const vid) {
35 80896 : auto [x, y, d] = vid;
36 80896 : return {x + dirs[d].x(), y + dirs[d].y(), d};
37 80896 : }
38 :
39 : struct VertexScore {
40 831216 : constexpr bool operator<(VertexScore const &other) const { return score > other.score; }
41 :
42 : VertexId id;
43 : int score;
44 : };
45 :
46 2 : VertexId startVertex(Grid2d<char> const &map) {
47 2 : auto [sourceX, sourceY] = map.find('S');
48 2 : return {sourceX, sourceY, 1};
49 2 : }
50 :
51 2 : std::array<VertexId, 4u> endVertices(Grid2d<char> const &map) {
52 2 : auto [endX, endY] = map.find('E');
53 2 : return {{{endX, endY, 0}, {endX, endY, 1}, {endX, endY, 2}, {endX, endY, 3}}};
54 2 : }
55 :
56 : } // namespace
57 :
58 1 : template <> size_t part1<2024, 16>(std::string_view const input) {
59 1 : Grid2d<char> const map = LinewiseInput(input).makeCharGrid2d();
60 1 : std::vector<int> distData(static_cast<size_t>(map.xSize() * map.ySize() * numDirections),
61 1 : std::numeric_limits<int>::max());
62 1 : std::experimental::mdspan const dist(distData.data(), map.xSize(), map.ySize(), numDirections);
63 :
64 1 : VertexId const source = startVertex(map);
65 :
66 1 : std::priority_queue<VertexScore> queue;
67 :
68 1 : dist[source] = 0;
69 1 : queue.emplace(source, 0);
70 :
71 40699 : while (!queue.empty()) {
72 40698 : auto [u, p] = queue.top();
73 40698 : queue.pop();
74 40698 : if (p != dist[u])
75 250 : continue;
76 40448 : {
77 40448 : auto v = moveForward(u);
78 40448 : if (map[v[0], v[1]] != '#') {
79 20848 : int alt = dist[u] + 1;
80 20848 : if (alt < dist[v]) {
81 10934 : dist[v] = alt;
82 10934 : queue.emplace(v, alt);
83 10934 : }
84 20848 : }
85 40448 : }
86 80896 : for (auto v : {turnLeft(u), turnRight(u)}) {
87 80896 : int alt = dist[u] + 1000;
88 80896 : if (alt < dist[v]) {
89 29763 : dist[v] = alt;
90 29763 : queue.emplace(v, alt);
91 29763 : }
92 80896 : }
93 40448 : }
94 :
95 1 : return std::ranges::min(endVertices(map) |
96 4 : std::views::transform([&](auto const &v) { return dist[v]; }));
97 1 : }
98 :
99 1 : template <> size_t part2<2024, 16>(std::string_view const input) {
100 1 : Grid2d<char> const map = LinewiseInput(input).makeCharGrid2d();
101 1 : std::vector<int> distData(static_cast<size_t>(map.xSize() * map.ySize() * numDirections),
102 1 : std::numeric_limits<int>::max());
103 1 : std::vector<std::vector<VertexId>> predData(
104 1 : static_cast<size_t>(map.xSize() * map.ySize() * numDirections));
105 1 : std::experimental::mdspan const dist(distData.data(), map.xSize(), map.ySize(), numDirections);
106 1 : std::experimental::mdspan const pred(predData.data(), map.xSize(), map.ySize(), numDirections);
107 :
108 1 : VertexId const source = startVertex(map);
109 :
110 1 : std::priority_queue<VertexScore> queue;
111 :
112 1 : dist[source] = 0;
113 1 : queue.emplace(source, 0);
114 :
115 40699 : while (!queue.empty()) {
116 40698 : auto [u, p] = queue.top();
117 40698 : queue.pop();
118 40698 : if (p != dist[u])
119 250 : continue;
120 40448 : {
121 40448 : auto v = moveForward(u);
122 40448 : if (map[v[0], v[1]] != '#') {
123 20848 : int alt = dist[u] + 1;
124 20848 : if (alt < dist[v]) {
125 10934 : pred[v].assign(1u, u);
126 10934 : dist[v] = alt;
127 10934 : queue.emplace(v, alt);
128 10934 : } else if (alt == dist[v]) {
129 223 : pred[v].push_back(u);
130 223 : }
131 20848 : }
132 40448 : }
133 80896 : for (auto v : {turnLeft(u), turnRight(u)}) {
134 80896 : int alt = dist[u] + 1000;
135 80896 : if (alt < dist[v]) {
136 29763 : pred[v].assign(1u, u);
137 29763 : dist[v] = alt;
138 29763 : queue.emplace(v, alt);
139 51133 : } else if (alt == dist[v]) {
140 9505 : pred[v].push_back(u);
141 9505 : }
142 80896 : }
143 40448 : }
144 :
145 1 : auto ev = endVertices(map);
146 1 : int const minScore =
147 4 : std::ranges::min(ev | std::views::transform([&](auto const &v) { return dist[v]; }));
148 :
149 1 : std::set<Vec2<int>> goodSeats;
150 1 : std::queue<VertexId> q;
151 :
152 4 : for (auto const &e : ev) {
153 4 : if (dist[e] == minScore)
154 1 : q.push(e);
155 4 : }
156 :
157 5836 : while (!q.empty()) {
158 5835 : VertexId cur = q.front();
159 5835 : q.pop();
160 5835 : goodSeats.emplace(cur[0], cur[1]);
161 :
162 5835 : for (VertexId p : pred[cur])
163 5834 : q.push(p);
164 5835 : }
165 :
166 1 : return goodSeats.size();
167 1 : }
|
