aoc/year2017/
day13.rs

1//! # Packet Scanners
2//!
3//! This problem is similar to [`Year 2016 Day 15`]. However the key difference is that we need
4//! to *avoid* the scanners, so the [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem)
5//! is not applicable.
6//!
7//! Part one checks that we can calculate the period for each scanner which is `2 * (range - 1)`.
8//! For example a scanner with range 3 will be at the top position at time 0, 4, 8 and so on.
9//!
10//! To avoid a brute force approach for part two we sieve possible values for each scanner
11//! sorted in ascending order of period. To combine the previous sieved values with the next
12//! scanner, we find the [least common multiple](https://en.wikipedia.org/wiki/Least_common_multiple)
13//! of their ranges. Then we "stretch" the sieved values to cover the new range, by adding
14//! multiples of the factor between the previous range and the new lcm. Finally any values
15//! that would collide with the new scanner are filtered out.
16//!
17//! Using the sample data:
18//!
19//! ```none
20//!    0: 3       1  2
21//!    1: 2  =>   0  4
22//!    4: 4       4  6
23//!    6: 4       6  6
24//! ```
25//!
26//! Starting value is `[1]`. First scanner:
27//!
28//! * Lcm of 1 and 2 => 2
29//! * Stretch `[1] => [1+0 1+1] => [1 2]`
30//! * Filter `[1 2] => [2]`
31//!
32//! Second scanner:
33//!
34//! * Lcm of 2 and 4 => 4
35//! * Stretch `[2] => [2+0 2+2] => [2 4]`
36//! * Filter `[2 4] => [2]`
37//!
38//! Third scanner:
39//!
40//! * Lcm of 4 and 6 => 12
41//! * Stretch `[2] => [2+0 2+4 2+8] => [2 6 10]`
42//! * Filter `[2 6 10] => [6 10]`
43//!
44//! Fourth scanner:
45//!
46//! * Lcm of 12 and 6 => 12
47//! * Stretch `[6 10] => [6+0 10+0] => [6 10]`
48//! * Filter `[6 10] => [10]`
49//!
50//! The lowest remaining value is our answer `10`.
51//!
52//! [`Year 2016 Day 15`]: crate::year2016::day15
53use crate::util::iter::*;
54use crate::util::math::*;
55use crate::util::parse::*;
56
57type Input = Vec<[u32; 2]>;
58
59/// Sorts scanners in ascending order of range.
60pub fn parse(input: &str) -> Input {
61    let mut scanners: Vec<_> = input.iter_unsigned().chunk::<2>().collect();
62    scanners.sort_unstable_by_key(|s| s[1]);
63    scanners
64}
65
66/// Leaving at time zero the packet will encounter each scanner at time `depth`.
67pub fn part1(input: &Input) -> u32 {
68    input
69        .iter()
70        .filter_map(|&[depth, range]| {
71            let period = 2 * (range - 1);
72            depth.is_multiple_of(period).then_some(depth * range)
73        })
74        .sum()
75}
76
77/// Sieves possible values at each scanner stage to reduce the number of possible values.
78pub fn part2(input: &Input) -> u32 {
79    let mut lcm = 1;
80    let mut current = &mut Vec::new();
81    let mut next = &mut Vec::new();
82
83    current.push(1);
84
85    for &[depth, range] in input {
86        // Find the least common multiple of the existing lcm and the new scanner period.
87        let period = 2 * (range - 1);
88        let next_lcm = lcm.lcm(period);
89
90        // Check each multiple of the current `end` against the new scanner.
91        for extra in (0..next_lcm).step_by(lcm as usize) {
92            for &delay in current.iter() {
93                if !(delay + extra + depth).is_multiple_of(period) {
94                    next.push(delay + extra);
95                }
96            }
97        }
98
99        lcm = next_lcm;
100        (current, next) = (next, current);
101        next.clear();
102    }
103
104    *current.first().unwrap()
105}
aoc/year2017/day13.rs

aoc/year2017/
day13.rs
