year2016/
day14.rs

1use std::collections::{BTreeMap, BTreeSet};
2use std::ops::DerefMut;
3use std::sync::Mutex;
4use utils::md5;
5use utils::prelude::*;
6
7/// Finding MD5 hashes, part three.
8///
9/// Similar to [2015 Day 4](../year2015/struct.Day04.html) and [2016 Day 5](crate::Day05), but with
10/// even more complex logic to assemble the answer from the matching hashes and key stretching for
11/// part 2.
12///
13/// See [`md5::find_hash_with_appended_count()`].
14#[derive(Clone, Debug)]
15pub struct Day14<'a> {
16    prefix: &'a str,
17}
18
19impl<'a> Day14<'a> {
20    pub fn new(input: &'a str, _: InputType) -> Result<Self, InputError> {
21        Ok(Self { prefix: input })
22    }
23
24    #[must_use]
25    pub fn part1(&self) -> u32 {
26        // TODO using multiple threads is not worth it for ~10,000 hashes
27        self.find_64th_key(0)
28    }
29
30    #[must_use]
31    pub fn part2(&self) -> u32 {
32        self.find_64th_key(2016)
33    }
34
35    fn find_64th_key(&self, additional: u32) -> u32 {
36        let mutex = Mutex::new((BTreeSet::new(), BTreeMap::new(), BTreeMap::new()));
37
38        md5::find_hash_with_appended_count(self.prefix, additional, |i, [a, b, c, d]: [u32; 4]| {
39            // Spread each nibble into bytes like utils::md5::u32_to_hex, but without the
40            // unnecessary mapping to ASCII hex
41            let mut nibble_bytes = [0u8; 32];
42            nibble_bytes[0..8].copy_from_slice(&spread_nibbles(a).to_be_bytes());
43            nibble_bytes[8..16].copy_from_slice(&spread_nibbles(b).to_be_bytes());
44            nibble_bytes[16..24].copy_from_slice(&spread_nibbles(c).to_be_bytes());
45            nibble_bytes[24..32].copy_from_slice(&spread_nibbles(d).to_be_bytes());
46
47            let Some(triplet) = nibble_bytes
48                .windows(3)
49                .find(|&w| w[0] == w[1] && w[0] == w[2])
50                .map(|w| 1u16 << w[0])
51            else {
52                // No triplet means there is also no quintuplet
53                return false;
54            };
55
56            let quintuplet = nibble_bytes
57                .windows(5)
58                .filter(|&w| w[0] == w[1] && w[0] == w[2] && w[0] == w[3] && w[0] == w[4])
59                .fold(0, |acc, w| acc | (1u16 << w[0]));
60
61            let mut guard = mutex.lock().unwrap();
62            let (keys, triplets, quintuplets) = guard.deref_mut();
63
64            triplets.insert(i, triplet);
65
66            // Check if a matching quintuplet has already been found in the following thousand
67            if quintuplets
68                .range(i + 1..i + 1001)
69                .any(|(_, &m)| triplet & m != 0)
70            {
71                keys.insert(i);
72            }
73
74            if quintuplet != 0 {
75                quintuplets.insert(i, quintuplet);
76
77                // Check if any matching triplets have already been found in the previous thousand
78                triplets
79                    .range(i.saturating_sub(1000)..i)
80                    .filter(|&(_, &m)| quintuplet & m != 0)
81                    .for_each(|(&k, _)| {
82                        keys.insert(k);
83                    });
84            }
85
86            keys.len() >= 64
87        });
88
89        let (keys, ..) = mutex.into_inner().unwrap();
90        *keys.iter().nth(63).unwrap()
91    }
92}
93
94fn spread_nibbles(n: u32) -> u64 {
95    let mut n = u64::from(n);
96    // n = 0x0000_0000_1234_5678
97
98    n = ((n & 0x0000_0000_FFFF_0000) << 16) | (n & 0x0000_0000_0000_FFFF);
99    // n = 0x0000_1234_0000_5678
100
101    n = ((n & 0x0000_FF00_0000_FF00) << 8) | (n & 0x0000_00FF_0000_00FF);
102    // n = 0x0012_0034_0056_0078
103
104    n = ((n & 0x00F0_00F0_00F0_00F0) << 4) | (n & 0x000F_000F_000F_000F);
105    // n = 0x0102_0304_0506_0708
106
107    n
108}
109
110examples!(Day14<'_> -> (u32, u32) [
111    {input: "abc", part1: 22728, part2: 22551},
112]);
year2016/day14.rs

year2016/
day14.rs
