Advent Of Code 2022 第十天 - 阴极射线管

发表于 更新于 分类于 ，

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

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

问题

使用指令驱动CRT，但需要注意周期的情况。

第一部分

你避开绳索，跳进河里，游到岸边。

精灵们嚷嚷着要在上游与他们会合，但河水太大，无法准确分辨他们在说什么。他们过完桥，就从视野中消失了。

像这样的情况一定是精灵们优先考虑让你的手持设备上的通讯系统工作的原因。你把它从背包里拿出来，但屏幕上的一个大裂缝里慢慢流出的水告诉你，它可能不会有什么直接用途。

或许 ，你能为该设备的视频系统设计一个替代品 它似乎是某种阴极射线管屏幕和简单的CPU，它们都由一个精确的 时钟电路 驱动。时钟电路以恒定的速率跳动；每一次跳动被称为一个 周期 。

首先要弄清楚由CPU发送的信号。CPU有一个单一的寄存器，X，它的起始值为1。它只支持两条指令。

  • addx V需要 两个周期 来完成。 在两个周期后 ，X寄存器增加了V的值。(V可以是负数)。
  • noop需要 一个周期 来完成。它没有其他作用。

CPU在程序中使用这些指令（你的谜题输入），以某种方式告诉屏幕要画什么。

考虑一下下面这个小程序：

1
2
3
noop
addx 3
addx -5

这个程序的执行过程如下。

  • 在第一个周期的开始，noop指令开始执行。在第一个周期中，X是1。在第一个周期后，noop指令结束执行，不做任何事情。
  • 在第二个周期的开始，addx 3指令开始执行。在第二个循环中，X仍然是1。
  • 在第三个周期中，X仍然是1。 在第三个周期后，addx 3指令结束执行，将X设置为4。
  • 在第四个周期的开始，addx -5指令开始执行。在第四个周期中，X仍然是4。
  • 在第五个周期中，X仍然是4。在第五个周期后，addx -5指令结束执行，将X设置为1。

也许你可以通过观察整个执行过程中X寄存器的值来了解一些情况。现在，考虑 在第20个周期和之后的每40个周期 （即在第20、60、100、140、180和220个周期）的 信号强度 （周期数乘以X寄存器的值）。

例如，考虑这个较大的程序：

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
addx 15
addx -11
addx 6
addx -3
addx 5
addx -1
addx -8
addx 13
addx 4
noop
addx -1
addx 5
addx -1
addx 5
addx -1
addx 5
addx -1
addx 5
addx -1
addx -35
addx 1
addx 24
addx -19
addx 1
addx 16
addx -11
noop
noop
addx 21
addx -15
noop
noop
addx -3
addx 9
addx 1
addx -3
addx 8
addx 1
addx 5
noop
noop
noop
noop
noop
addx -36
noop
addx 1
addx 7
noop
noop
noop
addx 2
addx 6
noop
noop
noop
noop
noop
addx 1
noop
noop
addx 7
addx 1
noop
addx -13
addx 13
addx 7
noop
addx 1
addx -33
noop
noop
noop
addx 2
noop
noop
noop
addx 8
noop
addx -1
addx 2
addx 1
noop
addx 17
addx -9
addx 1
addx 1
addx -3
addx 11
noop
noop
addx 1
noop
addx 1
noop
noop
addx -13
addx -19
addx 1
addx 3
addx 26
addx -30
addx 12
addx -1
addx 3
addx 1
noop
noop
noop
addx -9
addx 18
addx 1
addx 2
noop
noop
addx 9
noop
noop
noop
addx -1
addx 2
addx -37
addx 1
addx 3
noop
addx 15
addx -21
addx 22
addx -6
addx 1
noop
addx 2
addx 1
noop
addx -10
noop
noop
addx 20
addx 1
addx 2
addx 2
addx -6
addx -11
noop
noop
noop

这个输入的信号强度可以确定如下：

  • 在第20个周期中，寄存器X的值是21，所以信号强度是20*21= 420 。(第20个周期发生在第二个addx -1的中间，所以寄存器X的值是起始值1，加上所有其他的addx值到这一点：1 + 15 - 11 + 6 - 3 + 5 - 1 - 8 + 13 + 4 = 21。)
  • 在第60个周期，寄存器X的值为19，所以信号强度为60*19= 1140 。
  • 在第100个周期，寄存器X的值是18，所以信号强度是100*18= 1800 。
  • 在第140个周期，寄存器X的值为21，所以信号强度为140*21 = 2940 。
  • 在第180个周期，寄存器X的值为16，所以信号强度为180*16 = 2880 。
  • 在第220个周期，寄存器X的值是18，所以信号强度是220*18= 3960 。

这些信号强度的总和是 13140 。

找出第20、60、100、140、180和220个周期内的信号强度。 这六个信号强度之和是多少？

第二部分

似乎X寄存器控制了一个图形的水平位置。具体来说，图像的宽度为3像素，X寄存器设置该精灵的 中间的水平位置 。(在这个系统中，不存在 垂直位置 这种东西：如果精灵的水平位置将其像素放在CRT当前绘制的位置，那么这些像素将被绘制出来）。

你数数CRT上的像素：40个宽，6个高。这个CRT屏幕从左到右画出最上面的一行像素，然后是下面的一行，以此类推。每行的最左边的像素在0位置，每行的最右边的像素在39位置。

与CPU一样，CRT与时钟电路紧密相连：CRT在每个周期内 绘制一个像素 。将屏幕上的每个像素表示为一个 # ，这里是每行的第一个和最后一个像素被绘制的周期。

1
2
3
4
5
6
Cycle   1 -> ######################################## <- Cycle  40
Cycle  41 -> ######################################## <- Cycle  80
Cycle  81 -> ######################################## <- Cycle 120
Cycle 121 -> ######################################## <- Cycle 160
Cycle 161 -> ######################################## <- Cycle 200
Cycle 201 -> ######################################## <- Cycle 240

因此，通过仔细计时CPU指令和CRT绘制操作，你应该能够在每个像素被绘制的瞬间确定图像是否可见。如果图像的位置使其三个像素中的一个是当前正在绘制的像素，那么屏幕上就会产生一个 亮的 像素（#）；否则，屏幕上就会留下该像素的 暗 的像素（.）。

上面这个较大的例子中的前几个像素的绘制方法如下：

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
图像位置: ###.....................................

开始周期    1: 开始执行  addx 15
经过周期  1: CRT绘制像素于位置 0
当前CRT: #

经过周期  2: CRT绘制像素于位置 1
当前CRT: ##
结束周期   2: 完成执行 addx 15 (寄存器X的值为 16)
图像位置: ...............###......................

开始周期  3: 开始执行  addx -11
经过周期  3: CRT绘制像素于位置 2
当前CRT: ##.

经过周期  4: CRT绘制像素于位置 3
当前CRT: ##..
结束周期   4: 完成执行 addx -11 (寄存器X的值为 5)
图像位置: ....###.................................

开始周期    5: 开始执行  addx 6
经过周期  5: CRT绘制像素于位置 4
当前CRT: ##..#

经过周期  6: CRT绘制像素于位置 5
当前CRT: ##..##
结束周期   6: 完成执行 addx 6 (寄存器X的值为 11)
图像位置: ..........###...........................

开始周期    7: 开始执行  addx -3
经过周期  7: CRT绘制像素于位置 6
当前CRT: ##..##.

经过周期  8: CRT绘制像素于位置 7
当前CRT: ##..##..
结束周期   8: 完成执行 addx -3 (寄存器X的值为 8)
图像位置: .......###..............................

开始周期    9: 开始执行  addx 5
经过周期  9: CRT绘制像素于位置 8
当前CRT: ##..##..#

经过周期 10: CRT绘制像素于位置 9
当前CRT: ##..##..##
结束周期  10: 完成执行 addx 5 (寄存器X的值为 13)
图像位置: ............###.........................

开始周期   11: 开始执行  addx -1
经过周期 11: CRT绘制像素于位置 10
当前CRT: ##..##..##.

经过周期 12: CRT绘制像素于位置 11
当前CRT: ##..##..##..
结束周期  12: 完成执行 addx -1 (寄存器X的值为 12)
图像位置: ...........###..........................

开始周期   13: 开始执行  addx -8
经过周期 13: CRT绘制像素于位置 12
当前CRT: ##..##..##..#

经过周期 14: CRT绘制像素于位置 13
当前CRT: ##..##..##..##
结束周期  14: 完成执行 addx -8 (寄存器X的值为 4)
图像位置: ...###..................................

开始周期   15: 开始执行  addx 13
经过周期 15: CRT绘制像素于位置 14
当前CRT: ##..##..##..##.

经过周期 16: CRT绘制像素于位置 15
当前CRT: ##..##..##..##..
结束周期  16: 完成执行 addx 13 (寄存器X的值为 17)
图像位置: ................###.....................

开始周期   17: 开始执行  addx 4
经过周期 17: CRT绘制像素于位置 16
当前CRT: ##..##..##..##..#

经过周期 18: CRT绘制像素于位置 17
当前CRT: ##..##..##..##..##
结束周期  18: 完成执行 addx 4 (寄存器X的值为 21)
图像位置: ....................###.................

开始周期   19: 开始执行  noop
经过周期 19: CRT绘制像素于位置 18
当前CRT: ##..##..##..##..##.
结束周期  19: 完成执行 noop

开始周期   20: 开始执行  addx -1
经过周期 20: CRT绘制像素于位置 19
当前CRT: ##..##..##..##..##..

经过周期 21: CRT绘制像素于位置 20
当前CRT: ##..##..##..##..##..#
结束周期  21: 完成执行 addx -1 ( 20)
图像位置: ...................###..................

让程序运行到完成，使CRT产生以下图像：

1
2
3
4
5
6
##..##..##..##..##..##..##..##..##..##..
###...###...###...###...###...###...###.
####....####....####....####....####....
#####.....#####.....#####.....#####.....
######......######......######......####
#######.......#######.......#######.....

渲染你的程序所给的图像。 你的CRT上出现哪八个大写字母？

代码

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

10.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
use itertools::Itertools;

type Input = Vec<i16>;

fn in_sprite_range(i: usize, x: i16) -> bool {
    (x-1..=x+1).contains(&((i % 40) as i16))
}

fn parse(input: &str) -> Input {
    let mut val = 1;
    let mut k = vec![1];
    let mut other = input
        .trim()
        .split(|c| c == ' ' || c == '\n')
        .filter_map(| x| {
            if x == "" {
                return None
            }
            val += x.parse::<i16>().unwrap_or(0);
            Some(val)
        })
        .collect::<Vec<i16>>();
    k.append(&mut other);
    k
}

pub fn part_one(input: Input) -> Option<i16> {
    Some(
        input
            .iter()
            .skip(19)
            .step_by(40)
            .enumerate()
            .map(|(i, &x)| (i * 40 + 20) as i16 * x)
            .sum()
    )
}

pub fn part_two(input: Input) -> Option<String> {
    let k = input.iter()
        .enumerate()
        .filter_map(|(i, &x)| {
            if i < 240 {
                Some(if in_sprite_range(i, x) { '▓' } else { '░' })
            } else {
                None
            }
        })
        .chunks(40)
        .into_iter()
        .map(|x| x.collect::<String>())
        .join("\n")
        .trim()
        .to_string();
    Some(k)
}

解析器

这题有一点比较有意思，就是当你把每一个字符用换行符和空格切割，获得的那个向量就是当每一个周期结束之后添加的值。以那个简短程序做例子，

1
2
3
noop
addx 3
addx -5

会变成 [0, 0, 3, 0, -5]，这刚好对应了 addx 需要两个周期的属性，而将这些累加就可以获得那个周期结束时的寄存器值。

第一部分

当我们有了每个周期之后的寄存器值，跳过 19 个参数(因为我们要获取的值是在该周期运行期间的值，也就等于上个周期完成的值)，然后每40个获得一次就可以获得题目的数列。

第二部分

使用寄存器的值和它的 index 就可以判断那个像素是否在图像范围之内，把这个 char 的向量每四十个分割成一块并且组装成一个字符串就可以获得结果。

因为看 # 和 . 组成的图像比较费眼睛，其实是可以用其他符号来代替，这里我就用了阴影字符。

本来脑抽了还以为怎么用电脑看这块输出找出那几个英文字，难道要训练一个识字模型？原来只需要你眼睛看就好。

运行时间

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

1
2
3
4
5
6
7
8
9
10
11
Day 10
------
Parser: ✓ (10.8µs)
Part 1: 14760 (500.0ns)
Part 2: ▼  (9.4µs)
▓▓▓▓░▓▓▓▓░░▓▓░░▓▓▓▓░▓▓▓░░▓░░▓░▓▓▓░░▓▓▓▓░
▓░░░░▓░░░░▓░░▓░▓░░░░▓░░▓░▓░░▓░▓░░▓░▓░░░░
▓▓▓░░▓▓▓░░▓░░░░▓▓▓░░▓░░▓░▓░░▓░▓░░▓░▓▓▓░░
▓░░░░▓░░░░▓░▓▓░▓░░░░▓▓▓░░▓░░▓░▓▓▓░░▓░░░░
▓░░░░▓░░░░▓░░▓░▓░░░░▓░▓░░▓░░▓░▓░▓░░▓░░░░
▓▓▓▓░▓░░░░░▓▓▓░▓▓▓▓░▓░░▓░░▓▓░░▓░░▓░▓▓▓▓░