Advent Of Code 2022 第三天 - 背包重组

发表于 更新于 分类于 ，

本文是关于 Advent Of Code 2022 的。
编程圣诞日历，圣诞节前每天一个编程问题。

有兴趣的朋友可以在官网答题，用自己喜欢的编程方式去收集星星⭐️。在官网答题需要登陆并下载为你单独生成的谜题输入，每个人的都不一样。

问题

问题是对字符串进行处理，第一部分找出每一个字符串前半部分和后半部分唯一不同的字符。

第二部分将每三个字符串组成一组，找出一组中唯一的字符。

第一部分

一个精灵的重要工作是把所有的背包
装上丛林之旅的物资。不幸的是，那个精灵没有完全按照包装说明来做，所以现在有一些物品需要重新安排。

每个背包都有两个 大格 。所有特定类型的物品都要准确地放入这两个隔间中的一个。每个背包正好有一种物品类型做包装的精灵没有遵循这个规则。

精灵们已经列出了目前每个背包中所有物品的清单（你的谜题输入），但是他们需要你帮助他们找出错误。每种物品类型都由一个小写或大写字母标识（也就是说，a
和 A 是指不同类型的物品）。

每个背包的物品清单都以字符的形式出现在一行中。一个给定的背包在其两个隔间中总是有相同数量的物品，因此前一半的字符代表第一隔间的物品，而后一半的字符代表第二隔间的物品。

例如，假设你有以下六个背包的内容清单：

1
2
3
4
5
6
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw
  • 第一个背包包含物品vJrwpWtwJgWrhcsFMMfFFhFp，这意味着其第一个隔间包含物品vJrwpWtwJgWr
    ，而第二个隔间包含物品hcsFMMfFFhFp。唯一出现在两个隔间的物品类型是小写的 p 。
  • 第二个背包的隔间包含jqHRNqRjqzjGDLGL和rsFMfFZSrLrFZsSL。这两个隔间中出现的唯一物品类型是大写的 L 。
  • 第三个背包的隔间包含PmmdzqPrV和vPwwTWBwg；唯一常见的物品类型是大写字母 P 。
  • 第四个背包的隔间只共享物品类型 v 。
  • 第五个背包的隔间只共享物品类型 t 。
  • 第六个背包的隔间只共享物品类型 s 。

为了帮助重新安排物品的优先次序，每个物品类型都可以转换为 优先级 。

  • 小写的物品类型a到z有1到26的优先级。
  • 大写的项目类型A到Z有27到52的优先级。

在上面的例子中，出现在每个背包的两个隔间里的物品类型的优先级是16（p），38（L），42（P），22（v），20（t），和19（s）；这些的总和是
157 。

找出出现在每个背包的两个隔间里的物品类型。这些物品类型的优先权之和是多少？

第二部分

当你确认完放错地方的物品时，精灵们带着另一个问题来找你。

为了安全起见，精灵们被分成了三个小组。每个精灵都带着一个徽章，以识别他们的小组。为了提高效率，在每组三个精灵中，徽章是所有三个精灵
唯一携带的物品类型 。也就是说，如果一个小组的徽章是 B 型物品，那么所有三个精灵都会在他们背包的某个地方有 B
型物品，而最多有两个精灵会携带其他类型的物品。

问题是有人忘记在徽章上贴上今年更新的贴纸。所有的徽章都需要从背包里拉出来，以便贴上新的贴纸。

此外，没有人写下哪个物品类型对应于每个组的徽章。要想知道哪种物品类型是正确的，唯一的办法就是找到每组三个精灵之间 *
共通的一种物品类型* 。

你列表中的每一组三行都对应着一个组，但每个组可以有不同的徽章项目类型。所以，在上面的例子中，第一组的背包就是前三行。

1
2
3
4
vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg

而第二组的背包是接下来的三行。

1
2
3
4
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw

在第一组中，所有三个背包中出现的唯一物品类型是小写的r；这一定是他们的徽章。在第二组中，他们的徽章物品类型必须是Z。

仍然必须找到这些物品的优先次序，以组织贴纸的粘贴工作：在这里，第一组的优先次序是18（r），第二组的优先次序是52（Z）。这些的总和是
70 。

找到与每个三精灵组的徽章相对应的物品类型。这些物品类型的优先权之和是多少？

代码

完整的代码可以在 这里 找到。

03.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
type Input<'a> = Vec<&'a str>;

fn parse(input: &str) -> Input {
    input.lines().collect()
}

fn priority_func(input: u8) -> u8 {
    input % 32 + (26 * (input <= 90) as u8)
}

pub fn part_one(input: Input) -> Option<u32> {
    Some(
        input
            .iter()
            .filter_map(|&s| {
                let (a, b) = s.split_at(s.len() / 2);
                a.as_bytes()
                    .iter()
                    .find(|byte| b.as_bytes().contains(byte))
                    .map(|&byte| priority_func(byte) as u32)
            })
            .sum()
    )
}

pub fn part_two(input: Input) -> Option<u32> {
    Some(
        input
            .chunks(3)
            .filter_map(|chunk| {
                let mut k = chunk.iter();
                let a = k.next()?.as_bytes();
                let b = k.next()?.as_bytes();
                let c = k.next()?.as_bytes();

                a.iter()
                    .find(|byte| b.contains(byte) && c.contains(byte))
                    .map(|&byte| priority_func(byte) as u32)
            }).sum()
    )
}

解析器

分行处理。

第一部分

对每一行进行处理，将字符串对半切，找出前部分有的后部分也有的字符。

然后放入计算 priority (输出) 的函数内。这个问题要求 priority 是 a-z, A-Z 分别为 1-26 和 27-52。
因为大小写的 ASCII 都是从 Mod 32 开始的，所以可以以此找到偏移，而小于检查是否大写，如果是就是加上 26 。

第二部分

同理，只不过处理的是先 chunk(3) 的字符串。

运行时间

所有时间由我这垃圾笔记本电脑进行(不科学的)测试，均以 --release 启动。

1
2
3
4
5
Day 3
------
Parser: ✓ (17.2µs)
Part 1: 8202 (21.9µs)
Part 2: 2864 (26.6µs)