-
Notifications
You must be signed in to change notification settings - Fork 0
/
challenge21.cpp
183 lines (147 loc) · 6.32 KB
/
challenge21.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include "challenge21.hpp"
#include "helper.hpp"
#include "print.hpp"
#include <algorithm>
#include <cmath>
#include <unordered_set>
using namespace std::string_view_literals;
namespace {
template<typename T>
struct Coordinate {
T Row;
T Column;
constexpr bool operator==(const Coordinate&) const noexcept = default;
constexpr auto operator<=>(const Coordinate&) const noexcept = default;
Coordinate left(void) const noexcept {
return {Row, Column - 1};
}
Coordinate right(void) const noexcept {
return {Row, Column + 1};
}
Coordinate up(void) const noexcept {
return {Row - 1, Column};
}
Coordinate down(void) const noexcept {
return {Row + 1, Column};
}
};
} //namespace
namespace std {
template<typename T>
struct hash<Coordinate<T>> {
size_t operator()(const Coordinate<T>& c) const noexcept {
constexpr auto bits = std::numeric_limits<T>::digits / 2;
constexpr auto mask = ((T{1} << bits) - 1);
return std::hash<T>{}((c.Row << bits) | (c.Column & mask));
}
};
template<typename T, typename U>
struct hash<std::pair<Coordinate<T>, U>> {
size_t operator()(const std::pair<Coordinate<T>, U>& p) const noexcept {
return std::hash<Coordinate<T>>{}(p.first) ^ std::hash<U>{}(p.second);
}
};
} //namespace std
namespace {
using MyCoordinate = Coordinate<std::int64_t>;
using Map = const std::vector<std::string_view>&;
std::int64_t MaxColumn = 0;
std::int64_t MaxRow = 0;
bool isValid(const MyCoordinate& coordinate) noexcept {
return coordinate.Column >= 0 && coordinate.Column < MaxColumn && coordinate.Row >= 0 && coordinate.Row < MaxRow;
}
MyCoordinate findStart(Map map) noexcept {
MyCoordinate ret;
for ( ret.Row = 0; ret.Row < MaxRow; ++ret.Row ) {
ret.Column = static_cast<std::int64_t>(map[static_cast<std::size_t>(ret.Row)].find('S'));
if ( static_cast<std::size_t>(ret.Column) != std::string::npos ) {
return ret;
} //if ( static_cast<std::size_t>(ret.Column) != std::string::npos )
} //for ( ret.Row = 0; ret.Row < MaxRow; ++ret.Row )
return {};
}
template<bool Infinite>
struct ReachableCalculator {
::Map Map;
ReachableCalculator(::Map map) noexcept : Map{map} {
return;
}
std::int64_t calcReachable(MyCoordinate start, std::int64_t totalSteps) noexcept {
std::unordered_set<MyCoordinate> alreadySeen;
std::array<std::int64_t, 2> counter{};
std::vector<MyCoordinate> current;
std::vector<MyCoordinate> next{start};
//Step 0 ist die Start Position.
for ( std::size_t step = 0; step <= static_cast<std::size_t>(totalSteps); ++step ) {
std::swap(current, next);
next.clear();
for ( auto coordinate : current ) {
const auto normalizedCoordinate = [](MyCoordinate c) noexcept {
if constexpr ( !Infinite ) {
return c;
} //if constexpr ( !Infinite )
else {
while ( c.Row < 0 ) {
c.Row += MaxRow;
} //while ( c.Row < 0 )
c.Row %= MaxRow;
while ( c.Column < 0 ) {
c.Column += MaxColumn;
} //while ( c.Column < 0 )
c.Column %= MaxColumn;
return c;
} //else -> if constexpr( !Infinite )
}(coordinate);
if constexpr ( !Infinite ) {
if ( !isValid(coordinate) ) {
continue;
} //if ( !isValid(coordinate) )
} //if constexpr ( !Infinite )
const auto plot = Map[static_cast<std::size_t>(normalizedCoordinate.Row)]
[static_cast<std::size_t>(normalizedCoordinate.Column)];
if ( plot == '#' ) {
continue;
} //if ( plot == '#' )
if ( !alreadySeen.insert(coordinate).second ) {
continue;
} //if ( !alreadySeen.insert(coordinate).second )
alreadySeen.insert(coordinate);
++counter[step % 2];
next.push_back(coordinate.down());
next.push_back(coordinate.up());
next.push_back(coordinate.left());
next.push_back(coordinate.right());
} //for ( auto coordinate : current )
} //for ( int step = 0; step <= totalSteps; ++step )
return counter[static_cast<std::size_t>(totalSteps) % 2];
}
};
} //namespace
bool challenge21(Map map) {
throwIfInvalid(!map.empty());
MaxRow = static_cast<std::int64_t>(map.size());
MaxColumn = static_cast<std::int64_t>(map.front().size());
const auto start = findStart(map);
throwIfInvalid(MaxColumn == MaxRow);
throwIfInvalid(start.Row == MaxRow / 2);
throwIfInvalid(start.Column == MaxColumn / 2);
ReachableCalculator<false> partOneCalculator{map};
auto reachable = partOneCalculator.calcReachable(start, 64);
myPrint(" == Result of Part 1: {:d} ==\n", reachable);
ReachableCalculator<true> partTwoCalculator{map};
auto calcPart2 = [&partTwoCalculator, &start](int steps) noexcept {
//Extrapolation über ein quadratisches Polynom. Nicht das ich selbst auf die Idee gekommen wäre...
auto y1 = partTwoCalculator.calcReachable(start, start.Row);
auto y2 = partTwoCalculator.calcReachable(start, MaxRow + start.Row);
auto y3 = partTwoCalculator.calcReachable(start, MaxRow * 2 + start.Row);
auto a = (y3 + y1 - 2 * y2) / 2;
auto b = (4 * y2 - 3 * y1 - y3) / 2;
auto c = y1;
auto evalAt = (steps - start.Row) / MaxRow;
auto ret = (a * evalAt * evalAt) + (b * evalAt) + c;
return ret;
};
auto reachable2 = calcPart2(26501365);
myPrint(" == Result of Part 2: {:d} ==\n", reachable2);
return reachable == 3858 && reachable2 == 636'350'496'972'143;
}