aoc/year2017/
day15.rs

1//! # Dueling Generators
2//!
3//! Multithreaded approach using worker threads to generate batches of numbers for judging.
4//! Part one can be checked in parallel, but part two must be sent to a single thread as the
5//! indices must be checked in order.
6//!
7//! The sequence of numbers are [modular exponentiation](https://en.wikipedia.org/wiki/Modular_exponentiation)
8//! so we can jump to any location in the sequence, without needing to know the previous numbers.
9use crate::util::hash::*;
10use crate::util::iter::*;
11use crate::util::math::*;
12use crate::util::parse::*;
13use crate::util::thread::*;
14use std::sync::mpsc::{Receiver, Sender, channel};
15use std::thread;
16
17const MOD: usize = 0x7fffffff;
18const PART_ONE: usize = 40_000_000;
19const PART_TWO: usize = 5_000_000;
20const BLOCK: usize = 50_000;
21
22type Input = (usize, usize);
23
24/// State shared between all threads.
25pub struct Shared {
26    first: usize,
27    second: usize,
28    iter: AtomicIter,
29}
30
31/// Generated numbers from `start` to `start + BLOCK`.
32struct Block {
33    start: usize,
34    ones: usize,
35    fours: Vec<u16>,
36    eights: Vec<u16>,
37}
38
39pub fn parse(input: &str) -> Input {
40    let [first, second] = input.iter_unsigned().chunk::<2>().next().unwrap();
41    let shared = Shared { first, second, iter: AtomicIter::new(0, BLOCK as u32) };
42    let (tx, rx) = channel();
43
44    thread::scope(|scope| {
45        // Use all cores except one to generate blocks of numbers for judging.
46        for _ in 0..threads() - 1 {
47            scope.spawn(|| sender(&shared, &tx));
48        }
49        // Judge batches serially.
50        receiver(&shared, &rx)
51    })
52}
53
54pub fn part1(input: &Input) -> usize {
55    input.0
56}
57
58pub fn part2(input: &Input) -> usize {
59    input.1
60}
61
62fn sender(shared: &Shared, tx: &Sender<Block>) {
63    while let Some(start) = shared.iter.next() {
64        // Start at any point in the sequence using modular exponentiation.
65        let start = start as usize;
66        let mut first = shared.first * 16807.mod_pow(start, MOD);
67        let mut second = shared.second * 48271.mod_pow(start, MOD);
68
69        // Estimate capacity at one quarter or one eight.
70        let mut ones = 0;
71        let mut fours = Vec::with_capacity(BLOCK / 4);
72        let mut eights = Vec::with_capacity(BLOCK / 8);
73
74        // Check part one pairs immediately while queueing part two pairs.
75        for _ in 0..BLOCK {
76            first = fast_mod(first * 16807);
77            second = fast_mod(second * 48271);
78
79            let left = first as u16;
80            let right = second as u16;
81
82            if left == right {
83                ones += 1;
84            }
85            if left.is_multiple_of(4) {
86                fours.push(left);
87            }
88            if right.is_multiple_of(8) {
89                eights.push(right);
90            }
91        }
92
93        let _unused = tx.send(Block { start, ones, fours, eights });
94    }
95}
96
97fn receiver(shared: &Shared, rx: &Receiver<Block>) -> Input {
98    let mut required = 0;
99    let mut out_of_order = FastMap::new();
100
101    let mut fours = Vec::with_capacity(PART_TWO + BLOCK);
102    let mut eights = Vec::with_capacity(PART_TWO + BLOCK);
103    let mut start = 0;
104
105    let mut part_one = 0;
106    let mut part_two = 0;
107
108    while required < PART_ONE || fours.len() < PART_TWO || eights.len() < PART_TWO {
109        // Blocks could be received in any order, as there's no guarantee threads will finish
110        // processing at the same time. The `start` field of the block defines the order they
111        // must be added to the vec.
112        while let Ok(block) = rx.try_recv() {
113            out_of_order.insert(block.start, block);
114        }
115
116        while let Some(block) = out_of_order.remove(&required) {
117            required += BLOCK;
118
119            if required <= PART_ONE {
120                part_one += block.ones;
121            }
122
123            if fours.len() < PART_TWO {
124                fours.extend_from_slice(&block.fours);
125            }
126
127            if eights.len() < PART_TWO {
128                eights.extend_from_slice(&block.eights);
129            }
130
131            let end = PART_TWO.min(fours.len()).min(eights.len());
132            part_two +=
133                fours[start..end].iter().zip(&eights[start..end]).filter(|(a, b)| a == b).count();
134            start = end;
135        }
136    }
137
138    // Signal worker threads to finish.
139    shared.iter.stop();
140
141    (part_one, part_two)
142}
143
144#[inline]
145fn fast_mod(n: usize) -> usize {
146    let low = n & MOD;
147    let high = n >> 31;
148    let sum = low + high;
149    if sum < MOD { sum } else { sum - MOD }
150}
aoc/year2017/day15.rs

aoc/year2017/
day15.rs
