year2017/
day13.rs

1use std::collections::BTreeMap;
2use utils::number;
3use utils::prelude::*;
4
5/// Finding the gap in the firewall.
6///
7/// Similar to [2016 day 15](../year2016/struct.Day15.html), but instead of a system of linear
8/// simultaneous congruences, it is a system of simultaneous modular inequalities.
9#[derive(Clone, Debug)]
10pub struct Day13 {
11    layers: Vec<(u32, u32)>,
12}
13
14impl Day13 {
15    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
16        Ok(Self {
17            layers: parser::u32()
18                .with_suffix(": ")
19                .then(parser::u32())
20                .parse_lines(input)?,
21        })
22    }
23
24    #[must_use]
25    pub fn part1(&self) -> u32 {
26        self.layers
27            .iter()
28            .map(|&(depth, range)| {
29                let period = (range - 1) * 2;
30                if depth % period == 0 {
31                    depth * range
32                } else {
33                    0
34                }
35            })
36            .sum()
37    }
38
39    #[must_use]
40    pub fn part2(&self) -> u32 {
41        // Each key represents a modulus and maps to a list of values where
42        // delay % modulus can't equal the value
43        let mut constraints = BTreeMap::new();
44        for &(depth, range) in &self.layers {
45            let modulus = (range as i32 - 1) * 2;
46            let disallowed_value = (-(depth as i32)).rem_euclid(modulus);
47
48            constraints
49                .entry(modulus)
50                .or_insert_with(Vec::new)
51                .push(disallowed_value);
52        }
53
54        // Find all the possible delays % lcm which meet the above constraints
55        let mut lcm = 1;
56        let mut possible_delays = vec![0];
57        for (modulus, disallowed_values) in constraints {
58            let new_lcm = number::lcm(modulus, lcm);
59            possible_delays = possible_delays
60                .into_iter()
61                .flat_map(|delay| {
62                    (delay..new_lcm)
63                        .step_by(lcm as usize)
64                        .filter(|&i| !disallowed_values.contains(&(i % modulus)))
65                })
66                .collect();
67            lcm = new_lcm;
68        }
69
70        *possible_delays.iter().min().unwrap() as u32
71    }
72}
73
74examples!(Day13 -> (u32, u32) [
75    {input: "0: 3\n1: 2\n4: 4\n6: 4", part1: 24, part2: 10},
76]);
year2017/day13.rs

year2017/
day13.rs
