1use 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
24pub struct Shared {
26 first: usize,
27 second: usize,
28 iter: AtomicIter,
29}
30
31struct 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 for _ in 0..threads() - 1 {
47 scope.spawn(|| sender(&shared, &tx));
48 }
49 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 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 let mut ones = 0;
71 let mut fours = Vec::with_capacity(BLOCK / 4);
72 let mut eights = Vec::with_capacity(BLOCK / 8);
73
74 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 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 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}