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