Advent Of Code 2022 第四天 - 清理营地

发表于 更新于 分类于 ，

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

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

问题

简单来说就是找出两个范围完全覆盖和重叠的数量。

第二部分

在最后一批物资从船上卸下之前，需要清理空间，因此几个精灵被分配了清理营地部分区域的工作。每个区都有一个独特的 ID号码
，每个精灵都被分配到一个区的ID范围。

然而，当一些精灵互相比较他们的区段分配时，他们注意到许多分配是 重叠 的。为了尝试快速找到重叠之处，减少重复工作，精灵们结成对子，为每对精灵制定一个
大的章节任务清单 （你的谜题输入）。

例如，考虑以下的章节任务对列表：

1
2
3
4
5
6
2-4,6-8
2-3,4-5
5-7,7-9
2-8,3-7
6-6,4-6
2-6,4-8

对于最初的几对，这个列表意味着。

  • 在第一对精灵中，第一个精灵被分配到2-4区（2、3和4区），而第二个精灵被分配到6-8区（6、7、8区）。
  • 第二对中的精灵每人被分配到两个区。
  • 第三对中的精灵各自被分配到三个区：一个得到了5、6和7区，而另一个也得到了7，加上8和9。

这个例子的列表使用了个位数的区段ID，以使其更容易绘制；你的实际列表可能包含更大的数字。从视觉上看，这些成对的章节分配看起来像这样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
.234.....  2-4
.....678.  6-8

.23......  2-3
...45....  4-5

....567..  5-7
......789  7-9

.2345678.  2-8
..34567..  3-7

.....6...  6-6
...456...  4-6

.23456...  2-6
...45678.  4-8

有些对子已经注意到他们的一个任务 完全包含 另一个。例如，2-8 完全包含 3-7，6-6 被 4-6
完全包含。在一个任务完全包含另一个任务的配对中，一对中的一个精灵将专门清理他们的伙伴已经在清理的部分，所以这些似乎是最需要重新考虑的。在这个例子中，有
2 个这样的配对。

在多少个配对中，一个范围完全包含另一个？

第二部分

看来还是有相当多的重复工作计划。相反，精灵们想知道 重叠的对的数量。

在上面的例子中，前两对（2-4,6-8和2-3,4-5）没有重叠，而其余四对（5-7,7-9，2-8,3-7，6-6,4-6，和2-6,4-8）有重叠。

  • 5-7,7-9在一个部分重叠，7。
  • 2-8,3-7与所有的3到7部分重叠。
  • 6-6,4-6重叠在一个部分，6。
  • 2-6,4-8在4、5和6部分重叠。

所以，在这个例子中，重叠的赋值对的数量是 4 。

在多少个配对中，范围是重叠的？

代码

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

04.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
use std::cmp::{max, min};
use std::ops::Range;

type Input = Vec<(Range<u8>, Range<u8>)>;

fn cover(v1: &Range<u8>, v2: &Range<u8>) -> bool {
    v2.start >= v1.start && v2.end <= v1.end
}

fn overlap(v1: &Range<u8>, v2: &Range<u8>) -> bool {
    max(v1.start, v2.start) <= min(v1.end, v2.end)
}

fn parse(input: &str) -> Input {
    input
        .lines()
        .map(|l| {
            let (part1, part2) = l.split_once(",").unwrap();
            let (s1, e1) = part1.split_once("-").unwrap();
            let (s2, e2) = part2.split_once("-").unwrap();
            (
                (s1.parse().unwrap()..e1.parse().unwrap()),
                (s2.parse().unwrap()..e2.parse().unwrap()),
            )
        })
        .collect::<Input>()
}

pub fn part_one(input: Input) -> Option<usize> {
    Some(
        input
            .iter()
            .filter(|(v1, v2)| cover(v1, v2) || cover(v2, v1))
            .count()
    )
}

pub fn part_two(input: Input) -> Option<usize> {
    Some(
        input
            .iter()
            .filter(|(v1, v2)| overlap(v1, v2))
            .count()
    )
}

解析器

每一行切割成两个范围。

第一部分

范围是否完全覆盖取决于其中一个的开始小于等于另一个的开始，并且结束大于等于另一个的结束。

第二部分

是否部分重叠我使用的方法是开始的最大值是否小于结束的最小值，因为一旦大于了，就代表两个范围直接有一个空洞，是不允许的。

运行时间

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

1
2
3
4
5
Day 4
------
Parser: ✓ (85.2µs)
Part 1: 498 (1.9µs)
Part 2: 859 (1.2µs)