# Advent of code, day 15

Dec 15th, 2017
137
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. struct Rng {
2.     prev_val: u64,
3.     factor: u64,
4.     filter_modulus: u64,
5. }
6.
7. impl Rng {
8.     fn new(seed: u64, factor: u64, filter_modulus: u64) -> Self {
9.         Rng { prev_val: seed, factor: factor, filter_modulus: filter_modulus }
10.     }
11.
12.     fn rand(&mut self) -> u64 {
13.         const MODULUS: u64 = 2147483647;
14.         loop {
15.             let next_val = (self.prev_val * self.factor) % MODULUS;
16.             self.prev_val = next_val;
17.             if next_val % self.filter_modulus == 0 {
18.                 break;
19.             }
20.         }
21.         self.prev_val
22.     }
23. }
24.
25. fn solve(a_filter_modulus: u64,
26.          b_filter_modulus: u64,
27.          n_iterations: u64) -> u64 {
28.     const A_SEED: u64 = 512;
29.     const A_FACTOR: u64 = 16807;
30.     let mut a_rng = Rng::new(A_SEED, A_FACTOR, a_filter_modulus);
31.
32.     const B_SEED: u64 = 191;
33.     const B_FACTOR: u64 = 48271;
34.     let mut b_rng = Rng::new(B_SEED, B_FACTOR, b_filter_modulus);
35.
36.     const COLLISION_MASK: u64 = 0xffff;
37.
38.     let mut n_collisions = 0;
39.     for _ in 0..n_iterations {
40.         let a_val = a_rng.rand() & COLLISION_MASK;
41.         let b_val = b_rng.rand() & COLLISION_MASK;
42.         n_collisions += (a_val == b_val) as u64;
43.     }
44.     n_collisions
45. }
46.
47. fn main() {
48.     const PART_A_ITERATIONS: u64 = 40_000_000;
49.     let part_a = solve(1, 1, PART_A_ITERATIONS);
50.
51.     const A_FILTER_MODULUS: u64 = 4;
52.     const B_FILTER_MODULUS: u64 = 8;
53.     const PART_B_ITERATIONS: u64 = 5_000_000;
54.     let part_b = solve(A_FILTER_MODULUS, B_FILTER_MODULUS, PART_B_ITERATIONS);
55.     println!("{} {}", part_a, part_b);
56. }