Advent Of Code 2022 第十八天 - 沸腾的巨石

发表于 更新于 分类于 ，

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

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

问题

计算立体物体的表面积。

第一部分

你和大象们终于到达了新鲜空气。你已经出现在一座大火山的底部附近，这座火山似乎正在积极地喷发! 幸运的是，熔岩似乎正在远离你，流向大海。

熔岩的碎片仍在向你喷出，所以你在洞穴出口处又躲了一会儿。在洞外，你可以看到熔岩落在一个池塘里，听到它凝固时发出的响亮嘶嘶声。

根据熔岩中的特定化合物和冷却速度，它可能正在形成黑曜石 ！冷却速度应该基于熔岩液滴的表面积，所以当液滴从你身边飞过时，你要快速扫描它（你的谜题输入）。

由于熔岩的移动速度很快，扫描效果不是很好；它的分辨率相当低，因此，它用3D网格上的 1x1x1立方体 来近似熔岩液滴的形状，每个立方体的位置都是x,y,z。

为了近似计算表面积，计算每个立方体中没有立即连接到另一个立方体的边的数量。因此，如果你的扫描只有两个相邻的立方体，如1,1,1和2,1,1，每个立方体将有一个侧面被覆盖，五个侧面暴露出来，总的表面积为 10 面。

这里有一个更大的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2,2,2
1,2,2
3,2,2
2,1,2
2,3,2
2,2,1
2,2,3
2,2,4
2,2,6
1,2,5
3,2,5
2,1,5
2,3,5

在上面的例子中，算上所有没有与另一个立方体相连的边，总表面积是 64 。

你所扫描的熔岩水滴的表面积是多少？

第二部分

你的计算似乎有些偏差。冷却速度取决于外部表面积，但你的计算还包括被困在熔岩液滴中的气穴的表面积。

只考虑熔岩液滴翻滚到池塘时，水和蒸汽可以到达的外部面。蒸汽会尽可能地膨胀到达，完全取代熔岩液滴外部的任何空气，但绝不会斜向膨胀。

在上面这个较大的例子中，正好有一个立方体的空气被困在熔岩液滴内（在2,2,5），所以熔岩液滴的外表面积是 58 。

你扫描的熔岩液滴的外表面积是多少？

代码

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

18.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
use itertools::Itertools;
use std::collections::HashMap;
use std::hash::Hash;

#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub struct Cube {
    pub pos: u16, // Pos is a bit map of x, y, z, where each data point is 5 bits and a block is 15 bits
}

impl Cube {
    pub fn neighbours(&self) -> Vec<Cube> {
        let mut neighbours = Vec::new();
        let (x, y, z) = self.pos();
        if x > 0 {
            neighbours.push(Cube { pos: self.pos - 1 });
        }
        if x < 22 {
            neighbours.push(Cube { pos: self.pos + 1 });
        }
        if y > 0 {
            neighbours.push(Cube { pos: self.pos - 32 });
        }
        if y < 22 {
            neighbours.push(Cube { pos: self.pos + 32 });
        }
        if z > 0 {
            neighbours.push(Cube {
                pos: self.pos - 1024,
            });
        }
        if z < 22 {
            neighbours.push(Cube {
                pos: self.pos + 1024,
            });
        }
        neighbours
    }

    pub fn pos(&self) -> (u16, u16, u16) {
        (
            self.pos & 0x1F,
            (self.pos >> 5) & 0x1F,
            (self.pos >> 10) & 0x1F,
        )
    }

    pub fn from_pos(x: u16, y: u16, z: u16) -> Self {
        Self {
            pos: x | (y << 5) | (z << 10),
        }
    }
}

type Input = (Vec<Cube>, HashMap<u16, bool>, usize);

fn parse(input: &str) -> Input {
    let cubes = input
        .lines()
        .filter_map(|line| {
            let mut line_iter = line.split(",");
            let x = line_iter.next()?.parse::<u16>().unwrap();
            let y = line_iter.next()?.parse::<u16>().unwrap();
            let z = line_iter.next()?.parse::<u16>().unwrap();
            Some(Cube::from_pos(x, y, z))
        })
        .collect_vec();
    let mut cube_space_map = HashMap::new();
    let mut zero_count = 0;
    cubes.iter().for_each(|cube| {
        cube_space_map.insert(cube.pos, true);
        let (x, y, z) = cube.pos();
        if x == 0 || y == 0 || z == 0 {
            zero_count += 1;
        }
    });
    (cubes, cube_space_map, zero_count)
}

pub fn part_one(input: Input) -> Option<usize> {
    let (input, cube_space_map, zero_count) = input;

    Some(
        input
            .iter()
            .map(|cube| {
                cube.neighbours()
                    .iter()
                    .filter(|neighbour| cube_space_map.get(&neighbour.pos).is_none())
                    .count()
            })
            .sum::<usize>()
            + zero_count,
    )
}

pub fn part_two(input: Input) -> Option<usize> {
    let mut processed_map = HashMap::new();
    let mut queue = vec![Cube::from_pos(0, 0, 0)];
    let mut exterior = 0;
    let (_, cube_space_map, zero_count) = input;
    while let Some(cube) = queue.pop() {
        exterior += cube
            .neighbours()
            .iter()
            .filter_map(|neighbour| {
                if cube_space_map.get(&neighbour.pos).is_none() {
                    if processed_map.get(&neighbour.pos).is_none() {
                        processed_map.insert(neighbour.pos, true);
                        queue.push(*neighbour);
                    }
                    None
                } else {
                    Some(1)
                }
            })
            .sum::<usize>()
    }
    Some(exterior + zero_count)
}

解析器

方块的位置使用一个 u16 表达，第一位空位，接着三个 5 位的数字，分别表示 x、y 和 z。这样我们就可以使用 & 和 | 来获取和设置这些值。

因为这是 unsigned 的，所以我们无法获得 0 的邻居，因此需要计算出 0 的个数，这样我们就可以在最后加上这个值。

第一部分

对于每个方块，我们计算出它的邻居，然后过滤掉已经存在的方块，剩下的面数就是我们要的结果。

第二部分

我们需要计算出所有的外部面，这里我们使用一个队列来处理，每次从队列中取出一个方块，然后计算它的邻居，如果邻居没计算过并且是空气，那么就将它加入到队列中，否则将它的面数加入到结果中。

本来是使用递归的，但是因为递归会导致栈溢出，所以改成了队列。

运行时间

1
2
3
4
5
Day 18
------
Parser: ✓ (508.6µs)
Part 1: 4308 (587.2µs)
Part 2: 2540 (2.1ms)