-
Notifications
You must be signed in to change notification settings - Fork 4
/
day01.rs
74 lines (63 loc) · 2.81 KB
/
day01.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
//! # Chronal Calibration
//!
//! The simplest approach to part two is to store previously seen numbers in a `HashSet` then
//! stop once a duplicate is found. However this approach requires scanning the input of ~1,000
//! numbers multiple times, around 150 times for my input.
//!
//! A much faster `O(nlogn)` approach relies on the fact that each frequency increases by the same
//! amount (the sum of all deltas) each time the list of numbers is processed. For example:
//!
//! ```none
//! Deltas: +1, -2, +3, +1 =>
//! 0 1 -1 2
//! 3 4 2 5
//! ```
//!
//! Two frequencies that are a multiple of the sum will eventually repeat. First we group each
//! frequencies by its remainder modulo the sum, using `rem_euclid` to handle negative frequencies
//! correctly, Then we sort, first by the remainder to group frequencies that can repeat together,
//! then by the frequency increasing in order to help find the smallest gap between similar
//! frequencies, then lastly by index as this is needed in the next step.
//!
//! For the example this produces `[(0, 0, 0), (1, 1, 1), (2, -1, 2), (2, 2, 3)]`. Then we use
//! a sliding windows of size two to compare each pair of adjacent canditates, considering only
//! candidates with the same remainder. For each valid pair we then produce a tuple of
//! `(frequency gap, index, frequency)`.
//!
//! Finally we sort the tuples in ascending order, first by smallest frequency gap, breaking any
//! ties using the index to find frequencies that appear earlier in the list. The first tuple
//! in the list gives the result, in the example this is `[(3, 2, 2)]`.
use crate::util::parse::*;
pub fn parse(input: &str) -> Vec<i32> {
input.iter_signed().collect()
}
pub fn part1(input: &[i32]) -> i32 {
input.iter().sum()
}
pub fn part2(input: &[i32]) -> i32 {
// The frequencies increase by this amount each pass through the list of deltas.
let total: i32 = input.iter().sum();
// Calculate tuples of `(frequency gap, index, frequency)` then sort to group frequencies that
// can collide together.
let mut frequency: i32 = 0;
let mut seen = Vec::with_capacity(input.len());
for n in input {
seen.push((frequency.rem_euclid(total), frequency, seen.len()));
frequency += n;
}
seen.sort_unstable();
// Compare each adjacent pair of tuples to find candidates, then sort by smallest gap first,
// tie breaking with index if needed.
let mut pairs = Vec::new();
for window in seen.windows(2) {
let (remainder0, freq0, index0) = window[0];
let (remainder1, freq1, _) = window[1];
if remainder0 == remainder1 {
pairs.push((freq1 - freq0, index0, freq1));
}
}
pairs.sort_unstable();
// Result is the frequency of the first tuple.
let (_, _, freq) = pairs[0];
freq
}