advent_of_code/year2016/
day14.rs

1use crate::common::md5::Context;
2use crate::input::Input;
3
4fn to_hash_chars(hash: &[u8]) -> [u8; 32] {
5    let mut hash_chars = [0_u8; 32];
6    for i in 0..32 {
7        hash_chars[i] = if i % 2 == 0 {
8            (hash[i / 2] & 0xF0) >> 4
9        } else {
10            hash[i / 2] & 0x0F
11        };
12    }
13    hash_chars
14}
15
16fn first_triplet(hash: &[u8]) -> Option<u8> {
17    let hash_chars = to_hash_chars(hash);
18    hash_chars
19        .windows(3)
20        .find(|w| w[0] == w[1] && w[1] == w[2])
21        .map(|w| w[0])
22}
23
24fn contains_five_in_a_row(hash: &[u8], desired_char: u8) -> bool {
25    let hash_chars = to_hash_chars(hash);
26    hash_chars
27        .windows(5)
28        .any(|w| w[0] == desired_char && w.windows(2).all(|adjacent| adjacent[0] == adjacent[1]))
29}
30
31pub fn solve(input: &Input) -> Result<u32, String> {
32    let salt = input.text;
33    if salt.len() > 8 {
34        return Err("Too long salt (max length: 8)".to_string());
35    }
36
37    let mut hash_cache = Vec::new();
38    let mut orig_hasher = Context::new();
39    orig_hasher.consume(salt.as_bytes());
40
41    for i in 0..1000 {
42        let mut hasher = orig_hasher.clone();
43        hasher.consume(i.to_string().as_bytes());
44        if input.is_part_two() {
45            for _ in 0..2016 {
46                let hash: [u8; 16] = hasher.compute();
47                let hash_str = to_hash_chars(&hash)
48                    .iter()
49                    .map(|&b| if b <= 9 { b'0' + b } else { b'a' + (b - 10) })
50                    .collect::<Vec<_>>();
51                hasher = Context::new();
52                hasher.consume(&hash_str);
53            }
54        }
55        let hash: [u8; 16] = hasher.compute();
56        hash_cache.push(hash);
57    }
58
59    let mut valid_key_count = 0;
60    let mut index = 0;
61    loop {
62        let current_hash = hash_cache[index % 1000];
63        hash_cache[index % 1000] = {
64            let content_to_hash = format!("{}{}", salt, index + 1000);
65            let mut hasher = Context::new();
66            hasher.consume(content_to_hash.as_bytes());
67            if input.is_part_two() {
68                for _ in 0..2016 {
69                    let hash: [u8; 16] = hasher.compute();
70                    hasher = Context::new();
71                    let hash_str = to_hash_chars(&hash)
72                        .iter()
73                        .map(|&b| if b <= 9 { b'0' + b } else { b'a' + (b - 10) })
74                        .collect::<Vec<_>>();
75                    hasher.consume(&hash_str);
76                }
77            }
78            hasher.compute()
79        };
80
81        if let Some(triplet_value) = first_triplet(&current_hash) {
82            if hash_cache
83                .iter()
84                .any(|hash| contains_five_in_a_row(hash, triplet_value))
85            {
86                valid_key_count += 1;
87                if valid_key_count == 64 {
88                    return Ok(index as u32);
89                }
90            }
91        }
92
93        if index > 100_000 {
94            break;
95        }
96        index += 1;
97    }
98
99    Err("Time out".to_string())
100}
101
102#[test]
103pub fn tests() {
104    use crate::input::{test_part_one, test_part_two};
105
106    let real_input = include_str!("day14_input.txt");
107    test_part_one!(real_input => 15168);
108    test_part_two!(real_input => 20864);
109}
advent_of_code/year2016/day14.rs

advent_of_code/year2016/
day14.rs
