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
|
#include "aoc.h"
#include <set>
namespace aoc2022 {
int sensor::minx;
int sensor::maxx;
typedef sensor::pos pos;
typedef sensor::line line;
int no_beacon(int y, std::vector<sensor>& ss) {
int total = sensor::maxx - sensor::minx + 1;
char * p = (char *) malloc(total);
memset(p, 0, total);
std::vector<line> ls;
for (auto& s : ss) {
int dy = y - s.ps[0].y;
if (sensor::mdistance(s.ps[0], s.ps[1]) >= std::abs(dy)) {
ls.push_back(s.line_by_dy(dy));
}
}
for (auto& l : ls) {
int x0 = l.p0.x - sensor::minx;
int x1 = l.p1.x - sensor::minx;
memset(p + x0, 1, x1 - x0);
}
int ones{0};
for (int i = 0; i < total; i++) {
ones += (int) *(p + i) == 1;
}
free(p);
return ones;
}
int one_beacon(int y, int range, std::vector<sensor>& ss) {
int total = sensor::maxx - sensor::minx + 1;
char * p = (char *) malloc(total);
memset(p, 0, total);
std::vector<line> ls;
for (auto& s : ss) {
int dy = y - s.ps[0].y;
if (sensor::mdistance(s.ps[0], s.ps[1]) >= std::abs(dy)) {
ls.push_back(s.line_by_dy(dy));
}
}
for (auto& l : ls) {
int x0 = l.p0.x - sensor::minx;
int x1 = l.p1.x - sensor::minx;
memset(p + x0, 1, x1 - x0);
}
for (int i = 0 - sensor::minx; i <= range - sensor::minx; i++) {
if (*(p + i) == 0) {
free(p);
return sensor::minx + i + 1;
}
}
free(p);
return range;
}
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;
});
auto n = no_beacon(2000000, ss);
// int total = 4000000;
// for (int y = 0; y <= total; y++) {
// int x = one_beacon(y, total, ss);
// if (x != total) {
// printf("%d %d\n", x, y);
// break;
// }
// }
return {n, 0};
}
} // namespace aoc2022
|
