Line data Source code
1 : #include "LinewiseInput.h"
2 : #include "PuzzleImpl.h"
3 :
4 : #include <libassert/assert.hpp>
5 :
6 : #include <algorithm>
7 : #include <array>
8 : #include <charconv>
9 : #include <string>
10 : #include <string_view>
11 :
12 : namespace {
13 :
14 : unsigned toUnsigned(std::string_view::const_iterator const begin,
15 1772 : std::string_view::const_iterator const end) {
16 1772 : unsigned i = 0u;
17 1772 : [[maybe_unused]] std::from_chars_result result = std::from_chars(begin, end, i);
18 1772 : DEBUG_ASSERT(result.ec == std::errc());
19 1772 : return i;
20 1772 : }
21 :
22 : size_t getPartNumbers(std::string_view const line, std::string_view const topNeighborLine,
23 140 : std::string_view const bottomNeighborLine) {
24 :
25 22016 : auto isDigit = [](char const c) { return std::isdigit(c); };
26 8448 : auto isSymbol = [](char const c) { return c != '.' && !std::isdigit(c); };
27 :
28 140 : size_t sum = 0u;
29 :
30 1350 : for (auto it = std::ranges::find_if(line, isDigit); it != line.end();
31 1210 : it = std::find_if(it, line.end(), isDigit)) {
32 1210 : auto numberStart = it;
33 1210 : it = std::find_if_not(it, line.end(), isDigit);
34 1210 : auto numberEnd = it;
35 :
36 1210 : size_t const startPos = std::distance(line.begin(), numberStart);
37 1210 : size_t leftNeighborPos = startPos;
38 1210 : if (leftNeighborPos != 0) {
39 1197 : --leftNeighborPos;
40 1197 : if (isSymbol(line[leftNeighborPos])) {
41 88 : sum += toUnsigned(numberStart, numberEnd);
42 88 : continue;
43 88 : }
44 1197 : }
45 :
46 1122 : size_t const endPos = std::distance(line.begin(), numberEnd);
47 1122 : size_t rightNeighborPos = endPos;
48 1122 : if (rightNeighborPos != line.size()) {
49 1118 : ++rightNeighborPos;
50 1118 : if (isSymbol(line[rightNeighborPos - 1u])) {
51 93 : sum += toUnsigned(numberStart, numberEnd);
52 93 : continue;
53 93 : }
54 1118 : }
55 :
56 1642 : auto checkLine = [=](std::string_view const l) {
57 1642 : return !l.empty() &&
58 1642 : std::any_of(l.begin() + leftNeighborPos, l.begin() + rightNeighborPos, isSymbol);
59 1642 : };
60 :
61 1029 : if (checkLine(topNeighborLine) || checkLine(bottomNeighborLine)) {
62 890 : sum += toUnsigned(numberStart, numberEnd);
63 890 : }
64 1029 : }
65 140 : return sum;
66 140 : }
67 :
68 : class Gears {
69 : public:
70 701 : bool addGear(size_t const gear) {
71 701 : if (_numGears == 2u)
72 0 : return false;
73 701 : _gears[_numGears++] = gear;
74 701 : return true;
75 701 : }
76 :
77 372 : [[nodiscard]] size_t ratio() const { return _gears[0] * _gears[1]; }
78 :
79 : private:
80 : std::array<size_t, 2u> _gears = {0u, 0u};
81 : size_t _numGears = 0u;
82 : };
83 :
84 : size_t getGearRatios(std::string_view const line, std::string_view const topNeighborLine,
85 140 : std::string_view const bottomNeighborLine) {
86 :
87 5964 : auto isDigit = [](char const c) { return std::isdigit(c); };
88 :
89 140 : size_t sum = 0u;
90 :
91 512 : for (auto it = std::ranges::find(line, '*'); it != line.end();
92 372 : it = std::find(std::next(it), line.end(), '*')) {
93 :
94 372 : Gears gears;
95 :
96 372 : auto addGearsLeftAndRight = [&gears, isDigit](std::string_view line,
97 388 : std::string_view::const_iterator starIt) {
98 388 : auto leftNeighbor = starIt;
99 589 : while (leftNeighbor != line.begin() && isDigit(*std::prev(leftNeighbor))) {
100 201 : --leftNeighbor;
101 201 : }
102 388 : if (leftNeighbor != starIt) {
103 69 : if (!gears.addGear(toUnsigned(leftNeighbor, starIt)))
104 0 : return false;
105 69 : }
106 :
107 388 : auto rightNeighbor = std::next(starIt);
108 578 : while (rightNeighbor != line.end() && isDigit(*rightNeighbor)) {
109 190 : ++rightNeighbor;
110 190 : }
111 388 : if (std::prev(rightNeighbor) != starIt) {
112 67 : if (!gears.addGear(toUnsigned(std::next(starIt), rightNeighbor)))
113 0 : return false;
114 67 : }
115 388 : return true;
116 388 : };
117 :
118 372 : ASSUME(addGearsLeftAndRight(line, it));
119 :
120 372 : size_t const starPos = std::distance(line.begin(), it);
121 744 : auto addGears = [&gears, starPos, isDigit, addGearsLeftAndRight](std::string_view const l) {
122 744 : if (starPos != 0 && starPos + 1u != l.size() && isDigit(l[starPos - 1u]) &&
123 744 : !isDigit(l[starPos]) && isDigit(l[starPos + 1])) {
124 : // special case: two numbers
125 16 : auto const starIt = l.begin() + starPos;
126 16 : return addGearsLeftAndRight(l, starIt);
127 16 : }
128 :
129 728 : auto findGear = [&](size_t const pos) {
130 565 : auto leftIt = l.begin() + pos;
131 1053 : while (leftIt != l.begin() && isDigit(*std::prev(leftIt))) {
132 488 : --leftIt;
133 488 : }
134 565 : auto rightIt = l.begin() + pos + 1u;
135 1142 : while (rightIt != l.end() && isDigit(*rightIt)) {
136 577 : ++rightIt;
137 577 : }
138 565 : return toUnsigned(leftIt, rightIt);
139 565 : };
140 :
141 728 : std::optional<unsigned> gear;
142 728 : if (isDigit(l[starPos])) {
143 325 : gear = findGear(starPos);
144 403 : } else if (starPos != 0 && isDigit(l[starPos - 1u])) {
145 117 : gear = findGear(starPos - 1u);
146 286 : } else if (starPos != l.size() - 1U && isDigit(l[starPos + 1u])) {
147 123 : gear = findGear(starPos + 1u);
148 123 : }
149 728 : if (gear) {
150 565 : if (!gears.addGear(*gear))
151 0 : return false;
152 565 : }
153 :
154 728 : return true;
155 728 : };
156 :
157 372 : if (!addGears(topNeighborLine))
158 0 : continue;
159 :
160 372 : if (!addGears(bottomNeighborLine))
161 0 : continue;
162 :
163 372 : sum += gears.ratio();
164 372 : }
165 140 : return sum;
166 140 : }
167 :
168 : } // namespace
169 :
170 1 : template <> std::string solvePart1<2023, 3>(std::string_view const input) {
171 1 : LinewiseInput const lines(input);
172 :
173 1 : size_t sum = 0u;
174 141 : for (auto it = lines.begin(); it != lines.end(); ++it) {
175 140 : std::string_view top = it == lines.begin() ? std::string_view{} : *std::prev(it);
176 140 : std::string_view bottom = std::next(it) == lines.end() ? std::string_view{} : *std::next(it);
177 140 : sum += getPartNumbers(*it, top, bottom);
178 140 : }
179 :
180 1 : return std::to_string(sum);
181 1 : }
182 :
183 1 : template <> std::string solvePart2<2023, 3>(std::string_view const input) {
184 1 : LinewiseInput const lines(input);
185 :
186 1 : size_t sum = 0u;
187 141 : for (auto it = lines.begin(); it != lines.end(); ++it) {
188 140 : std::string_view top = it == lines.begin() ? std::string_view{} : *std::prev(it);
189 140 : std::string_view bottom = std::next(it) == lines.end() ? std::string_view{} : *std::next(it);
190 140 : sum += getGearRatios(*it, top, bottom);
191 140 : }
192 :
193 1 : return std::to_string(sum);
194 1 : }
|
