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

aoc/year2015/
day04.rs
