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
|
#include "aoc.h"
#include "md5.h"
#include <deque>
#include <map>
#include <set>
namespace aoc2016 {
struct pos {
int x;
int y;
int n;
std::string* path;
bool operator==(pos p) { return x == p.x && y == p.y; }
friend bool operator<(pos p1, pos p2) { return p1.x < p2.x ? true : p1.x > p2.x ? false : p1.y < p2.y; }
bool isvalid() const noexcept { return x > 0 && x < 5 && y > 0 && y < 5; }
};
static pos bfs(pos p, pos target, const std::string& passcode) {
std::deque<pos> q;
// std::set<pos> visited;
q.push_back(p);
auto is_open = [](char c) { return c > 'a' && c <= 'f'; };
while (!q.empty()) {
auto s = q.size();
while (s-- > 0) {
pos p0 = q.front();
q.pop_front();
if (p0 == target) {
return p0;
}
pos ns[4] = {
{p0.x, p0.y - 1, p0.n + 1, new std::string(*p0.path)},
{p0.x, p0.y + 1, p0.n + 1, new std::string(*p0.path)},
{p0.x - 1, p0.y, p0.n + 1, new std::string(*p0.path)},
{p0.x + 1, p0.y, p0.n + 1, new std::string(*p0.path)},
};
for (size_t i = 0; i < 4; i++) {
pos nx = ns[i];
std::string pass{passcode};
pass.append(*nx.path);
char md5[33] = {0};
memcpy(md5, md5sum((char*)pass.c_str()), 32);
// printf("%s: %d %d %d %s\n", md5, p0.x, p0.y, p0.n, (*p0.path).c_str());
if (nx.isvalid() && is_open(*(md5 + i))) {
char direction[] = {'U', 'D', 'L', 'R'};
nx.path->push_back(direction[i]);
q.push_back(nx);
}
}
}
}
return target;
}
static void dfs(pos p0, pos target, const std::string& passcode, int* max) {
if (p0 == target) {
if (*max < p0.n) {
*max = p0.n;
}
} else {
pos ns[4] = {
{p0.x, p0.y - 1, p0.n + 1, new std::string(*p0.path)},
{p0.x, p0.y + 1, p0.n + 1, new std::string(*p0.path)},
{p0.x - 1, p0.y, p0.n + 1, new std::string(*p0.path)},
{p0.x + 1, p0.y, p0.n + 1, new std::string(*p0.path)},
};
auto is_open = [](char c) { return c > 'a' && c <= 'f'; };
for (size_t i = 0; i < 4; i++) {
pos nx = ns[i];
std::string pass{passcode};
pass.append(*nx.path);
char md5[33] = {0};
memcpy(md5, md5sum((char*)pass.c_str()), 32);
if (nx.isvalid() && is_open(*(md5 + i))) {
char direction[] = {'U', 'D', 'L', 'R'};
nx.path->push_back(direction[i]);
dfs(nx, target, passcode, max);
}
}
}
}
std::pair<std::string, int64_t> day17(line_view) {
static std::string ss[] = {"", "UNKNOWN"};
pos b = {1, 1, 0, ss};
pos e = {4, 4, INT32_MAX, ss + 1};
auto p = bfs(b, e, "bwnlcvfs");
int max{INT32_MIN};
dfs(b, e, "bwnlcvfs", &max);
return {*p.path, max};
}
} // namespace aoc2016
|
