blob: 16e3e0a6689bdcc85b7a86e99062358195418b0d (
plain)
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
|
#include "aoc.h"
#include <algorithm>
namespace aoc2016 {
static void get_number(const char** pp, uint32_t* d) {
const char* p = *pp;
while (*p >= '0' && *p <= '9') {
*d = *d * 10 + *p - '0';
p++;
}
*pp = p;
}
struct ipdigit {
uint32_t ds[2] = {0};
void print() const noexcept { printf("%u-%u\n", ds[0], ds[1]); }
ipdigit(line_view lv) {
const char* p = lv.line;
int i{0};
while (p < lv.line + lv.length) {
if (*p >= '0' && *p <= '9') {
get_number(&p, ds + i);
i++;
}
p++;
}
}
friend bool operator<(ipdigit ip1, ipdigit ip2) {
return ip1.ds[0] < ip2.ds[0] ? true : ip1.ds[0] > ip2.ds[0] ? false : ip1.ds[1] < ip2.ds[1];
}
};
static bool merge(ipdigit& ip, const ipdigit& ipx) {
if (ip.ds[1] >= ipx.ds[1]) {
return true;
}
if (ip.ds[1] < ipx.ds[1] && ip.ds[1] + 1 >= ipx.ds[0]) {
ip.ds[1] = ipx.ds[1];
return true;
}
return false;
}
static std::vector<ipdigit> merge(const std::vector<ipdigit>& ips) {
std::vector<ipdigit> ds;
ipdigit ip = ips[0];
for (size_t i = 1; i < ips.size(); i++) {
if (!merge(ip, ips[i])) {
ds.push_back(ip);
ip = ips[i];
}
}
ds.push_back(ip);
return ds;
}
static size_t count(std::vector<ipdigit>& ips) {
size_t c{0};
for (size_t i = 1; i < ips.size(); i++) {
c += ips[i].ds[0] - ips[i - 1].ds[1] - 1;
}
uint32_t max{UINT32_MAX};
auto& last = ips[ips.size() - 1];
c += max - last.ds[1];
return c;
}
std::pair<int64_t, int64_t> day20(line_view file) {
std::vector<ipdigit> ips;
per_line(file, [&ips](line_view lv) {
ips.emplace_back(lv);
return true;
});
std::sort(ips.begin(), ips.end());
auto ds = merge(ips);
// printf("%zu\n", count(ds));
// for (auto ip : ds) {
// ip.print();
// }
return {0, count(ds)};
}
} // namespace aoc2016
|
