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