本文是关于 Advent Of Code 2022 的。
编程圣诞日历, 圣诞节前每天一个编程问题。
有兴趣的朋友可以在官网答题, 用自己喜欢的编程方式去收集星星⭐️。在官网答题需要登陆并下载为你单独生成的谜题输入, 每个人的都不一样。
问题
按照指示解码文件, 然后找到精灵们的位置。
第一部分
终于到了与精灵们重逢的时候了。然而, 当你试图联系他们时, 你没有得到任何答复。也许你不在范围内？
你知道他们正在前往生长星星果实的小树林, 所以如果你能找出那是哪里, 你应该能和他们会合。
幸运的是, 你的手持设备上有一个文件（你的谜题输入）, 其中包含了小树林的坐标。不幸的是, 这个文件是 加密的 –以防设备落入坏人手中。
也许你可以解密它？
当你还在营地的时候, 你无意中听到一些精灵在谈论坐标文件的加密。解密文件所涉及的主要操作被称为 混合 。
加密后的文件是一个数字的列表。为了 混合 文件, 将文件中的每个数字向前或向后移动一定数量的位置, 相当于被移动数字的值。这个列表是*圆形的, 所以将一个数字从列表的一端移到另一端, 就像两端相连一样。
例如, 在 “4, 5, 6, 1, 7, 8, 9” 这样的序列中移动 1, 1 向前移动一个位置：”4, 5, 6, 7, 1, 8, 9”。接下来移动 -2 的序列, “4, -2 , 5, 6, 7, 8, 9”, 2 向后移动两个位置, 并且从另一边回来：”4, 5, 6, 7, 8, -2, 9”。
这些数字应该 按照它们在加密文件中最初出现的顺序 移动。在混合过程中, 数字的移动不会改变数字的移动顺序。
考虑一下这个加密文件：
混合这个文件的过程如下：
1
2
3
4
5
6
7
8
| 1, 2, -3, 3, -2, 0, 4
2, 1, -3, 3, -2, 0, 4
1, -3, 2, 3, -2, 0, 4
1, 2, 3, -2, -3, 0, 4
1, 2, -2, -3, 0, 3, 4
1, 2, -3, 0, 3, 4, -2
1, 2, -3, 0, 3, 4, -2
1, 2, -3, 4, 0, 3, -2
|
然后, 通过查看数值 0 之后的第 1000 、 2000 和 3000 个数字, 必要时环绕列表, 就可以找到小树林的坐标。在上面的例子中, 0 之后的第1000个数字是 4 , 第2000个是 3 , 第3000个是 2 ；将这些数字相加产生 3 。
将你的加密文件正好混合一次。 构成小树林坐标的三个数字之和是多少？
第二部分
小树林的坐标值似乎毫无意义。当你思考精灵族加密的奥秘时, 你突然想起在营地时偷听到的解密程序的其余部分。
首先, 你需要应用 解密密钥 , 811589153。在你开始之前, 将每个数字乘以解密密钥；这将产生要混合的实际数字列表。
第二, 你需要将数字列表混合 10次 。在混合过程中, 数字被混合的顺序不会改变；数字仍然按照它们在原始的、预先混合的列表中出现的顺序移动。(所以, 如果-3在原来的数字列表中出现在第四位, 那么-3将是每一轮混合中移动的第四个数字）。
用上述同样的例子：
1
2
3
4
5
6
7
8
9
10
11
| 811589153, 1623178306, -2434767459, 2434767459, -1623178306, 0, 3246356612
0, -2434767459, 3246356612, -1623178306, 2434767459, 1623178306, 811589153
0, 2434767459, 1623178306, 3246356612, -2434767459, -1623178306, 811589153
0, 811589153, 2434767459, 3246356612, 1623178306, -1623178306, -2434767459
0, 1623178306, -2434767459, 811589153, 2434767459, 3246356612, -1623178306
0, 811589153, -1623178306, 1623178306, -2434767459, 3246356612, 2434767459
0, 811589153, -1623178306, 3246356612, -2434767459, 1623178306, 2434767459
0, -2434767459, 2434767459, 1623178306, -1623178306, 811589153, 3246356612
0, 1623178306, 3246356612, 811589153, -2434767459, 2434767459, -1623178306
0, 811589153, 1623178306, -2434767459, 3246356612, 2434767459, -1623178306
0, -2434767459, 1623178306, 3246356612, -1623178306, 2434767459, 811589153
|
小树林的坐标仍然可以用同样的方法找到。这里, 0 之后的第1000个数字是 811589153 , 第2000个是 2434767459 , 第3000个是 1623178306 ；将这些数字相加得出 1623178306 。
应用解密密钥, 将你的加密文件混合10次。 构成小树林坐标的三个数字之和是多少？
代码
完整的代码可以在 这里 找到。
20.rs1
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
| use itertools::Itertools;
use advent_of_code::treap::Treap;
type Input = Vec<i64>;
fn parse(input: &str) -> Input {
input.lines().filter_map(|n| n.parse::<i64>().ok()).collect_vec()
}
fn decrypt(input: &[i64], multi: i64, k: usize) -> Option<i64> {
let zero_idx = input.iter().position(|x| *x == 0).unwrap();
let mut rng = rand::thread_rng();
let mut trp = Treap::default();
let mut nodes = input
.iter()
.enumerate()
.map(|(i, n)| trp.insert(*n * multi, i, &mut rng))
.collect_vec();
for _ in 0..k {
for node in &mut nodes {
let (value, rank) = trp.remove(*node)?;
let new_rank = (value + rank as i64).rem_euclid(input.len() as i64 - 1);
*node = trp.insert(value, new_rank as usize, &mut rng);
}
}
let zero_rank = trp.rank(nodes[zero_idx]).unwrap();
Some(
(1..=3).map(|k| {
let rank = trp.derank((zero_rank + 1000 * k) % input.len());
trp.get(rank).unwrap()
}).sum()
)
}
pub fn part_one(input: Input) -> Option<i64> {
decrypt(&input, 1, 1)
}
pub fn part_two(input: Input) -> Option<i64> {
decrypt(&input, 811589153, 10)
}
|
解析器
每一行的数字变成一个 i64 类型的向量。
第一部分
移动的方法为去除当前的节点, 并且在节点数值加上节点原本位置对总长度取余数的地方插入节点, 就能够完成一次移动。
这里使用了 Treap 数据结构, 它是一种二叉搜索树, 同时也是一个堆。这样就能够在 O(log n) 的时间内完成插入、删除、查找等操作。
第二部分
和第一部分一样, 只是在移动的时候, 先将节点数值乘以 811589153 , 然后再进行移动十次。因为是靠余数找到节点的位置, 所以加大数量对于时间的影响不大。
运行时间
1
2
3
4
5
| Day 20
------
Parser: ✓ (129.6µs)
Part 1: 988 (8.7ms)
Part 2: 7768531372516 (61.1ms)
|