Advertisement
krzysz00

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. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement