Advent Of Code 2022 第六天 - 信号问题

发表于 更新于 分类于 ，

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

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

问题

给出一个字符串，让你找出第一个 n 个字符都不相同的位置。

第一部分

准备工作终于完成了；你和精灵们步行离开营地，开始向 星 果树林进发。

当你穿过茂密的树丛时，其中一个精灵给了你一个手持 设备 。他说，它有很多花哨的功能，但现在最重要的是设置 通信系统 。

然而，因为他听说你有与处理基于信号的系统的经验，他说服了其他精灵，把他们那个出故障的设备给你也无妨–你修好它肯定不会有问题。

仿佛是受到了喜剧时机的启发，该设备发出了一些五颜六色的火花。

为了能够与精灵族沟通，该设备需要 锁定他们的信号 。该信号是一系列看似随机的字符，设备一次接收一个。

为了修复通信系统，你需要在设备上添加一个子程序，检测数据流中的 开始包标记 。在精灵族使用的协议中，一个数据包的开始是由 *
四个不同的字符序列* 来表示的。

设备将向你的子程序发送一个 数据流缓冲区（你的谜题输入）；你的子程序需要识别最近收到的四个字符全部不同的第一个位置。具体来说，它需要报告从缓冲区开始到第一个这样的四个字符标记结束的字符数。

例如，假设你收到以下数据流缓冲区：

1
mjqjpqmgbljsphdztnvjfqwrcgsmlb

在收到前三个字符（mjq
）后，还没有收到足够的字符来寻找标记。第一次可能出现的标记是在收到第四个字符后，使最近的四个字符为mjqj。因为j
是重复的，这不是一个标记。

标记的第一次出现是在 第七个 字符到达之后。一旦它出现，最后收到的四个字符是jpqm，这都是不同的。在这种情况下，你的子程序应该报告值
7 ，因为在处理了7个字符后，第一个包开始标记就完成了。

这里还有几个例子：

  • bvwbjplbgvbhsrlpgdmjqwftvncz: 第一个标记于 5
  • nppdvjthqldpwncqszvftbrmjlhg: 第一个标记于 6
  • nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg: 第一个标记于 10
  • zcfzfwzzqfrljwzlrfnpqdbhtmscgvjw: 第一个标记于 11

在检测到第一个数据包开始标记之前，需要处理多少个字符？

第二部分

你的设备的通信系统正确地检测到了数据包，但仍然没有工作。看起来它还需要寻找 消息 。

一个 消息开始标记 就像一个数据包开始标记，只是它由 14个不同的字符 组成，而不是4个。

下面是上述所有例子中信息开始标记的第一个位置：

  • mjqjpqmgbljsphdztnvjfqwrcgsmlb: 第一个标记于 19
  • bvwbjplbgvbhsrlpgdmjqwftvncz: 第一个标记于 23
  • nppdvjthqldpwncqszvftbrmjlhg: 第一个标记于 23
  • nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg: 第一个标记于 29
  • zcfzfwzzqfrljwzlrfnpqdbhtmscgvjw: 第一个标记于 26

在检测到第一个数据包开始标记之前，需要处理多少个字符？

代码

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

06.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
use itertools::Itertools;

type Input = Vec<char>;

fn no_dup<T: PartialEq>(slice: &[T]) -> bool {
    for i in 1..slice.len() {
        if slice[i..].contains(&slice[i - 1]) {
            return false;
        }
    }
    true
}

fn first_marker(input: Input, windows_size: usize) -> Option<usize> {
    input
        .windows(windows_size)
        .find_position(|&x| no_dup(x))
        .map(|(pos, _)| pos + windows_size)
}

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

pub fn part_one(input: Input) -> Option<usize> {
    first_marker(input, 4)
}

pub fn part_two(input: Input) -> Option<usize> {
    first_marker(input, 14)
}

解析器

没什么东西，就是把字符串分割成字符的迭代器

第一部分

先把字符做一个 4 大小的 windows ，然后再找到这些 windows 里面第一个没有重复字符的，因为起始点是 0 还得再加上大小。

第二部分

同理，只不过大小是 14。

运行时间

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

1
2
3
4
5
Day 6
------
Parser: ✓ (16.5µs)
Part 1: 1723 (11.2µs)
Part 2: 3708 (28.4µs)