advent_of_code/year2017/
day15.rs

1use crate::input::Input;
2
3#[derive(Copy, Clone)]
4struct Generator {
5    value: u64,
6    factor: u64,
7    only_multiples_of: u64,
8}
9
10impl Iterator for Generator {
11    type Item = u64;
12
13    fn next(&mut self) -> Option<Self::Item> {
14        loop {
15            // https://www.reddit.com/r/adventofcode/comments/7jyz5x/2017_day_15_opportunities_for_optimization/drasfzr?utm_source=share&utm_medium=web2x&context=3
16            // self.value = (self.value * self.factor) % 2147483647;
17            let prod = self.value * self.factor;
18            let g = (prod & 0x7fff_ffff) + (prod >> 31);
19            self.value = if g >> 31 == 0 { g } else { g - 0x7fff_ffff };
20
21            // Speedier version of modulo here:
22            // if self.value % self.only_multiples_of == 0 {
23            if self.value & (self.only_multiples_of - 1) == 0 {
24                return Some(self.value);
25            }
26        }
27    }
28}
29
30pub fn solve(input: &Input) -> Result<u32, String> {
31    let starting_values = input
32        .text
33        .lines()
34        .enumerate()
35        .map(|(line_index, line)| {
36            let last_word = line
37                .split(' ')
38                .last()
39                .ok_or_else(|| "Empty line".to_string())?;
40            last_word.parse::<u64>().map_err(|parse_error| {
41                format!(
42                    "Line {}: Unable to parse starting value: {}",
43                    line_index + 1,
44                    parse_error
45                )
46            })
47        })
48        .collect::<Result<Vec<u64>, _>>()?;
49
50    if starting_values.len() != 2 {
51        return Err("Invalid input - should be 2 lines".to_string());
52    }
53
54    let first_generator = Generator {
55        value: starting_values[0],
56        factor: 16807,
57        only_multiples_of: input.part_values(1, 4),
58    };
59
60    let second_generator = Generator {
61        value: starting_values[1],
62        factor: 48271,
63        only_multiples_of: input.part_values(1, 8),
64    };
65
66    let matches = first_generator
67        .zip(second_generator)
68        .take(input.part_values(40_000_000, 5_000_000))
69        .filter(|(a, b)| *a as u16 == *b as u16)
70        .count();
71    Ok(matches as u32)
72}
73
74#[test]
75fn tests() {
76    use crate::input::{test_part_one, test_part_two};
77
78    let real_input = include_str!("day15_input.txt");
79    test_part_one!(real_input => 597);
80    test_part_two!(real_input => 303);
81}
advent_of_code/year2017/day15.rs

advent_of_code/year2017/
day15.rs
