aoc/year2015/
day04.rs

1//! # The Ideal Stocking Stuffer
2//!
3//! This solution relies on brute forcing combinations as quickly as possible using an internal
4//! implementation of the [`MD5`] hashing algorithm.
5//!
6//! Each number's hash is independent of the others, so we speed things up by using threading
7//! to search in parallel in blocks of 1000 numbers at a time.
8//!
9//! Using the [`format!`] macro to join the secret key to the number is quite slow. To go faster
10//! we reuse the same `u8` buffer, incrementing digits one at a time.
11//! The numbers from 1 to 999 are handled specially.
12//!
13//! Interestingly, the total time to solve this problem is *extremely* sensitive to the secret key
14//! provided as input. For example my key required ~10⁷ iterations to find the answer to part two.
15//! However for unit testing, I was able to randomly find a value that takes only 455 iterations,
16//! about 22,000 times faster!
17//!
18//! [`MD5`]: crate::util::md5
19//! [`format!`]: std::format
20use crate::util::md5::*;
21use crate::util::thread::*;
22use std::sync::atomic::{AtomicU32, Ordering};
23
24pub struct Shared {
25    prefix: String,
26    iter: AtomicIter,
27    first: AtomicU32,
28    second: AtomicU32,
29}
30
31pub fn parse(input: &str) -> Shared {
32    let shared = Shared {
33        prefix: input.trim().to_owned(),
34        iter: AtomicIter::new(1000, 1000),
35        first: AtomicU32::new(u32::MAX),
36        second: AtomicU32::new(u32::MAX),
37    };
38
39    // Handle the first 999 numbers specially as the number of digits varies.
40    for n in 1..1000 {
41        let (mut buffer, size) = format_string(&shared.prefix, n);
42        check_hash(&mut buffer, size, n, &shared);
43    }
44
45    // Use as many cores as possible to parallelize the remaining search.
46    spawn(|| {
47        #[cfg(not(feature = "simd"))]
48        worker(&shared);
49        #[cfg(feature = "simd")]
50        simd::worker(&shared);
51    });
52
53    shared
54}
55
56pub fn part1(input: &Shared) -> u32 {
57    input.first.load(Ordering::Relaxed)
58}
59
60pub fn part2(input: &Shared) -> u32 {
61    input.second.load(Ordering::Relaxed)
62}
63
64fn format_string(prefix: &str, mut n: u32) -> ([u8; 64], usize) {
65    let prefix_len = prefix.len();
66    let digits = n.max(1).ilog10() as usize + 1;
67    let size = prefix_len + digits;
68
69    let mut buffer = [0; 64];
70    buffer[..prefix_len].copy_from_slice(prefix.as_bytes());
71
72    for i in (prefix_len..size).rev() {
73        buffer[i] = b'0' + (n % 10) as u8;
74        n /= 10;
75    }
76
77    (buffer, size)
78}
79
80fn check_hash(buffer: &mut [u8], size: usize, n: u32, shared: &Shared) {
81    let [result, ..] = hash(buffer, size);
82
83    if result & 0xffffff00 == 0 {
84        shared.second.fetch_min(n, Ordering::Relaxed);
85        shared.iter.stop();
86    } else if result & 0xfffff000 == 0 {
87        shared.first.fetch_min(n, Ordering::Relaxed);
88    }
89}
90
91#[cfg(not(feature = "simd"))]
92fn worker(shared: &Shared) {
93    while let Some(offset) = shared.iter.next() {
94        let (mut buffer, size) = format_string(&shared.prefix, offset);
95
96        for n in 0..1000 {
97            // Format macro is very slow, so update digits directly
98            buffer[size - 3] = b'0' + (n / 100) as u8;
99            buffer[size - 2] = b'0' + ((n / 10) % 10) as u8;
100            buffer[size - 1] = b'0' + (n % 10) as u8;
101
102            check_hash(&mut buffer, size, offset + n, shared);
103        }
104    }
105}
106
107#[cfg(feature = "simd")]
108mod simd {
109    use super::*;
110    use crate::util::bitset::*;
111    use crate::util::md5::simd::hash_fixed;
112    use std::simd::cmp::SimdPartialEq as _;
113    use std::simd::*;
114
115    #[expect(clippy::needless_range_loop)]
116    fn check_hash_simd<const N: usize>(
117        buffers: &mut [[u8; 64]; N],
118        size: usize,
119        start: u32,
120        offset: u32,
121        shared: &Shared,
122    ) {
123        // Format macro is very slow, so update digits directly
124        for i in 0..N {
125            let n = offset + i as u32;
126            buffers[i][size - 3] = b'0' + (n / 100) as u8;
127            buffers[i][size - 2] = b'0' + ((n / 10) % 10) as u8;
128            buffers[i][size - 1] = b'0' + (n % 10) as u8;
129        }
130
131        let [result, ..] = hash_fixed(buffers, size);
132        let bitmask = (result & Simd::splat(0xfffff000)).simd_eq(Simd::splat(0)).to_bitmask();
133
134        for i in bitmask.biterator() {
135            if result[i] & 0xffffff00 == 0 {
136                shared.second.fetch_min(start + offset + i as u32, Ordering::Relaxed);
137                shared.iter.stop();
138            } else {
139                shared.first.fetch_min(start + offset + i as u32, Ordering::Relaxed);
140            }
141        }
142    }
143
144    pub(super) fn worker(shared: &Shared) {
145        while let Some(start) = shared.iter.next() {
146            let (prefix, size) = format_string(&shared.prefix, start);
147            let buffers = &mut [prefix; 32];
148
149            for offset in (0..992).step_by(32) {
150                check_hash_simd(buffers, size, start, offset, shared);
151            }
152
153            let buffers = &mut [prefix; 8];
154            check_hash_simd(buffers, size, start, 992, shared);
155        }
156    }
157}
aoc/year2015/day04.rs

aoc/year2015/
day04.rs
