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
|
#include <iostream>
#include <vector>
using namespace std;
namespace {
struct Marble {
explicit Marble(long score)
: score{ score }
{
}
Marble(long score, Marble* prev, Marble* next)
: score{ score }
, prev{ prev }
, next{ next }
{
}
[[nodiscard]]
Marble* insert_after_two(long value) const
{
auto* insert_after = this->next;
auto* new_marble = new Marble(value, insert_after, insert_after->next); // NOLINT
insert_after->next->prev = new_marble;
insert_after->next = new_marble;
return new_marble;
}
[[nodiscard]]
pair<Marble*, long> remove_seventh_back()
{
auto* to_remove = this;
for ( int i = 0; i != 7; ++i ) {
to_remove = to_remove->prev;
}
to_remove->prev->next = to_remove->next;
to_remove->next->prev = to_remove->prev;
auto* new_current = to_remove->next;
auto score = to_remove->score;
delete to_remove; // NOLINT
return { new_current, score };
}
long score;
Marble* prev{ this };
Marble* next{ this };
};
long
solve(const size_t players, const long last_marble)
{
auto current = new Marble(0); // NOLINT
vector<long> scores(players, 0);
size_t player = 0;
for ( long marble = 1; marble <= last_marble; ++marble ) {
if ( marble % 23 != 0 ) {
current = current->insert_after_two(marble);
}
else {
auto [new_current, removed_score] = current->remove_seventh_back();
scores[player] += marble + removed_score;
current = new_current;
}
player += 1;
player %= players;
}
Marble* start = current;
do {
Marble* next = start->next;
delete start; // NOLINT
start = next;
} while ( start != current );
return ranges::max(scores);
}
void
part1(const size_t players, const long last_marble)
{
cout << "Part 1: " << solve(players, last_marble) << '\n';
}
void
part2(const size_t players, const long last_marble)
{
cout << "Part 2: " << solve(players, last_marble * 100) << '\n';
}
} // namespace
int
main()
{
static const size_t players = 400;
static const long points = 71864;
part1(players, points);
part2(players, points);
}
|
