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    let mut result = 0;
69
70    for &[depth, range] in input {
71        let period = 2 * (range - 1);
72        if depth % period == 0 {
73            result += depth * range;
74        }
75    }
76
77    result
78}
79
80/// Sieves possible values at each scanner stage to reduce the number of possible values.
81pub fn part2(input: &Input) -> u32 {
82    let mut lcm = 1;
83    let mut current = &mut Vec::new();
84    let mut next = &mut Vec::new();
85
86    current.push(1);
87
88    for &[depth, range] in input {
89        // Find the least common multiple of the existing lcm and the new scanner period.
90        let period = 2 * (range - 1);
91        let next_lcm = lcm.lcm(period);
92
93        // Check each multiple of the current `end` against the new scanner.
94        for extra in (0..next_lcm).step_by(lcm as usize) {
95            for &delay in current.iter() {
96                if (delay + extra + depth) % period != 0 {
97                    next.push(delay + extra);
98                }
99            }
100        }
101
102        lcm = next_lcm;
103        (current, next) = (next, current);
104        next.clear();
105    }
106
107    *current.first().unwrap()
108}
aoc/year2017/day13.rs

aoc/year2017/
day13.rs
