Line data Source code
1 : #include "Grid2d.h"
2 : #include "Intcode.h"
3 : #include "PuzzleImpl.h"
4 :
5 : #include <libassert/assert.hpp>
6 :
7 : #include <algorithm>
8 : #include <chrono>
9 : #include <iostream>
10 : #include <limits>
11 : #include <queue>
12 : #include <stack>
13 : #include <thread>
14 :
15 : namespace {
16 : using Coord = Grid2d<char>::Coord;
17 :
18 : enum Dir : uint8_t { N = 0, E = 1, S = 2, W = 3 };
19 : constexpr std::array<Coord, 4u> stencil = {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
20 : constexpr std::array<Dir, 4u> leftTurn = {W, N, E, S};
21 : constexpr std::array<Dir, 4u> rightTurn = {E, S, W, N};
22 : constexpr std::array<Dir, 4u> opposite = {S, W, N, E};
23 : constexpr std::array<int64_t, 4u> command = {1, 4, 2, 3};
24 : constexpr std::array<char, 3u> mapSymbol = {'#', '.', 'X'};
25 :
26 2 : std::tuple<Grid2d<char>, Coord, Coord> exploreMap(std::string_view const input) {
27 2 : Computer c(input);
28 2 : SparseGrid2d<char> map(' ');
29 2 : std::stack<Dir> back;
30 2 : Dir d = E;
31 2 : Coord pos{0, 0};
32 2 : map.set(pos, '.');
33 2 : int64_t response = 0;
34 2 : std::optional<Coord> oxygenSystemPos;
35 4910 : c.registerOutput([&](int64_t v) { response = v; });
36 :
37 : // constexpr int FPS = 60;
38 : // constexpr std::chrono::duration<double> frameTime{1.0 / FPS};
39 4912 : while (!oxygenSystemPos || pos != Coord{0, 0}) {
40 : // auto const start = std::chrono::steady_clock::now();
41 4910 : Dir newDir = d;
42 4910 : Coord newPos = pos;
43 :
44 4910 : newDir = rightTurn[newDir];
45 4910 : bool backtrack = true;
46 13192 : for (int i = 0; i < 4; ++i) {
47 11596 : if (map[pos + stencil[newDir]] == ' ') {
48 3314 : backtrack = false;
49 3314 : break;
50 3314 : }
51 8282 : newDir = leftTurn[newDir];
52 8282 : }
53 4910 : if (backtrack)
54 1596 : newDir = back.top();
55 :
56 4910 : newPos = pos + stencil[newDir];
57 4910 : c.queueInput(command[newDir]);
58 :
59 4910 : c.run();
60 :
61 4910 : if (backtrack) {
62 1596 : DEBUG_ASSERT(response == 1);
63 1596 : d = newDir;
64 1596 : pos = newPos;
65 1596 : back.pop();
66 3314 : } else {
67 3314 : switch (response) {
68 2 : case 2:
69 2 : oxygenSystemPos = newPos;
70 2 : [[fallthrough]];
71 1596 : case 1:
72 1596 : d = newDir;
73 1596 : pos = newPos;
74 1596 : back.push(opposite[d]);
75 1596 : [[fallthrough]];
76 3314 : case 0:
77 3314 : map.set(newPos, mapSymbol[response]);
78 3314 : break;
79 0 : default:
80 0 : UNREACHABLE(response);
81 3314 : }
82 3314 : }
83 :
84 : // char old = map[pos];
85 : // map.set(pos, 'D');
86 : // std::cout << "\n" << map << "\n\n";
87 : // map.set(pos, old);
88 : // std::this_thread::sleep_until(start + frameTime);
89 4910 : }
90 2 : ASSERT(oxygenSystemPos);
91 :
92 2 : auto [grid, offset] = map.toGrid2d();
93 :
94 2 : return {grid, -offset, oxygenSystemPos.value_or(Coord{0, 0}) - offset};
95 2 : }
96 :
97 1 : int64_t aStar(Grid2d<char> const &map, Coord start, Coord goal) {
98 1 : Grid2d<int64_t> gScore(map.xSize(), map.ySize(), std::numeric_limits<int64_t>::max());
99 1 : gScore[start] = 0;
100 1 : using PrioCoord = std::tuple<int64_t, Coord>;
101 1098 : auto comp = [&](PrioCoord const &lhs, PrioCoord const &rhs) {
102 1098 : return std::get<0>(lhs) > std::get<0>(rhs);
103 1098 : };
104 1 : std::priority_queue<PrioCoord, std::vector<PrioCoord>, decltype(comp)> openSet(comp);
105 523 : auto heuristic = [](Coord a, Coord b) {
106 523 : return std::abs(a.x() - b.x()) + std::abs(a.y() - b.y());
107 523 : };
108 1 : openSet.emplace(heuristic(start, goal), start);
109 :
110 518 : while (!openSet.empty()) {
111 518 : auto const [oldScore, cur] = openSet.top();
112 518 : openSet.pop();
113 :
114 518 : if (cur == goal)
115 1 : return gScore[cur];
116 :
117 2068 : for (auto const &s : stencil) {
118 2068 : Coord const neighbor = cur + s;
119 2068 : if (map[neighbor] == '#')
120 1030 : continue;
121 1038 : int64_t tentiativeGScore = gScore[cur] + 1;
122 1038 : if (tentiativeGScore < gScore[neighbor]) {
123 522 : gScore[neighbor] = tentiativeGScore;
124 522 : openSet.emplace(tentiativeGScore + heuristic(neighbor, goal), neighbor);
125 522 : }
126 1038 : }
127 517 : }
128 :
129 1 : UNREACHABLE();
130 0 : }
131 :
132 1 : Grid2d<unsigned> dijkstra(Grid2d<char> const &map, Coord start) {
133 1 : Grid2d<unsigned> dist(map.xSize(), map.ySize(), std::numeric_limits<unsigned>::max());
134 1 : Grid2d<uint8_t> visited(map.xSize(), map.ySize(), 0);
135 1 : dist[start] = 0;
136 1 : std::queue<Coord> next;
137 1 : next.push(start);
138 800 : while (!next.empty()) {
139 799 : Coord const cur = next.front();
140 799 : visited[cur] = 1;
141 799 : next.pop();
142 3196 : for (auto const &s : stencil) {
143 3196 : Coord const neighbor = cur + s;
144 3196 : if (visited[neighbor] || map[neighbor] == '#')
145 2398 : continue;
146 798 : dist[neighbor] = std::min(dist[neighbor], dist[cur] + 1u);
147 798 : next.push(neighbor);
148 798 : }
149 799 : }
150 1 : return dist;
151 1 : }
152 :
153 : } // namespace
154 :
155 1 : template <> size_t part1<2019, 15>(std::string_view const input) {
156 1 : auto [map, start, goal] = exploreMap(input);
157 1 : DEBUG_ASSERT(map[start] == '.', start);
158 1 : DEBUG_ASSERT(map[goal] == 'X', goal);
159 :
160 1 : return aStar(map, start, goal);
161 1 : }
162 :
163 1 : template <> size_t part2<2019, 15>(std::string_view const input) {
164 1 : auto [map, start, goal] = exploreMap(input);
165 1 : Grid2d<unsigned> dist = dijkstra(map, goal);
166 1 : unsigned maxDist = 0u;
167 42 : for (int y = 0; y < dist.ySize(); ++y)
168 1722 : for (int x = 0; x < dist.xSize(); ++x)
169 1681 : if (map[x, y] == '.')
170 798 : maxDist = std::max(maxDist, dist[x, y]);
171 1 : return maxDist;
172 1 : }
|
