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
134
135
136
137
|
#include "aoc.h"
#include <algorithm>
namespace aoc2022 {
typedef sensor::pos pos;
typedef sensor::line line;
int sensor::minx;
int sensor::maxx;
std::set<pos> sensor::beacons;
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;
}
static int count(const std::vector<line>& ls) {
int total{0};
for (auto& l : ls) {
total += l.p1.x - l.p0.x + 1;
}
return total;
}
int no_beacon(int y, std::vector<sensor>& ss) {
std::vector<line> ls;
int x = sensor::minx;
while (x <= sensor::maxx) {
pos p{x, y};
for (size_t i = 0; i < ss.size(); i++) {
auto& s = ss[i];
auto d1 = sensor::mdistance(s.ps[0], s.ps[1]);
auto d2 = sensor::mdistance(s.ps[0], p);
if (d2 <= d1) {
auto dy = s.ps[0].y - y;
auto x0 = s.ps[0].x + d2 - std::abs(dy);
if (p == s.ps[1]) {
ls.push_back({{x + 1, y}, {x0, y}});
} else if (pos{x0, y} == s.ps[1]) {
ls.push_back({{x, y}, {x0 - 1, y}});
} else {
ls.push_back({{x, y}, {x0, y}});
}
x = x0;
break;
}
}
x++;
}
std::sort(ls.begin(), ls.end());
return count(merge(ls));
}
bool get_line(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;
}
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) {
std::vector<std::pair<int, std::vector<line>>> ps;
for (auto& s : ss) {
ps.emplace_back(s.lines());
}
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());
auto n1 = no_beacon(2000000, ss);
auto n2 = one_beacon(4000000, ss);
return {n1, n2};
}
} // namespace aoc2022
|
