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
}