year2016/
day14.rs

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

year2016/
day14.rs
