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
|
#include "aoc.h"
#include <deque>
#include <set>
namespace aoc2017 {
hexagon route(hexagon h, const std::vector<hd>& hds, int* max) {
for (auto& hd : hds) {
h = h.neighbour(hd);
int d = h.a + h.r + h.c;
if (d > *max) {
*max = d;
}
}
return h;
}
int bfs(hexagon start, hexagon target) {
int step{0};
std::deque<hexagon> q;
std::set<hexagon> visited;
q.push_back(start);
while (!q.empty()) {
auto s = q.size();
while (s-- > 0) {
auto h = q.front();
q.pop_front();
if (h == target) {
return step;
}
hexagon ns[6] = {
h.neighbour(hd::n), h.neighbour(hd::nw), h.neighbour(hd::ne),
h.neighbour(hd::sw), h.neighbour(hd::se), h.neighbour(hd::s),
};
for (auto& n : ns) {
if (visited.find(n) == visited.end()) {
visited.insert(n);
q.push_back(n);
}
}
}
step++;
}
return INT32_MAX;
}
std::pair<int64_t, int64_t> day11(line_view file) {
std::vector<hd> ds;
const char* p0 = file.line;
const char* p1 = p0;
line_view d6[] = {"n", "ne", "nw", "se", "sw", "s"};
while (p1 < file.line + file.length) {
if (*p1 == ',' || *p1 == '\n') {
line_view d{p0, p1};
for (int i = 0; i < 6; i++) {
if (d6[i] == d) {
ds.push_back(static_cast<hd>(i));
break;
}
}
p0 = p1 + 1;
}
p1++;
}
int max{INT32_MIN};
auto d = route({0, 0, 0}, ds, &max);
return {d.a + d.r + d.c, max};
}
} // namespace aoc2017
|
