Expand description
§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:
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)].