Advent Of Code 2022 第十三天 - 求救信号

发表于 更新于 分类于 ，

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

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

问题

对动态类型列表进行解析和处理。

第一部分

你爬上山头，再次尝试与精灵们联系。然而，你却收到了一个你意想不到的信号：一个 求救信号 。

你的手持设备肯定还是工作不正常；求救信号的数据包被乱序解码了。你需要对收到的数据包列表（你的谜题输入）重新排序，以解码该信息。

你的列表由成对的数据包组成；成对的数据包之间有一个空行。你需要确定 有多少对数据包的顺序是正确的。

lines
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[1,1,3,1,1]
[1,1,5,1,1]

[[1],[2,3,4]]
[[1],4]

[9]
[[8,7,6]]

[[4,4],4,4]
[[4,4],4,4,4]

[7,7,7,7]
[7,7,7]

[]
[3]

[[[]]]
[[]]

[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9]

包数据由列表和整数组成。每个列表以[开头，以]结尾，并包含零个或多个逗号分隔的值（整数或其他列表）。每个数据包总是一个列表，并出现在自己的行中。

当比较两个值时:

  • 如果 两个值都是整数 ，那么 低的整数 应该排在前面。如果左边的整数比右边的整数低，则输入的顺序是正确的。如果左边的整数比右边的整数高，输入的顺序就不对了。否则，输入是同一个整数；继续检查输入的下一个部分。
  • 如果 两个值都是列表 ，比较每个列表的第一个值，然后是第二个值，依次类推。如果左边的列表先用完了项目，那么输入的顺序是正确的。如果右边的列表中的项目先用完，则输入的顺序不对。如果列表的长度相同，并且没有比较来决定顺序，继续检查输入的下一部分。
  • 如果 正好有一个值是整数 ，就把这个整数转换成一个列表，其中包含这个整数作为它的唯一值，然后重试比较。例如，如果比较[0,0,0]和2，将右边的值转换为[2]（一个包含2的列表）；然后改用比较[0,0,0]和[2]的方法找到结果。

使用这些规则，你可以确定例子中的哪些对的顺序是正确的。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
== Pair 1 ==
- Compare [1,1,3,1,1] vs [1,1,5,1,1]
  - Compare 1 vs 1
  - Compare 1 vs 1
  - Compare 3 vs 5
    - Left side is smaller, so inputs are in the right order

== Pair 2 ==
- Compare [[1],[2,3,4]] vs [[1],4]
  - Compare [1] vs [1]
    - Compare 1 vs 1
  - Compare [2,3,4] vs 4
    - Mixed types; convert right to [4] and retry comparison
    - Compare [2,3,4] vs [4]
      - Compare 2 vs 4
        - Left side is smaller, so inputs are in the right order

== Pair 3 ==
- Compare [9] vs [[8,7,6]]
  - Compare 9 vs [8,7,6]
    - Mixed types; convert left to [9] and retry comparison
    - Compare [9] vs [8,7,6]
      - Compare 9 vs 8
        - Right side is smaller, so inputs are not in the right order

== Pair 4 ==
- Compare [[4,4],4,4] vs [[4,4],4,4,4]
  - Compare [4,4] vs [4,4]
    - Compare 4 vs 4
    - Compare 4 vs 4
  - Compare 4 vs 4
  - Compare 4 vs 4
  - Left side ran out of items, so inputs are in the right order

== Pair 5 ==
- Compare [7,7,7,7] vs [7,7,7]
  - Compare 7 vs 7
  - Compare 7 vs 7
  - Compare 7 vs 7
  - Right side ran out of items, so inputs are not in the right order

== Pair 6 ==
- Compare [] vs [3]
  - Left side ran out of items, so inputs are in the right order

== Pair 7 ==
- Compare [[[]]] vs [[]]
  - Compare [[]] vs []
    - Right side ran out of items, so inputs are not in the right order

== Pair 8 ==
- Compare [1,[2,[3,[4,[5,6,7]]]],8,9] vs [1,[2,[3,[4,[5,6,0]]]],8,9]
  - Compare 1 vs 1
  - Compare [2,[3,[4,[5,6,7]]]] vs [2,[3,[4,[5,6,0]]]]
    - Compare 2 vs 2
    - Compare [3,[4,[5,6,7]]] vs [3,[4,[5,6,0]]]
      - Compare 3 vs 3
      - Compare [4,[5,6,7]] vs [4,[5,6,0]]
        - Compare 4 vs 4
        - Compare [5,6,7] vs [5,6,0]
          - Compare 5 vs 5
          - Compare 6 vs 6
          - Compare 7 vs 0
            - Right side is smaller, so inputs are not in the right order

已经 在正确顺序中 的一对的索引是多少？(第一对的索引是1，第二对的索引是2，以此类推。)在上面的例子中，正确顺序的一对是1，2，4和6；这些索引的总和是 13 。

确定哪些数据包对已经处于正确的顺序。 这些数据对的索引之和是多少？

第二部分

现在，你只需要把 所有 的数据包按正确的顺序排列。不考虑你的接收数据包列表中的空白行。

遇险信号协议还要求你包括两个额外的 分割器 数据包。

lines
1
2
[[2]]
[[6]]

使用与之前相同的规则，将所有数据包(在你的接收数据包列表中的数据包以及两个分隔数据包)，整理成正确的顺序。

在上面的例子中，将数据包按正确顺序排列的结果是。

lines
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[]
[[]]
[[[]]]
[1,1,3,1,1]
[1,1,5,1,1]
[[1],[2,3,4]]
[1,[2,[3,[4,[5,6,0]]]],8,9]
[1,[2,[3,[4,[5,6,7]]]],8,9]
[[1],4]
[[2]]
[3]
[[4,4],4,4]
[[4,4],4,4,4]
[[6]]
[7,7,7]
[7,7,7,7]
[[8,7,6]]
[9]

之后，找到分割器数据包。为了找到这个求救信号的 解码器密钥 ，你需要确定两个分割器数据包的索引，然后将它们相乘。(第一个数据包的索引是1，第二个数据包的索引是2，以此类推。)在这个例子中，分割器数据包是第 10 个和第 14 个，因此解码器密钥是 140 。

将所有的数据包整理成正确的顺序。 求救信号的解码器密钥是什么？

代码

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

13.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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
use std::cmp::Ordering;
use std::fmt::Debug;

#[derive(PartialEq, Clone)]
pub enum Packet {
    Number(u32),
    Array(Vec<Packet>),
}

type Input = Vec<Packet>;

impl Packet {
    fn parse(input: &str) -> Option<Packet> {
        let mut packet = Vec::new();
        let mut chars = input.chars();
        let mut current = chars.next()?;
        let mut is_array = false;
        if current == '[' {
            is_array = true;
            current = chars.next()?;
        }

        while current != ']' {
            if current == ',' {
                current = chars.next()?;
            }

            if current.is_digit(10) {
                let mut number = String::new();
                while current.is_digit(10) {
                    number.push(current);
                    current = chars.next()?;
                }
                packet.push(Packet::Number(number.parse().unwrap()));
            }

            if current == '[' {
                let mut array = String::new();
                let mut depth = 1;
                while depth > 0 {
                    array.push(current);
                    current = chars.next()?;
                    if current == '[' {
                        depth += 1;
                    }
                    if current == ']' {
                        depth -= 1;
                    }
                }
                array.push(current);
                packet.push(Packet::parse(&array)?);
                current = chars.next()?;
            }
        }

        if is_array {
            Some(Packet::Array(packet))
        } else {
            packet.pop()
        }
    }

    fn right_order(packet_a: &Packet, packet_b: &Packet) -> Option<bool> {
        match (packet_a, packet_b) {
            (Packet::Number(a), Packet::Number(b)) => {
                if a == b { return None }
                Some(a < b)
            },
            (Packet::Array(a), Packet::Array(b)) => {
                let mut left = a.iter();
                let mut right = b.iter();

                loop {
                    match (left.next(), right.next()) {
                        (None, None) => return None,
                        (None, Some(_)) => return Some(true),
                        (Some(_), None) => return Some(false),
                        (Some(a), Some(b)) => {
                            match Packet::right_order(a, b) {
                                None => continue,
                                k => return k,
                            }
                        }
                    }
                }
            }
            (Packet::Number(a), Packet::Array(_)) => {
                let a = Packet::Array(vec![Packet::Number(*a)]);
                Packet::right_order(&a, packet_b)
            }
            (Packet::Array(_), Packet::Number(b)) => {
                let b = Packet::Array(vec![Packet::Number(*b)]);
                Packet::right_order(packet_a, &b)
            }
        }
    }
}

impl Debug for Packet {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Packet::Number(n) => write!(f, "{}", n),
            Packet::Array(a) => {
                write!(f, "[")?;
                for (i, p) in a.iter().enumerate() {
                    if i > 0 {
                        write!(f, ", ")?;
                    }
                    write!(f, "{:?}", p)?;
                }
                write!(f, "]")
            }
        }
    }
}

impl PartialOrd for Packet {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        match Packet::right_order(self, other) {
            None => None,
            Some(true) => Some(Ordering::Less),
            Some(false) => Some(Ordering::Greater),
        }
    }
}

impl Eq for Packet {}

impl Ord for Packet {
    fn cmp(&self, other: &Self) -> Ordering {
        match Packet::right_order(self, other) {
            None => Ordering::Equal,
            Some(true) => Ordering::Less,
            Some(false) => Ordering::Greater,
        }
    }
}

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

pub fn part_one(input: Input) -> Option<usize> {
    Some(
        input
            .chunks(2)
            .enumerate()
            .filter_map(|(i, x)| {
                if Packet::right_order(&x[0], &x[1]).unwrap() {
                    Some(i + 1)
                } else {
                    None
                }
            })
            .sum()
    )
}

pub fn part_two(mut input: Input) -> Option<usize> {
    let divider_a = Packet::Array(vec![Packet::Number(2)]);
    let divider_b = Packet::Array(vec![Packet::Number(6)]);

    input.push(divider_a.clone());
    input.push(divider_b.clone());

    input.sort();
    Some(
        input.iter()
            .enumerate()
            .filter_map(|(i, x)| {
                if x == &divider_a {
                    Some(i + 1)
                } else if x == &divider_b {
                    Some(i + 1)
                } else {
                    None
                }
            })
            .product()
    )
}

解析器

这里用了rust的 enum 来表达可以是列表也可以是数字。这里的处理方法就是在解析一个 json 的列表，递归对于每一层进行处理：

  • 数字找到结尾之后放到 enum 中
  • 列表当深度归零时代表找到了对应的开括号和关括号，将其递归处理。

第一部分

按照题目指示对 Packet 进行处理，并且在遇到列表时递归处理。

Option<bool>所表达的意思是：

  • None: 代表需要继续查询
  • Some(true): 代表方向正确
  • Some(true): 代表方向错误

第二部分

搞一个 Ord 的判断大小的 Trait 然后直接 sort 排序就好了。

运行时间

1
2
3
4
5
Day 13
------
Parser: ✓ (1.1ms)
Part 1: 5529 (373.6µs)
Part 2: 27690 (508.5µs)