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
|
#include "aoc.h"
#include "md5.h"
#include <map>
#include <set>
namespace aoc2016 {
struct md5_property {
std::string md5;
char c = 0;
};
static std::vector<md5_property> md5s;
static std::map<char, std::vector<size_t>> has5s;
static bool is_equal(const char* p0, const char* p1) {
while (p0 < p1) {
if (*p0 != *p1) {
return false;
}
p0++;
}
return true;
}
const char* has(const char* md5, int n) {
const char* p = md5;
while (p < md5 + 32 - n + 1) {
if (is_equal(p, p + n - 1)) {
return p;
}
p++;
}
return nullptr;
}
static bool in_range(char c, size_t l, size_t h) {
auto it = has5s.find(c);
if (it != has5s.end()) {
auto& v = it->second;
size_t ll = v[0];
size_t hh = v[v.size() - 1];
auto is_in = [l, h](size_t x) { return x >= l && x <= h; };
if (is_in(ll) || is_in(hh)) {
return true;
}
}
return false;
}
std::string stretching(const char* md5, size_t n) {
std::string s{md5};
while (n-- > 0) {
s = std::string{md5sum((char*)s.c_str()), 32};
}
return s;
}
md5_property md5(const char* secret, size_t index) {
if (index >= md5s.size()) {
char buf[128] = {0};
int l = strlen(secret);
memcpy(buf, secret, l);
auto s = md5s.size();
md5s.resize(index + 1);
for (size_t i = s; i < md5s.size(); i++) {
sprintf(buf + l, "%zu", i);
md5s[i].md5 = std::string(md5sum(buf), 32);
// md5s[i].md5 = stretching(md5s[i].md5.c_str(), 2016);
auto pc3 = has(md5s[i].md5.c_str(), 3);
if (pc3 != nullptr) {
md5s[i].c = *pc3;
auto pc5 = has(md5s[i].md5.c_str(), 5);
if (pc5 != nullptr) {
// printf("%zu has 5 %c\n", i, *pc3);
auto p = has5s.insert({*pc3, {i}});
if (!p.second) {
p.first->second.push_back(i);
}
}
}
}
}
return md5s[index];
}
size_t find_key(int* count, int max) {
size_t i{0};
while (*count < max && i < md5s.size()) {
auto& p = md5s[i];
if (p.c > 0 && in_range(p.c, i + 1, i + 1000)) {
// printf("%zu %s with %c\n", i, p.md5.c_str(), p.c);
*count += 1;
}
i++;
}
return i - 1;
}
std::pair<size_t, int64_t> day14(line_view) {
// md5("abc", 30000);
md5("jlmsuwbz", 50000);
int count{0};
auto i = find_key(&count, 64);
return {i, 0};
}
} // namespace aoc2016
|
