Line data Source code
1 : #include "Grid2d.h"
2 : #include "IntegerCast.h"
3 : #include "LinewiseInput.h"
4 : #include "PuzzleImpl.h"
5 :
6 : #include <absl/container/flat_hash_map.h>
7 : #include <absl/hash/hash.h>
8 : #include <libassert/assert.hpp>
9 :
10 : #include <execution>
11 : #include <numeric>
12 : #include <optional>
13 : #include <string>
14 : #include <string_view>
15 :
16 : namespace {
17 : using IndexType = Grid2dSpan<char>::IndexType;
18 :
19 : class LineComparator {
20 : public:
21 200 : LineComparator(Grid2dSpan<char const> const &grid) : _grid(grid) {
22 200 : _lineHashes.reserve(_grid.ySize());
23 200 : absl::Hash<Grid2dSpan<char const>> hasher;
24 2700 : for (int y = 0; y < _grid.ySize(); ++y)
25 2500 : _lineHashes.push_back(hasher(grid.line(y)));
26 200 : }
27 :
28 690 : bool operator()(IndexType const lhs, IndexType const rhs) const {
29 690 : if (_lineHashes[lhs] != _lineHashes[rhs])
30 369 : return false;
31 :
32 321 : return _grid.line(lhs) == _grid.line(rhs);
33 690 : }
34 :
35 : private:
36 : Grid2dSpan<char const> _grid;
37 : std::vector<size_t> _lineHashes;
38 : };
39 :
40 : class ColumnComparator {
41 : public:
42 200 : ColumnComparator(Grid2dSpan<char const> const &grid) : _grid(grid) {
43 200 : _columnHashes.reserve(_grid.xSize());
44 200 : absl::Hash<Grid2dSpan<char const>> hasher;
45 2700 : for (int x = 0; x < _grid.xSize(); ++x)
46 2500 : _columnHashes.push_back(hasher(grid.column(x)));
47 200 : }
48 :
49 1418 : bool operator()(IndexType const lhs, IndexType const rhs) const {
50 1418 : if (_columnHashes[lhs] != _columnHashes[rhs])
51 951 : return false;
52 :
53 467 : return _grid.column(lhs) == _grid.column(rhs);
54 1418 : }
55 :
56 : private:
57 : Grid2dSpan<char const> _grid;
58 : std::vector<size_t> _columnHashes;
59 : };
60 :
61 : class FuzzyLineComparator {
62 : public:
63 100 : FuzzyLineComparator(Grid2dSpan<char const> const &grid) : _grid(grid) {}
64 :
65 328 : bool operator()(IndexType const lhs, IndexType const rhs) const {
66 328 : bool missmatch = false;
67 2271 : for (IndexType x = 0; x < _grid.xSize(); ++x) {
68 2164 : if (_grid[x, lhs] != _grid[x, rhs]) {
69 513 : if (missmatch)
70 221 : return false;
71 292 : missmatch = true;
72 292 : }
73 2164 : }
74 107 : return true;
75 328 : }
76 :
77 : private:
78 : Grid2dSpan<char const> _grid;
79 : };
80 :
81 : class FuzzyColumnComparator {
82 : public:
83 100 : FuzzyColumnComparator(Grid2dSpan<char const> const &grid) : _grid(grid) {}
84 :
85 931 : bool operator()(IndexType const lhs, IndexType const rhs) const {
86 931 : bool missmatch = false;
87 5210 : for (IndexType y = 0; y < _grid.ySize(); ++y) {
88 5031 : if (_grid[lhs, y] != _grid[rhs, y]) {
89 1610 : if (missmatch)
90 752 : return false;
91 858 : missmatch = true;
92 858 : }
93 5031 : }
94 179 : return true;
95 931 : }
96 :
97 : private:
98 : Grid2dSpan<char const> _grid;
99 : };
100 :
101 149 : std::optional<IndexType> findReflectionPoint(IndexType const size, auto const &comp) {
102 :
103 149 : std::optional<IndexType> reflectionLocation;
104 149 : IndexType const last = size - 1;
105 :
106 1285 : auto checkReflection = [&](IndexType x1, IndexType x2) {
107 1285 : if (comp(x1, x2)) {
108 130 : bool isReflection = true;
109 463 : while (isReflection && x1 < x2) {
110 333 : isReflection = comp(x1++, x2--);
111 333 : }
112 130 : if (isReflection) {
113 100 : reflectionLocation = x2;
114 100 : }
115 130 : }
116 1285 : };
117 :
118 939 : for (IndexType x = last % 2 == 1 ? 0 : 1; x < size && !reflectionLocation; x += 2)
119 790 : checkReflection(x, last);
120 :
121 644 : for (IndexType x = last % 2 == 1 ? last : last - 1; x >= 0 && !reflectionLocation; x -= 2)
122 495 : checkReflection(0, x);
123 :
124 149 : return reflectionLocation;
125 149 : }
126 :
127 : std::optional<IndexType> findReflectionPointFuzzy(IndexType const size, auto const &comp,
128 144 : auto const &fuzzyComp) {
129 :
130 144 : std::optional<IndexType> reflectionLocation;
131 144 : IndexType const last = size - 1;
132 :
133 1140 : auto checkReflection = [&](IndexType x1, IndexType x2) {
134 1140 : if (fuzzyComp(x1, x2)) {
135 172 : bool fuzzy = false;
136 172 : bool isReflection = true;
137 662 : while (isReflection && x1 < x2) {
138 490 : isReflection = comp(x1, x2);
139 490 : if (!isReflection && !fuzzy) {
140 120 : fuzzy = true;
141 120 : isReflection = fuzzyComp(x1, x2);
142 120 : }
143 490 : ++x1;
144 490 : --x2;
145 490 : }
146 172 : if (isReflection && fuzzy) {
147 100 : reflectionLocation = x2;
148 100 : }
149 172 : }
150 1140 : };
151 :
152 869 : for (IndexType x = last % 2 == 1 ? 0 : 1; x < size && !reflectionLocation; x += 2)
153 725 : checkReflection(x, last);
154 :
155 560 : for (IndexType x = last % 2 == 1 ? last : last - 1; x >= 0 && !reflectionLocation; x -= 2)
156 416 : checkReflection(0, x);
157 :
158 144 : return reflectionLocation;
159 144 : }
160 :
161 : } // namespace
162 :
163 1 : template <> std::string solvePart1<2023, 13>(std::string_view const input) {
164 1 : LinewiseInput lines(input);
165 1 : auto linesPerGrid = lines.splitOnEmptyLines();
166 :
167 1 : return std::to_string(std::transform_reduce(
168 1 : std::execution::par, linesPerGrid.begin(), linesPerGrid.end(), std::size_t(0), std::plus<>(),
169 100 : [](auto const &gridLines) {
170 100 : Grid2d<char> const grid = makeCharGrid2d(gridLines);
171 100 : LineComparator lineComp(grid);
172 100 : ColumnComparator columnComp(grid);
173 :
174 100 : std::optional<IndexType> columnReflection = findReflectionPoint(grid.xSize(), columnComp);
175 100 : if (columnReflection) {
176 51 : return integerCast<size_t>(*columnReflection + 1);
177 51 : }
178 :
179 49 : std::optional<IndexType> lineReflection = findReflectionPoint(grid.ySize(), lineComp);
180 49 : ASSERT(lineReflection);
181 49 : return integerCast<size_t>((grid.ySize() - (*lineReflection + 1)) * 100); // NOLINT
182 100 : }));
183 1 : }
184 :
185 1 : template <> std::string solvePart2<2023, 13>(std::string_view const input) {
186 1 : LinewiseInput lines(input);
187 1 : auto linesPerGrid = lines.splitOnEmptyLines();
188 :
189 1 : return std::to_string(std::transform_reduce(
190 1 : std::execution::par, linesPerGrid.begin(), linesPerGrid.end(), std::size_t(0), std::plus<>(),
191 100 : [](auto const &gridLines) {
192 100 : Grid2d<char> const grid = makeCharGrid2d(gridLines);
193 100 : LineComparator lineComp(grid);
194 100 : FuzzyLineComparator fuzzyLineComp(grid);
195 100 : ColumnComparator columnComp(grid);
196 100 : FuzzyColumnComparator fuzzyColumnComp(grid);
197 :
198 100 : std::optional<IndexType> columnReflection =
199 100 : findReflectionPointFuzzy(grid.xSize(), columnComp, fuzzyColumnComp);
200 100 : if (columnReflection) {
201 56 : return integerCast<size_t>(*columnReflection + 1);
202 56 : }
203 :
204 44 : std::optional<IndexType> lineReflection =
205 44 : findReflectionPointFuzzy(grid.ySize(), lineComp, fuzzyLineComp);
206 : ASSERT(lineReflection, grid);
207 44 : return integerCast<size_t>((grid.ySize() - (*lineReflection + 1)) * 100); // NOLINT
208 100 : }));
209 1 : }
|
