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