Line data Source code
1 : #include "Grid2d.h"
2 : #include "LinewiseInput.h"
3 : #include "PuzzleImpl.h"
4 :
5 : #include <libassert/assert.hpp>
6 :
7 : #include <cstdint>
8 : #include <iostream>
9 : #include <string>
10 : #include <string_view>
11 : #include <tuple>
12 :
13 : namespace {
14 :
15 : using Grid = Grid2d<char>;
16 : using IndexType = Grid2d<char>::IndexType;
17 : using Coord = Grid::Coord;
18 :
19 : enum Dir : uint8_t { N, S, E, W };
20 :
21 4 : constexpr Coord operator+(Coord const &c, Dir d) {
22 4 : switch (d) {
23 3 : case N:
24 3 : return c + Coord{0, 1};
25 1 : case S:
26 1 : return c + Coord{0, -1};
27 0 : case E:
28 0 : return c + Coord{1, 0};
29 0 : case W:
30 0 : return c + Coord{-1, 0};
31 0 : default:
32 0 : UNREACHABLE();
33 4 : }
34 4 : }
35 :
36 27636 : constexpr Coord &operator+=(Coord &c, Dir const d) {
37 27636 : switch (d) {
38 6922 : case N:
39 6922 : c[1] += 1;
40 6922 : return c;
41 6922 : case S:
42 6922 : c[1] -= 1;
43 6922 : return c;
44 6896 : case E:
45 6896 : c[0] += 1;
46 6896 : return c;
47 6896 : case W:
48 6896 : c[0] -= 1;
49 6896 : return c;
50 0 : default:
51 0 : UNREACHABLE();
52 27636 : }
53 27636 : }
54 :
55 27634 : Dir findNextDir(char const curNode, Dir const d) {
56 27634 : switch (d) {
57 6920 : case N:
58 6920 : switch (curNode) {
59 2584 : case '|':
60 2584 : return N;
61 2156 : case 'F':
62 2156 : return E;
63 2180 : case '7':
64 2180 : return W;
65 0 : default:
66 0 : UNREACHABLE(curNode, d);
67 6920 : }
68 0 : break;
69 6922 : case S:
70 6922 : switch (curNode) {
71 2630 : case '|':
72 2630 : return S;
73 2130 : case 'J':
74 2130 : return W;
75 2162 : case 'L':
76 2162 : return E;
77 0 : default:
78 0 : UNREACHABLE(curNode, d);
79 6922 : }
80 0 : break;
81 6896 : case E:
82 6896 : switch (curNode) {
83 2578 : case '-':
84 2578 : return E;
85 2160 : case '7':
86 2160 : return S;
87 2158 : case 'J':
88 2158 : return N;
89 0 : default:
90 0 : UNREACHABLE(curNode, d);
91 6896 : }
92 0 : break;
93 6896 : case W:
94 6896 : switch (curNode) {
95 2586 : case '-':
96 2586 : return W;
97 2132 : case 'F':
98 2132 : return S;
99 2178 : case 'L':
100 2178 : return N;
101 0 : default:
102 0 : UNREACHABLE(curNode, d);
103 6896 : }
104 27634 : }
105 :
106 0 : return N;
107 27634 : }
108 :
109 3 : bool hasNorthConnection(Grid const &grid, Coord const &c) {
110 3 : char const neighborPiece = grid[c + N];
111 3 : return neighborPiece == '|' || neighborPiece == 'F' || neighborPiece == '7';
112 3 : }
113 :
114 1 : bool hasSouthConnection(Grid const &grid, Coord const &c) {
115 1 : char const neighborPiece = grid[c + S];
116 1 : return neighborPiece == '|' || neighborPiece == 'L' || neighborPiece == 'J';
117 1 : }
118 :
119 0 : bool hasEastConnection(Grid const &grid, Coord const &c) {
120 0 : char const neighborPiece = grid[c + E];
121 0 : return neighborPiece == '-' || neighborPiece == 'J' || neighborPiece == '7';
122 0 : }
123 :
124 0 : bool hasWestConnection(Grid const &grid, Coord const &c) {
125 0 : char const neighborPiece = grid[c + E];
126 0 : return neighborPiece == '-' || neighborPiece == 'F' || neighborPiece == 'L';
127 0 : }
128 :
129 2 : Dir findStartDir(Grid const &grid, Coord const &c) {
130 2 : if (hasNorthConnection(grid, c))
131 2 : return N;
132 0 : else if (hasSouthConnection(grid, c))
133 0 : return S;
134 0 : else if (hasEastConnection(grid, c))
135 0 : return E;
136 0 : else if (hasWestConnection(grid, c))
137 0 : return W;
138 0 : else
139 0 : UNREACHABLE();
140 :
141 0 : return N;
142 2 : }
143 :
144 1 : char findStartPosPiece(Grid const &grid, Coord const &c) {
145 :
146 1 : bool const n = hasNorthConnection(grid, c);
147 1 : bool const s = hasSouthConnection(grid, c);
148 1 : if (n && s)
149 1 : return '|';
150 0 : bool const e = hasEastConnection(grid, c);
151 0 : if (n && e)
152 0 : return 'L';
153 0 : if (s && e)
154 0 : return 'F';
155 0 : bool const w = hasWestConnection(grid, c);
156 0 : if (e && w)
157 0 : return '-';
158 0 : if (n && w)
159 0 : return 'J';
160 0 : if (s && w)
161 0 : return '7';
162 :
163 0 : PANIC(c, n, s, e, w);
164 0 : }
165 :
166 1 : size_t findFarthestAwayPoint(Grid const &grid) {
167 1 : Coord c = grid.find('S');
168 1 : ASSUME(c.x() < grid.xSize());
169 1 : ASSUME(c.y() < grid.ySize());
170 :
171 1 : Dir d = findStartDir(grid, c);
172 1 : size_t ctr = 0;
173 1 : ++ctr;
174 1 : c += d;
175 :
176 13818 : while (grid[c] != 'S') {
177 13817 : d = findNextDir(grid[c], d);
178 13817 : ++ctr;
179 13817 : c += d;
180 13817 : }
181 :
182 1 : return ctr / 2 + ctr % 2;
183 1 : }
184 :
185 1 : auto markLoopWithX(Grid const &grid) {
186 1 : Grid loopGrid(grid.xSize(), grid.ySize(), '.');
187 1 : Coord const startPos = grid.find('S');
188 1 : ASSUME(startPos.x() < grid.xSize());
189 1 : ASSUME(startPos.y() < grid.ySize());
190 :
191 1 : Coord c = startPos;
192 :
193 1 : Dir d = findStartDir(grid, c);
194 1 : loopGrid[c] = 'X';
195 1 : c += d;
196 :
197 13818 : while (grid[c] != 'S') {
198 13817 : d = findNextDir(grid[c], d);
199 13817 : loopGrid[c] = 'X';
200 13817 : c += d;
201 13817 : }
202 :
203 1 : return std::make_tuple(std::move(loopGrid), startPos);
204 1 : }
205 :
206 1 : size_t scanline(Grid const &grid, Grid const &loopGrid) {
207 1 : size_t ctr = 0;
208 141 : for (IndexType y = 0; y < grid.ySize(); ++y) {
209 140 : bool isInner = false;
210 140 : bool edgeFromBelow = false;
211 19740 : for (IndexType x = 0; x < grid.xSize(); ++x) {
212 19600 : if (loopGrid[x, y] != 'X') {
213 : // loopGrid[x, y] = isInner ? 'I' : 'O';
214 5782 : if (isInner)
215 461 : ++ctr;
216 13818 : } else {
217 13818 : switch (grid[x, y]) {
218 2608 : case '|':
219 2608 : isInner = !isInner;
220 2608 : break;
221 2582 : case '-':
222 2582 : continue;
223 2144 : case 'F':
224 2144 : edgeFromBelow = true;
225 2144 : break;
226 2170 : case 'L':
227 2170 : edgeFromBelow = false;
228 2170 : break;
229 2144 : case 'J':
230 2144 : if (edgeFromBelow)
231 1170 : isInner = !isInner;
232 2144 : break;
233 2170 : case '7':
234 2170 : if (!edgeFromBelow)
235 1196 : isInner = !isInner;
236 2170 : break;
237 0 : default:
238 0 : PANIC(x, y, grid[x, y]);
239 13818 : }
240 13818 : }
241 19600 : }
242 140 : }
243 1 : return ctr;
244 1 : }
245 :
246 : } // namespace
247 :
248 1 : template <> std::string solvePart1<2023, 10>(std::string_view const input) {
249 1 : LinewiseInput const lines(input);
250 :
251 1 : Grid grid = lines.makeCharGrid2dWithGhostLayers('.', 1);
252 1 : return std::to_string(findFarthestAwayPoint(grid));
253 1 : }
254 :
255 1 : template <> std::string solvePart2<2023, 10>(std::string_view const input) {
256 1 : LinewiseInput const lines(input);
257 1 : Grid grid = lines.makeCharGrid2dWithGhostLayers('.', 1);
258 1 : auto [loopGrid, startPos] = markLoopWithX(grid);
259 1 : grid[startPos] = findStartPosPiece(grid, startPos);
260 1 : return std::to_string(scanline(grid, loopGrid));
261 1 : }
|
