-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDay09.cpp
More file actions
89 lines (77 loc) · 1.74 KB
/
Day09.cpp
File metadata and controls
89 lines (77 loc) · 1.74 KB
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
#include "Solution.hpp"
#include <iterator>
#include <range/v3/algorithm/max.hpp>
#include <vector>
template <typename T>
struct circular_list {
struct node {
node* prev;
node* next;
T data;
};
~circular_list() {
node* n = curr->next;
while (n != curr) {
delete std::exchange(n, n->next);
}
delete curr;
}
void insert(T data) {
node* n = new node;
n->data = data;
if (curr == nullptr) {
n->prev = n->next = n;
} else {
n->prev = curr->prev;
n->next = curr;
n->prev->next = n->next->prev = n;
}
curr = n;
}
T remove() {
T data = curr->data;
if (curr->next == curr) {
delete std::exchange(curr, nullptr);
} else {
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
delete std::exchange(curr, curr->next);
}
return data;
}
void next(int n = 1) {
while (n--) curr = curr->next;
}
void prev(int n = 1) {
while (n--) curr = curr->prev;
}
node* curr = nullptr;
};
template <>
template <bool part2>
void
Day<9>::solve(std::istream& is, std::ostream& os) {
int players, marbles;
std::string line{std::istream_iterator<char>(is), {}};
sscanf(line.c_str(), "%d players; last marble is worth %d points", &players, &marbles);
if constexpr (part2) {
marbles *= 100;
}
std::vector<unsigned long long> p(players);
circular_list<int> l;
l.insert(0);
for (int m = 1; m < marbles; ++m) {
if (m % 23 == 0) {
l.prev(7);
p[m % players] += m + l.remove();
} else {
l.next(2);
l.insert(m);
}
}
os << ranges::max(p) << '\n';
}
template void
Day<9>::solve<true>(std::istream&, std::ostream&);
template void
Day<9>::solve<false>(std::istream&, std::ostream&);