Advent Of Code 2022 第十七天 - 火山碎石流

发表于 更新于 分类于 ，

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

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

问题

模拟盗版俄罗斯方块。

第一部分

你的手持设备已经为你和大象找到了洞穴的另一个出口。地面现在几乎在不断地隆隆作响，但这个奇怪的阀门为你争取了一些时间。不过这里肯定越来越热了。

隧道最终打开，进入一个非常高大、狭窄的房间。巨大又形状怪异的石头从上面落入室内。如果你搞不清楚这些石头接下来会落在哪里，你可能会被压死！

五种类型的岩石有以下奇特的形状，其中#是岩石，.是空隙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
####

.#.
###
.#.

..#
..#
###

#
#
#
#

##
##

石头按照上面显示的顺序落下：首先是-形状，然后是+形状，以此类推。一旦到了列表的末尾，同样的顺序会重复：-形状的石头会是第1个，第6个，第11个，第16个 etc 落下。

岩石不旋转，但它们确实被从墙壁中喷出的热气推来推去。快速浏览一下，就会发现热气喷流在石头下落时对它们的影响（你的谜题输入）。

例如，假设这是你洞穴中的喷射模式：

1
>>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>

在喷射模式中，<表示向左推，而>表示向右推。上面的模式意味着热气将把落下的石头向右推，然后向右，然后向右，然后向左，然后向左，然后向右，如此循环。如果达到列表的末尾，就会重复。

高大的垂直室正好有 七个单位的宽度 。每块石头出现时，其左边的边缘离左边的墙有两个单位的距离，其底部的边缘比房间里最高的石头（如果没有，则是地板）高出三个单位。

在石头出现后，它交替出现在 被热气喷射 一个单位（往下一个符号所指示的方向），然后 往下掉一个单位 。如果任何运动会导致岩石的任何部分移动到墙壁、地板或停止的岩石中，运动不会发生。如果一个 向下的运动会导致下落的石头移动到地板或已经下落的石头上，那么下落的石头就会在原地停止 ，而一个新的石头会立即开始下落。

用@画出下落的石头，#画出停止的石头，上面例子中的喷射模式表现如下。

可视化

 
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
The first rock begins falling:
|..@@@@.|
|.......|
|.......|
|.......|
+-------+

Jet of gas pushes rock right:
|...@@@@|
|.......|
|.......|
|.......|
+-------+

Rock falls 1 unit:
|...@@@@|
|.......|
|.......|
+-------+

Jet of gas pushes rock right, but nothing happens:
|...@@@@|
|.......|
|.......|
+-------+

Rock falls 1 unit:
|...@@@@|
|.......|
+-------+

Jet of gas pushes rock right, but nothing happens:
|...@@@@|
|.......|
+-------+

Rock falls 1 unit:
|...@@@@|
+-------+

Jet of gas pushes rock left:
|..@@@@.|
+-------+

Rock falls 1 unit, causing it to come to rest:
|..####.|
+-------+

A new rock begins falling:
|...@...|
|..@@@..|
|...@...|
|.......|
|.......|
|.......|
|..####.|
+-------+

Jet of gas pushes rock left:
|..@....|
|.@@@...|
|..@....|
|.......|
|.......|
|.......|
|..####.|
+-------+

Rock falls 1 unit:
|..@....|
|.@@@...|
|..@....|
|.......|
|.......|
|..####.|
+-------+

Jet of gas pushes rock right:
|...@...|
|..@@@..|
|...@...|
|.......|
|.......|
|..####.|
+-------+

Rock falls 1 unit:
|...@...|
|..@@@..|
|...@...|
|.......|
|..####.|
+-------+

Jet of gas pushes rock left:
|..@....|
|.@@@...|
|..@....|
|.......|
|..####.|
+-------+

Rock falls 1 unit:
|..@....|
|.@@@...|
|..@....|
|..####.|
+-------+

Jet of gas pushes rock right:
|...@...|
|..@@@..|
|...@...|
|..####.|
+-------+

Rock falls 1 unit, causing it to come to rest:
|...#...|
|..###..|
|...#...|
|..####.|
+-------+

A new rock begins falling:
|....@..|
|....@..|
|..@@@..|
|.......|
|.......|
|.......|
|...#...|
|..###..|
|...#...|
|..####.|
+-------+

在接下来的每一块石头开始落下的时候，你会看到这样的形状：

可视化

 
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
|..@....|
|..@....|
|..@....|
|..@....|
|.......|
|.......|
|.......|
|..#....|
|..#....|
|####...|
|..###..|
|...#...|
|..####.|
+-------+

|..@@...|
|..@@...|
|.......|
|.......|
|.......|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

|..@@@@.|
|.......|
|.......|
|.......|
|....##.|
|....##.|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

|...@...|
|..@@@..|
|...@...|
|.......|
|.......|
|.......|
|.####..|
|....##.|
|....##.|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

|....@..|
|....@..|
|..@@@..|
|.......|
|.......|
|.......|
|..#....|
|.###...|
|..#....|
|.####..|
|....##.|
|....##.|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

|..@....|
|..@....|
|..@....|
|..@....|
|.......|
|.......|
|.......|
|.....#.|
|.....#.|
|..####.|
|.###...|
|..#....|
|.####..|
|....##.|
|....##.|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

|..@@...|
|..@@...|
|.......|
|.......|
|.......|
|....#..|
|....#..|
|....##.|
|....##.|
|..####.|
|.###...|
|..#....|
|.####..|
|....##.|
|....##.|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

|..@@@@.|
|.......|
|.......|
|.......|
|....#..|
|....#..|
|....##.|
|##..##.|
|######.|
|.###...|
|..#....|
|.####..|
|....##.|
|....##.|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

为了向大象证明你的模拟是准确的，他们想知道在 2022个岩石停止后（但在第2023个岩石开始下降前），塔会有多高。在这个例子中，石头塔将有 3068 个单位高。

在2022个石头停止掉落后，石塔会有多少个单位高？

第二部分

大象并不觉得你的模拟是正确的。它们要求知道，在 10000000000个岩石停止后 ，塔会有多高！只有这样，它们才会有足够的信心穿过洞穴。

在上面的例子中，塔会有 1514285714288 个单位高!

10000000000岩石停止后，塔会有多高？

代码

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

17.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
use std::collections::{hash_map::Entry, HashMap};

#[derive(Debug, Clone, Copy)]
pub enum Wind {
    Left,
    Right,
}

type Input = Vec<Wind>;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Shape(u32);

impl Shape {
    const fn all_shapes() -> [Self; 5] {
        [
            Self(0x0000001E),
            Self(0x00081C08),
            Self(0x0004041C),
            Self(0x10101010),
            Self(0x00001818),
        ]
    }

    pub fn blow(&mut self, direction: Wind, mask: u32) {
        let new_pos = match direction {
            Wind::Left => {
                if self.0 & 0x40404040 == 0 {
                    self.0 << 1
                } else {
                    return;
                }
            }
            Wind::Right => {
                if self.0 & 0x01010101 == 0 {
                    self.0 >> 1
                } else {
                    return;
                }
            }
        };

        if new_pos & mask == 0 {
            self.0 = new_pos;
        }
    }

    pub const fn intersects(&self, mask: u32) -> bool {
        self.0 & mask != 0
    }

    pub fn as_bytes(self) -> impl Iterator<Item = u8> {
        self.0.to_le_bytes().into_iter().take_while(|b| *b != 0)
    }
}

fn tower_mask(tower: &[u8], height: usize) -> u32 {
    if height >= tower.len() {
        0
    } else {
        tower[height..]
            .iter()
            .take(4)
            .rev()
            .fold(0u32, |acc, b| (acc << 8) | *b as u32)
    }
}

fn drop_rock(
    tower: &mut Vec<u8>,
    wind: Vec<Wind>,
    mut wind_idx: usize,
    mut shape: Shape,
) -> Option<usize> {
    let mut height = tower.len() + 3;

    loop {
        let wind_dir = wind[wind_idx];
        wind_idx += 1;
        if wind_idx == wind.len() {
            wind_idx = 0;
        }

        let current_mask = tower_mask(tower, height);

        shape.blow(wind_dir, current_mask);

        if height > tower.len() {
            height -= 1;
        } else if height == 0 || shape.intersects(tower_mask(tower, height - 1)) {
            for byte in shape.as_bytes() {
                if height < tower.len() {
                    tower[height] |= byte;
                } else {
                    tower.push(byte);
                }
                height += 1;
            }
            return Some(wind_idx);
        } else {
            height -= 1;
        }
    }
}

fn parse(input: &str) -> Input {
    input
        .chars()
        .filter_map(|c| match c {
            '<' => Some(Wind::Left),
            '>' => Some(Wind::Right),
            _ => None,
        })
        .collect()
}

pub fn part_one(input: Input) -> Option<usize> {
    let num_rocks = 2022;
    let mut tower = Vec::with_capacity(num_rocks * 4);

    let mut wind_idx = 0;
    for shape in Shape::all_shapes().into_iter().cycle().take(num_rocks) {
        wind_idx = drop_rock(&mut tower, input.clone(), wind_idx, shape)?;
    }

    Some(tower.len())
}

pub fn part_two(input: Input) -> Option<usize> {
    let num_rocks = 1000000000000;
    let mut seen_states = HashMap::with_capacity(1024);
    let mut tower = Vec::with_capacity(1024);

    let mut cycle_height = 0;
    let mut wind_idx = 0;
    let shapes = Shape::all_shapes();
    let mut n = 0;
    while n < num_rocks {
        let shape_idx = n % shapes.len();
        let shape = shapes[shape_idx];

        wind_idx = drop_rock(&mut tower, input.clone(), wind_idx, shape)?;
        n += 1;

        if tower.len() < 8 {
            continue;
        }

        let skyline = u64::from_ne_bytes(tower[tower.len() - 8..].try_into().ok()?);
        let state = (skyline, shape_idx, wind_idx);

        match seen_states.entry(state) {
            Entry::Occupied(e) => {
                let (old_n, old_height) = e.get();
                let num_rocks_in_cycle = n - old_n;
                let num_cycles = (num_rocks - n) / num_rocks_in_cycle;
                n += num_rocks_in_cycle * num_cycles;
                cycle_height += num_cycles * (tower.len() - old_height);
                seen_states.clear();
            }
            Entry::Vacant(e) => {
                e.insert((n, tower.len()));
            }
        }
    }

    Some(tower.len() + cycle_height)
}

解析器

把输入变成一个 enum ，没什么好说的。

第一部分

这个问题我使用了位来存储形状以及状态。以 0x0004041C (L) 为例，这就是它们在十六进制中的样子。当我们以二进制方式一次打印出一个字节，每个字节在一个新的行上，它看起来像这样：

1
2
3
4
00000100
00000100
00011100
00000000

在移动之前做检查：如果俄罗斯方块、边界和塔的四行的 & 运算是零，那就意味着你可以安全地移动那一块。注意，这是一个普通的移位（>>或<<），不需要位元旋转，部分原因是移位可以保留棋子的形状。

第二部分

当然你可以运行非常多次第一部分，但这里的重点在于你要发现这个风向是循环的，这使得到某一时刻，塔的结构必定循环，因此你只需要找出循环的周期，并计算前后偏差值就可以找到答案。

我使用了一个简单的启发式算法来进行循环检测，最后8行很方便地形成了一个 u64，并且可以快速哈希。我之前使用了16行和一个128位的int，但事实证明我的输入并不需要这么大的样板。

运行时间

1
2
3
4
5
Day 17
------
Parser: ✓ (34.5µs)
Part 1: 3211 (655.1µs)
Part 2: 1589142857183 (1.4ms)