year2017/
day15.rs

1use std::collections::BTreeMap;
2use std::sync::atomic::{AtomicU32, Ordering};
3use std::sync::Mutex;
4use utils::multithreading;
5use utils::number::mod_pow;
6use utils::prelude::*;
7
8/// Comparing numbers from two simple random number generators.
9///
10/// Uses a pool of worker threads to calculate batches of the random numbers.
11#[derive(Clone, Debug)]
12pub struct Day15 {
13    batches: BTreeMap<u32, BatchResults>,
14}
15
16#[derive(Clone, Debug)]
17struct BatchResults {
18    part1_matches: u32,
19    part2_a_values: Vec<u16>,
20    part2_b_values: Vec<u16>,
21}
22
23const FACTOR_A: u64 = 16807;
24const FACTOR_B: u64 = 48271;
25const MODULUS: u64 = 2147483647;
26
27const PART1_PAIRS: u32 = 40_000_000;
28const PART2_PAIRS: u32 = 5_000_000;
29const BATCH_SIZE: u32 = 250_000; // BATCH_SIZE must evenly divide PART1_PAIRS
30
31impl Day15 {
32    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
33        let (start_a, start_b) = parser::u32()
34            .with_prefix("Generator A starts with ")
35            .with_suffix(parser::eol())
36            .then(parser::u32().with_prefix("Generator B starts with "))
37            .parse_complete(input)?;
38
39        let mutex = Mutex::default();
40        let next_index = AtomicU32::new(0);
41        let part2_a_count = AtomicU32::new(0);
42        let part2_b_count = AtomicU32::new(0);
43
44        multithreading::worker_pool(|| {
45            Self::values_worker(
46                start_a as u64,
47                start_b as u64,
48                &mutex,
49                &next_index,
50                &part2_a_count,
51                &part2_b_count,
52            );
53        });
54
55        Ok(Self {
56            batches: mutex.into_inner().unwrap(),
57        })
58    }
59
60    #[must_use]
61    pub fn part1(&self) -> u32 {
62        self.batches
63            .range(0..PART1_PAIRS)
64            .map(|(_, BatchResults { part1_matches, .. })| part1_matches)
65            .sum()
66    }
67
68    #[must_use]
69    pub fn part2(&self) -> u32 {
70        let a_values = self
71            .batches
72            .values()
73            .flat_map(|BatchResults { part2_a_values, .. }| part2_a_values.iter().copied());
74        let b_values = self
75            .batches
76            .values()
77            .flat_map(|BatchResults { part2_b_values, .. }| part2_b_values.iter().copied());
78
79        a_values
80            .zip(b_values)
81            .take(PART2_PAIRS as usize)
82            .filter(|&(a, b)| a == b)
83            .count() as u32
84    }
85
86    fn values_worker(
87        start_a: u64,
88        start_b: u64,
89        mutex: &Mutex<BTreeMap<u32, BatchResults>>,
90        next_index: &AtomicU32,
91        part2_a_count: &AtomicU32,
92        part2_b_count: &AtomicU32,
93    ) {
94        loop {
95            let start_index = next_index.fetch_add(BATCH_SIZE, Ordering::AcqRel);
96            let part2_a_finished = part2_a_count.load(Ordering::Acquire) >= PART2_PAIRS;
97            let part2_b_finished = part2_b_count.load(Ordering::Acquire) >= PART2_PAIRS;
98            if start_index >= PART1_PAIRS && part2_a_finished && part2_b_finished {
99                break;
100            }
101
102            let mut part1_matches = 0;
103            let mut part2_a_values = Vec::with_capacity(if part2_a_finished { 0 } else { 65536 });
104            let mut part2_b_values = Vec::with_capacity(if part2_b_finished { 0 } else { 32768 });
105
106            let mut a = start_a * mod_pow(FACTOR_A, start_index as u64, MODULUS);
107            let mut b = start_b * mod_pow(FACTOR_B, start_index as u64, MODULUS);
108            for _ in 0..BATCH_SIZE {
109                a = (a * FACTOR_A) % MODULUS;
110                b = (b * FACTOR_B) % MODULUS;
111
112                if a as u16 == b as u16 {
113                    part1_matches += 1;
114                }
115                if !part2_a_finished && a % 4 == 0 {
116                    part2_a_values.push(a as u16);
117                }
118                if !part2_b_finished && b % 8 == 0 {
119                    part2_b_values.push(b as u16);
120                }
121            }
122
123            part2_a_count.fetch_add(part2_a_values.len() as u32, Ordering::AcqRel);
124            part2_b_count.fetch_add(part2_b_values.len() as u32, Ordering::AcqRel);
125
126            let mut batches_guard = mutex.lock().unwrap();
127            batches_guard.insert(
128                start_index,
129                BatchResults {
130                    part1_matches,
131                    part2_a_values,
132                    part2_b_values,
133                },
134            );
135        }
136    }
137}
138
139examples!(Day15 -> (u32, u32) [
140    {input: "Generator A starts with 65\nGenerator B starts with 8921", part1: 588, part2: 309},
141]);
year2017/day15.rs

year2017/
day15.rs
