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::{AtomicBool, AtomicU32, Ordering};
23
24pub struct Shared {
25    prefix: String,
26    done: AtomicBool,
27    counter: AtomicU32,
28    first: AtomicU32,
29    second: AtomicU32,
30}
31
32pub fn parse(input: &str) -> Shared {
33    let shared = Shared {
34        prefix: input.trim().to_owned(),
35        done: AtomicBool::new(false),
36        counter: AtomicU32::new(1000),
37        first: AtomicU32::new(u32::MAX),
38        second: AtomicU32::new(u32::MAX),
39    };
40
41    // Handle the first 999 numbers specially as the number of digits varies.
42    for n in 1..1000 {
43        let (mut buffer, size) = format_string(&shared.prefix, n);
44        check_hash(&mut buffer, size, n, &shared);
45    }
46
47    // Use as many cores as possible to parallelize the remaining search.
48    spawn(|| {
49        #[cfg(not(feature = "simd"))]
50        worker(&shared);
51        #[cfg(feature = "simd")]
52        simd::worker(&shared);
53    });
54
55    shared
56}
57
58pub fn part1(input: &Shared) -> u32 {
59    input.first.load(Ordering::Relaxed)
60}
61
62pub fn part2(input: &Shared) -> u32 {
63    input.second.load(Ordering::Relaxed)
64}
65
66fn format_string(prefix: &str, n: u32) -> ([u8; 64], usize) {
67    let string = format!("{prefix}{n}");
68    let size = string.len();
69
70    let mut buffer = [0; 64];
71    buffer[0..size].copy_from_slice(string.as_bytes());
72
73    (buffer, size)
74}
75
76fn check_hash(buffer: &mut [u8], size: usize, n: u32, shared: &Shared) {
77    let (result, ..) = hash(buffer, size);
78
79    if result & 0xffffff00 == 0 {
80        shared.second.fetch_min(n, Ordering::Relaxed);
81        shared.done.store(true, Ordering::Relaxed);
82    } else if result & 0xfffff000 == 0 {
83        shared.first.fetch_min(n, Ordering::Relaxed);
84    }
85}
86
87#[cfg(not(feature = "simd"))]
88fn worker(shared: &Shared) {
89    while !shared.done.load(Ordering::Relaxed) {
90        let offset = shared.counter.fetch_add(1000, Ordering::Relaxed);
91        let (mut buffer, size) = format_string(&shared.prefix, offset);
92
93        for n in 0..1000 {
94            // Format macro is very slow, so update digits directly
95            buffer[size - 3] = b'0' + (n / 100) as u8;
96            buffer[size - 2] = b'0' + ((n / 10) % 10) as u8;
97            buffer[size - 1] = b'0' + (n % 10) as u8;
98
99            check_hash(&mut buffer, size, offset + n, shared);
100        }
101    }
102}
103
104#[cfg(feature = "simd")]
105mod simd {
106    use super::*;
107    use crate::util::md5::simd::hash;
108    use std::simd::{LaneCount, SupportedLaneCount};
109
110    #[expect(clippy::needless_range_loop)]
111    fn check_hash_simd<const N: usize>(
112        buffers: &mut [[u8; 64]],
113        size: usize,
114        start: u32,
115        offset: u32,
116        shared: &Shared,
117    ) where
118        LaneCount<N>: SupportedLaneCount,
119    {
120        // Format macro is very slow, so update digits directly
121        for i in 0..N {
122            let n = offset + i as u32;
123            buffers[i][size - 3] = b'0' + (n / 100) as u8;
124            buffers[i][size - 2] = b'0' + ((n / 10) % 10) as u8;
125            buffers[i][size - 1] = b'0' + (n % 10) as u8;
126        }
127
128        let (result, ..) = hash::<N>(buffers, size);
129
130        for i in 0..N {
131            if result[i] & 0xffffff00 == 0 {
132                shared.second.fetch_min(start + offset + i as u32, Ordering::Relaxed);
133                shared.done.store(true, Ordering::Relaxed);
134            } else if result[i] & 0xfffff000 == 0 {
135                shared.first.fetch_min(start + offset + i as u32, Ordering::Relaxed);
136            }
137        }
138    }
139
140    pub(super) fn worker(shared: &Shared) {
141        while !shared.done.load(Ordering::Relaxed) {
142            let start = shared.counter.fetch_add(1000, Ordering::Relaxed);
143            let (prefix, size) = format_string(&shared.prefix, start);
144            let mut buffers = [prefix; 32];
145
146            for offset in (0..992).step_by(32) {
147                check_hash_simd::<32>(&mut buffers, size, start, offset, shared);
148            }
149
150            check_hash_simd::<8>(&mut buffers, size, start, 992, shared);
151        }
152    }
153}
aoc/year2015/day04.rs

aoc/year2015/
day04.rs
