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
|
#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 = 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));
}
size_t one_beacon(int range, std::vector<sensor>& ss) {
for (int y = 0; y <= range; y++) {
if (y % 10000 == 0) {
printf("%d\n", y);
}
std::vector<line> ls;
int x = 0;
while (x <= range) {
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());
auto m = merge(ls);
if (m.size() > 1) {
pos p{m[0].p1.x+1, y};
if (sensor::beacons.find(p) == sensor::beacons.end()) {
printf("%d %d\n", m[0].p1.x+1, y);
return ((size_t) m[0].p1.x+1) * range + y;
}
}
}
return 0;
}
std::pair<int, int> 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
|
