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