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
108
109
110
111
112
113
114
115
116
|
use md5;
type Hash = Vec<char>;
// Find first `char' appearing three time in a row in `h', if any
fn find_triple(h: &Hash) -> Option<char> {
for i in 0..h.len() - 2 {
if h[i] == h[i + 1] && h[i] == h[i + 2] {
return Some(h[i]);
}
}
None
}
// Does `h' contain `c' five times in a row?
fn has_quintuple(h: &Hash, c: char) -> bool {
let mut qs: Vec<char> = Vec::new();
for i in 0..h.len() - 4 {
if h[i] == h[i + 1] && h[i] == h[i + 2] && h[i] == h[i + 3] && h[i] == h[i + 4] {
qs.push(h[i])
}
}
qs.contains(&c)
}
struct HashCache<'a> {
salt: &'a str,
reps: usize,
vec: Vec<Hash>,
}
impl<'a> HashCache<'a> {
fn new(salt: &'a str, reps: usize) -> Self {
HashCache {
salt,
reps,
vec: Vec::new(),
}
}
// Generate hashes on demand, and always cache them for later use.
// Can't write this as `impl Index<usize> for HashCache' because
// the `Index' trait only allows an immutable borrow `&self'.
fn at_index(&mut self, i: usize) -> &Hash {
// If this hash is not in the cache yet...
if i >= self.vec.len() {
// ... calculate all hashes up to the requested one
for j in self.vec.len()..i + 1 {
let d = format!("{}{}", self.salt, j);
let mut h = format!("{:x}", md5::compute(d));
// Additional key stretching repetitions
for _k in 0..self.reps {
h = format!("{:x}", md5::compute(h));
}
self.vec.push(h.chars().collect());
}
}
&self.vec[i]
}
}
fn solve_puzzle(salt: &str, reps: usize) -> usize {
// The 64 valid indices we want to find
let mut valid = Vec::new();
let mut hc = HashCache::new(salt, reps);
let mut i = 0;
while valid.len() < 64 {
// If `hc.at_index(i)' contains any `c' three times in a row
if let Some(c) = find_triple(hc.at_index(i)) {
for j in 1..1001 {
if has_quintuple(hc.at_index(i + j), c) {
valid.push(i);
break;
}
}
}
i += 1;
}
*valid.last().unwrap()
}
fn main() {
// My personal puzzle input
let salt = "yjdafjpo";
// Part 1 gives 25427 for me
println!("Part 1 solution: {}", solve_puzzle(salt, 0));
// Part 2 gives 22045 for me
println!("Part 2 solution: {}", solve_puzzle(salt, 2016));
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn part1_example1() {
let salt = "abc";
assert_eq!(solve_puzzle(salt, 0), 22728);
}
#[test]
fn part2_example1() {
let salt = "abc";
assert_eq!(solve_puzzle(salt, 2016), 22551);
}
}
|
