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
|
#include "aoc.h"
#include <set>
namespace aoc2020 {
static int numbers[1000] = {0};
static int get_number(const char* p) {
int d{0};
while (*p >= '0' && *p <= '9') {
d = d * 10 + *p - '0';
p++;
}
return d;
}
bool check25(int i, int* weak) {
std::set<int> si;
for (int x = i - 25; x < i; x++) {
si.insert(numbers[x]);
}
for (int x = i - 25; x < i; x++) {
int y = numbers[i] - numbers[x];
if (si.find(y) != si.end()) {
return true;
}
}
*weak = numbers[i];
return false;
}
bool check_contiguous(int i, int* end, int target) {
if (target == 0) {
*end = i;
return true;
}
if (target < 0) {
return false;
}
return check_contiguous(i + 1, end, target - numbers[i]);
}
static void minmax(int x, int y, int* min, int* max) {
for(int i = x; i < y; i++) {
if (*min > numbers[i]) {
*min = numbers[i];
}
if (*max < numbers[i]) {
*max = numbers[i];
}
}
}
std::pair<int, int> day9(line_view file) {
int i{0};
per_line(file, [&i](line_view lv){
numbers[i++] = get_number(lv.line);
return true;
});
int weak{0};
int pos{0};
for (int i = 25; i < 1000; i++) {
if (!check25(i, &weak)) {
pos = i;
break;
}
}
int e{0};
int min{INT32_MAX}, max{INT32_MIN};
for (int i = 0; i < pos; i++) {
if (check_contiguous(i, &e, weak)) {
minmax(i, e, &min, &max);
}
}
return {weak, min + max};
}
}
|
