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
|
#include "aoc.h"
#include <algorithm>
namespace aoc2022 {
typedef sensor::pos pos;
typedef sensor::line line;
typedef std::vector<std::pair<int, std::vector<line>>> vecpair;
static std::vector<line> merge(const std::vector<line>& ls) {
std::vector<line> merged;
if (ls.empty())
return merged;
merged.push_back(ls[0]);
for (size_t i = 1; i < ls.size(); i++) {
line& last = merged[merged.size() - 1];
if (last.p1.x + 1 >= ls[i].p0.x) {
last.p1.x = std::max(last.p1.x, ls[i].p1.x);
} else {
merged.push_back(ls[i]);
}
}
return merged;
}
bool is_beacon(pos p, const std::vector<sensor>& ss) {
for (auto& s : ss) {
if (p == s.ps[1]) {
return true;
}
}
return false;
}
static int count(const std::vector<line>& ls, const std::vector<sensor>& ss) {
int total{0};
for (auto& l : ls) {
total += l.p1.x - l.p0.x + 1;
}
return total;
}
static bool get_line(const std::pair<int, std::vector<line>>& ls, int y, line* l) {
auto y0 = ls.first;
if (y >= y0 && y < y0 + (int)ls.second.size()) {
*l = ls.second[y - y0];
// printf("get %d: (%d-%d)\n", y, l->p0.x, l->p1.x);
return true;
}
return false;
}
int no_beacon(int y, const std::vector<sensor>& ss, const vecpair& ps) {
std::vector<line> ls;
for (auto& p : ps) {
line l;
if (get_line(p, y, &l)) {
if (is_beacon(l.p0, ss)) {
ls.push_back({{l.p0.x + 1, l.p0.y}, l.p1});
} else if (is_beacon(l.p1, ss)) {
ls.push_back({l.p0, {l.p1.x - 1, l.p1.y}});
} else
ls.push_back(l);
}
}
std::sort(ls.begin(), ls.end());
return count(merge(ls), ss);
}
bool check_range(int y, const std::vector<line>& ls, int range, size_t* d) {
line l{{0, y}, {range, y}};
for (size_t i = 0; i < ls.size() - 1; i++) {
auto l0 = ls[i];
auto l1 = ls[i + 1];
auto b1 = l.p0.x >= l0.p0.x && l.p0.x <= l0.p1.x;
auto b2 = l.p1.x >= l1.p0.x && l.p1.x <= l1.p1.x;
// printf("%d: checking (%d,%d) with (%d,%d) and (%d,%d)\n", y, 0, range, l0.p0.x, l0.p1.x, l1.p0.x, l1.p1.x);
if (b1 && b2) {
// printf("%d, %d\n", l0.p1.x + 1, y);
*d = ((size_t)l0.p1.x + 1) * range + y;
return true;
}
}
return false;
}
// static void print(const char* s, int y, const std::vector<line>& ls) {
// for (auto& l : ls) {
// printf("%s %d: (%d-%d)\n", s, y, l.p0.x, l.p1.x);
// }
// }
size_t one_beacon(int range, std::vector<sensor>& ss, const vecpair& ps) {
size_t d{0};
for (int y = 0; y <= range; y++) {
std::vector<line> ls;
for (auto& p : ps) {
line l;
if (get_line(p, y, &l)) {
ls.push_back(l);
}
}
std::sort(ls.begin(), ls.end());
// print("after sort", y, ls);
auto m = merge(ls);
// print("after merge", y, m);
if (check_range(y, m, range, &d)) {
return d;
}
}
return d;
}
std::pair<int, size_t> day15(line_view file) {
std::vector<sensor> ss;
per_line(file, [&ss](line_view lv) {
ss.emplace_back(lv);
return true;
});
std::sort(ss.begin(), ss.end());
std::vector<std::pair<int, std::vector<line>>> ps;
for (auto& s : ss) {
ps.emplace_back(s.lines());
}
auto n1 = no_beacon(2000000, ss, ps);
auto n2 = one_beacon(4000000, ss, ps);
return {n1, n2};
}
} // namespace aoc2022
|
