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
|
#include "common.h"
#include <vector>
#include <set>
namespace aoc2022 {
struct sensor {
struct pos {
int x = 0;
int y = 0;
pos() {}
pos(int i, int j): x(i), y(j) {}
bool operator==(pos px) const noexcept {
return x == px.x && y == px.y;
}
bool operator<(pos px) const noexcept {
return x < px.x ? true : x > px.x ? false : y < px.y;
}
};
struct line {
pos p0;
pos p1;
line() {}
line(pos x, pos y): p0(x), p1(y) {}
friend bool operator<(const line& l1, const line& l2) {
return l1.p0.x < l2.p0.x;
}
};
static int minx;
static int maxx;
static std::set<pos> beacons;
pos ps[2] = {{0,0},{0,0}};
static int mdistance(pos p1, pos p2) {
return std::abs(p1.x - p2.x) + std::abs(p1.y - p2.y);
}
std::pair<int, std::vector<line>> lines() const noexcept {
auto d = mdistance(ps[0], ps[1]);
std::vector<line> ls;
for(int y = ps[0].y - d; y <= ps[0].y + d; y++) {
auto dx = d - std::abs(ps[0].y - y);
pos p0 = {ps[0].x - dx, y};
pos p1 = {ps[0].x + dx, y};
ls.emplace_back(p0, p1);
}
return {ps[0].y - d,ls};
}
void get_number(const char** pp, int* d) {
const char *p = *pp;
int sign = 1;
if (*p == '-') {
sign = -1;
p++;
}
while (*p >= '0' && *p <= '9') {
*d = *d * 10 + *p - '0';
p++;
}
*d *= sign;
*pp = p;
}
void print() {
printf("S(%d, %d) B(%d, %d)\n", ps[0].x, ps[0].y, ps[1].x, ps[1].y);
}
sensor(line_view lv) {
const char* p = lv.line;
int *is[] = {&ps[0].x, &ps[0].y, &ps[1].x, &ps[1].y};
int n{0};
while (p < lv.line + lv.length) {
if (*p == '=') {
const char* p0 = p+1;
get_number(&p0, is[n]);
p = p0;
n++;
}
p++;
}
beacons.insert(ps[1]);
auto x1 = ps[0].x - mdistance(ps[0], ps[1]);
auto x2 = ps[0].x + mdistance(ps[0], ps[1]);
if (minx > x1) minx = x1;
if (maxx < x2) maxx = x2;
}
bool operator<(const sensor& s) const noexcept {
return ps[0].x < s.ps[0].x;
}
};
std::pair<int, size_t> day15(line_view);
}
|
