aoc/year2022/
day20.rs

1//! # Grove Positioning System
2//!
3//! We store the numbers in a triple nested `vec` of `vec` of `vec`. The initial size of each
4//! vector is ∛5000 ~= 17, so that numbers are spread as evenly as possible.
5//!
6//! Numbes are stored in the leaf `vec`s. This greatly reduces the time to insert, remove and find
7//! numbers, compared to storing all numbers in a single flat `vec`. Some further optimizations:
8//! * The first and second level indices of a number change only when it moves, so these can be
9//!   stored in a lookup array for fast access.
10//! * The size of each first level `vec` is the the sum of the second level `vec`s contained
11//!   inside. This is stored in the `skip` array to prevent recomputing on each move.
12//!
13//! This implementation is both faster and simpler than the previous version (preserved in the
14//! commit history) that used an [order statistic tree](https://en.wikipedia.org/wiki/Order_statistic_tree),
15//! although perhaps adding [balancing rotations](https://en.wikipedia.org/wiki/Tree_rotation)
16//! to the tree would make it faster.
17use crate::util::parse::*;
18
19pub fn parse(input: &str) -> Vec<i64> {
20    input.iter_signed().collect()
21}
22
23pub fn part1(input: &[i64]) -> i64 {
24    decrypt(input, 1, 1)
25}
26
27pub fn part2(input: &[i64]) -> i64 {
28    decrypt(input, 811589153, 10)
29}
30
31fn decrypt(input: &[i64], key: i64, rounds: usize) -> i64 {
32    // Important nuance, size is one less because we don't consider the moving number.
33    let size = input.len() - 1;
34    // Another nuance, input contain duplicate numbers, so use index to refer to each number uniquely.
35    let indices: Vec<_> = (0..input.len()).collect();
36    // Pre-process the numbers, coverting any negative indices to positive indices that will wrap.
37    // For example, -1 becomes 4998.
38    let numbers: Vec<_> =
39        input.iter().map(|n| (n * key).rem_euclid(size as i64) as usize).collect();
40
41    // Store first and second level indices.
42    let mut lookup = Vec::new();
43    // Triple nested vec of numbers.
44    let mut mixed = Vec::new();
45    // Size of each first level element for convenience.
46    let mut skip = Vec::new();
47
48    // Break 5000 numbers into roughly equals chunks at each level. 289 = 17 * 17.
49    for first in indices.chunks(289) {
50        let mut outer = Vec::new();
51
52        for second in first.chunks(17) {
53            // Initial first and second level indices.
54            (0..second.len()).for_each(|_| lookup.push((mixed.len(), outer.len())));
55
56            // Leave some extra room, as mixing won't balance evenly.
57            let mut inner = Vec::with_capacity(100);
58            inner.extend_from_slice(second);
59
60            outer.push(inner);
61        }
62
63        mixed.push(outer);
64        skip.push(first.len());
65    }
66
67    for _ in 0..rounds {
68        'mix: for index in 0..input.len() {
69            // Quickly find the leaf vector storing the number.
70            let number = numbers[index];
71            let (first, second) = lookup[index];
72            // Third level changes as other numbers are added and removed,
73            // so needs to be checked each time.
74            let third = mixed[first][second].iter().position(|&i| i == index).unwrap();
75
76            // Find the offset of the number by adding the size of all previous `vec`s.
77            let position = third
78                + skip[0..first].iter().sum::<usize>()
79                + mixed[first][0..second].iter().map(Vec::len).sum::<usize>();
80            // Update our position, wrapping around if necessary.
81            let mut next = (position + number) % size;
82
83            // Remove number from current leaf vector, also updating the first level size.
84            mixed[first][second].remove(third);
85            skip[first] -= 1;
86
87            // Find our new destination, by checking `vec`s in order until the total elements
88            // are greater than our new index.
89            for (first, outer) in mixed.iter_mut().enumerate() {
90                if next > skip[first] {
91                    next -= skip[first];
92                } else {
93                    for (second, inner) in outer.iter_mut().enumerate() {
94                        if next > inner.len() {
95                            next -= inner.len();
96                        } else {
97                            // Insert number into its new home.
98                            inner.insert(next, index);
99                            skip[first] += 1;
100                            lookup[index] = (first, second);
101                            continue 'mix;
102                        }
103                    }
104                }
105            }
106        }
107    }
108
109    let indices: Vec<_> = mixed.into_iter().flatten().flatten().collect();
110    let zeroth = indices.iter().position(|&i| input[i] == 0).unwrap();
111
112    [1000, 2000, 3000]
113        .iter()
114        .map(|offset| (zeroth + offset) % indices.len())
115        .map(|index| input[indices[index]] * key)
116        .sum()
117}
aoc/year2022/day20.rs

aoc/year2022/
day20.rs
