Advent Of Code 2022 第七天 - 设备上没有剩余空间

发表于 更新于 分类于 ，

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

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

问题

把一个终端的输入输出变成一个树状结构。

第一部分

随着考察的进行，你可以听到鸟儿的鸣叫和雨滴打在树叶上的声音。偶尔，你甚至能听到远处更响亮的声音；这里的动物到底有多大？

精灵们给你的设备不仅在通信系统上有问题。你试着运行一个系统更新：

1
$ system-update --please --pretty-please-with-sugar-on-top

错误: 设备上没有剩余空间

也许你可以删除一些文件来为更新腾出空间？

你在文件系统中浏览以评估情况，并保存终端输出结果（你的谜题输入）。比如说：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
$ cd /
$ ls
dir a
14848514 b.txt
8504156 c.dat
dir d
$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..
$ cd ..
$ cd d
$ ls
4060174 j
8033020 d.log
5626152 d.ext
7214296 k

文件系统由文件（普通数据）和目录（可以包含其他目录或文件）组成的树状结构。最外层的目录被称为/。
你可以在文件系统中导航，进入或离开目录，并列出你当前所在目录的内容。

在终端输出中，以$开头的行是你执行的 命令 ，非常像一些现代计算机。

  • cd意味着 改变目录 。这将改变哪个目录是当前目录，但具体结果取决于参数。

    • cd x移动 一级 ：它在当前目录中寻找名为x的目录并使其成为当前目录。
    • cd ..移出 一级 ：它寻找包含当前目录的目录，然后使该目录成为当前目录。
    • cd /将当前目录切换到最外层的目录，/。

  • ls意味着 列表 。它打印出当前目录所有文件和目录。

    • 123 abc表示当前目录包含一个名为abc的文件，大小为123。
    • dir xyz表示当前目录包含一个名为xyz的目录。

考虑到上面例子中的命令和输出，你可以确定文件系统在视觉上看起来像这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
- / (dir)
  - a (dir)
    - e (dir)
      - i (file, size=584)
    - f (file, size=29116)
    - g (file, size=2557)
    - h.lst (file, size=62596)
  - b.txt (file, size=14848514)
  - c.dat (file, size=8504156)
  - d (dir)
    - j (file, size=4060174)
    - d.log (file, size=8033020)
    - d.ext (file, size=5626152)
    - k (file, size=7214296)

这里，有四个目录。/（最外层的目录），a和d（在/中），以及e（在a中）。这些目录还包含不同大小的文件。

由于磁盘已满，你的第一步可能应该是找到适合删除的目录。要做到这一点，你需要确定每个目录的 总大小
。一个目录的总大小是它直接或间接包含的文件大小之和。(目录本身不算是有任何内在的大小)。

上述目录的总大小可以通过以下方式找到。

  • 目录e的总大小是 584 ，因为它包含一个大小为584的文件i，没有其他目录。
  • 目录a的总大小为 94853 ，因为它包含文件f（大小为29116），g（大小为2557），和h.lst（大小为62596），加上文件i
    间接地（a包含e，e包含i）。
  • 目录d的总大小为 24933642 。
  • 作为最外层的目录，/包含每个文件。它的总大小是 48381165 ，是每个文件的大小之和。

首先，找到所有总大小为 最多100000 的目录，然后计算它们的总大小之和。在上面的例子中，这些目录是a和e；它们的总大小之和是 95437 （94853 + 584）。(在这个例子中，这个过程可以不止一次地计算文件！)

找到所有总大小最多为100000的目录。 这些目录的总大小之和是多少？

第二部分

现在，你准备选择一个目录来删除。

文件系统可用的总磁盘空间是 70000000 。为了运行更新，你需要至少有 30000000 的未使用空间。你需要找到一个可以删除的目录，它将 释放出足够的空间 来运行更新。

在上面的例子中，最外层目录的总大小（也就是已使用空间的总量）是48381165；这意味着 未使用 空间的大小目前必须是21618835，这还没有达到更新所要求的30000000。因此，更新仍然需要在运行前删除一个总大小至少为8381165的目录。

为了达到这个目的，你有以下选择。

  • 删除目录e，这将增加584的未使用空间。
  • 删除目录a，这将增加94853的未使用空间。
  • 删除目录d，这将增加24933642的未使用空间。
  • 删除目录/，这将增加48381165的未使用空间。

目录e和a都太小了；删除它们将不能释放足够的空间。然而，目录d和/都足够大！在这两者之间，选择 小的 。在这两个目录中，选择 小的 一个。d，增加未使用空间 24933642 。

找到最小的目录，如果删除它，将在文件系统上释放足够的空间来运行更新。 该目录的总大小是多少？

代码

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

07.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
use indextree::{Arena, NodeId};

#[derive(Clone)]
pub struct Folder<'a> {
    name: &'a str,
    size: u32,
}

type Input<'a> = Arena<Folder<'a>>;

fn parse(input: &str) -> Input {
    let mut file_tree = Arena::new();
    let mut current_file = file_tree.new_node(Folder { name: "/", size: 0 });
    input.split("$ ").skip(2).for_each(|pair| {
        let (cmd_part, result_part) = pair.split_at(2);
        let trimmed = result_part.trim();
        match (cmd_part, trimmed) {
            ("cd", "..") => current_file = file_tree.get(current_file).unwrap().parent().unwrap(),
            ("cd", _) => current_file = current_file.children(&file_tree).find(|&x| {
                file_tree.get(x).unwrap().get().name == trimmed
            }).unwrap(),
            ("ls", _) => {
                trimmed.lines().for_each(|line| {
                    let (size, name) = line.split_once(" ").unwrap();
                    if size == "dir" {
                        current_file.append(file_tree.new_node(Folder { name, size: 0 }), &mut file_tree);
                    } else {
                        current_file
                            .ancestors(&file_tree)
                            .collect::<Vec<NodeId>>()
                            .into_iter()
                            .for_each(|x| {
                                file_tree.get_mut(x).unwrap().get_mut().size += size.parse::<u32>().unwrap()
                            })
                    }
                })
            }
            _ => unreachable!(),
        }
    });
    file_tree
}

pub fn part_one(input: Input) -> Option<u32> {
    Some(
        input
            .iter()
            .map(|node| node.get().size)
            .filter(|&folder| folder <= 100000)
            .sum()
    )
}

pub fn part_two(input: Input) -> Option<u32> {
    let mut file_iter = input.iter().map(|node| node.get().size);
    let space_required = 30000000 - (70000000 - file_iter.next().unwrap());

    file_iter.filter(|&file| file >= space_required).min()
}

解析器

这里用了 index_tree 的 Arena ，基本上就是一个符合 rust 标准的树状结构。使用 $ 分割不同指令，并且因为 cd 和 ls
都是两个字符，用了个 split_at。

接下来有了命令和参数/输出，我就可以通过 match 来根据逻辑操作 file_tree，并且在遇到文件的时候，当前节点之前的所有节点都会添加大小，相当于预计算了文件夹大小。

第一部分

使用 Iterator 实现的非常简单的过滤求和。

第二部分

因为第一个文件夹 (\) 永远是根文件夹，因此可以获取所有文件的大小，从而获得所需要释放的空间。
再使用 Iterator 找出符合条件最小的那个大小。

运行时间

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

1
2
3
4
5
Day 7
------
Parser: ✓ (121.8µs)
Part 1: 1908462 (6.4µs)
Part 2: 3979145 (8.4µs)