【TIS-100 攻略】第 18 关：信号窗口筛选器
本文首发于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原创不易，转载请注明出处。
第 18 关《信号窗口筛选器》（Signal Window Filter）关卡展示
本关的 IN 会不断提供数字，你要随时将【前 3 个数之和】和【前 5 个数之和】输出给 OUT.3 和 OUT.5。如果窗口中的数字不足 3 个／5 个，视空位为 0，即输出【前方所有数之和】。
本关我们首先想到的，自然是用栈将【前 5 个数】存起来，然后 OUT.3 上方的节点只取其中三个数字相加，而 OUT.5 上方的节点将这些数字全部加起来。代码如下：
本关使用到了 7 个节点，单纯的方向已经不便于描述了，因此我将写有代码的节点都标上了编号，后续我会用【x 号节点】这样的描述来指代。
1 号节点的位置不好，和栈离得老远了，所以它把收到的数字传给 2 号节点，由它来干活（mov up right）。接下来看 2 号节点的逻辑：
由于最远需要追溯到前 4 个数字，所以 2 号节点在收到第一个数字前，要往栈里补 4 个 0（mov 0 right）
（mov 0 right）
（mov 0 right）
（mov 0 right）
然后，每从 1 号节点收到一个数字，就往下方的 4 号节点传（mov left down）。
传完后，需要折返到第 5 行，准备好传下一个数字（jmp 5）。如果任由程序跳回第 1 行的话，会往栈里写入多余的 0。
4 号节点将 2 号节点发来的【当前数】传给右边的 5 号节点。5 号节点的位置非常好，夹在两个栈中间，它要做的工作就是将栈中的数字取出来，发给左边，取完后再将栈恢复原样。4 号节点接下来要等待 5 号节点将栈中的数字取出，所以这时候我们先看 5 号节点的逻辑：
5 号节点收到【当前数】后，将它存入右下角的栈里暂存（mov left down）。
紧接着从右上角的节点里取出【前 1~3 个数】，统统扔到右下角的栈里暂存（mov up down）
（mov up down）
（mov up down）
由于【前 4 个数】在本次使用后，以后都不需要再次使用，所以取出【前 4 个数】后，直接扔给左边的节点，无需暂存（mov up left）。
对于剩下的【前 3 个数】、【前 2 个数】、【前 1 个数】和【当前数】这四个数，每个数都要往左边发两遍，而且它们还要在将来用到，不能像【前 4 个数】那样丢弃，而是要放回到栈里。这部分操作较为复杂，将同样的逻辑复写四遍的话，代码空间不够用，因此这里我们写成循环的方式。首先将 bak 置为 4（mov 4 acc）
（swp）
接下来，我们从下方的栈里取一个数字（mov up acc），
将它向左边发两遍（mov acc left）
（mov acc left）后，
扔回右上角的栈里（mov acc up）。
每这样做一次，就令 bak 减去 1（swp）
（sub 1）并判断 bak 是否减到了 0。
尚未减到 0 时，说明右下角的栈没有被取空，跳回第 7 行继续取（jnz 7），直到 bak 减到 0 后，最近的 5 个数字就全部发给了左边。此时跳回第 1 行，等待左边发来下一次的数字。
现在回过头来看 4 号节点。
4 号节点把当前数发给 5 号节点后（mov up right），
就开始等待 5 号节点将最近 5 个数传来。其中【前 4 个数】只会传一遍，【前 3 个数～当前数】都会被传两遍。4 号节点需要计算【前 4 个数 + 前 3 个数 + 前 2 个数 + 前 1 个数 + 当前数】的值，而 2 号节点只需计算【前 2 个数 + 前 1 个数 + 当前数】的值。当 4 号节点收到【前 4 个数】的时候，将 acc 置为该数（mov right acc）；
对于【前 3 个数】，5 号节点由于代码行数限制，也会发两遍。但是这个数 3 号节点是不需要的，所以这两份副本里，4 号节点需要丢弃掉其中一个（mov right nil），
并在收到另一个时，将它累加到自己的 acc 里（add right）。
对于剩下的【前 2 个数～当前数】，5 号节点也会发两遍，3 号节点和 4 号节点各需要一份，所以 4 号节点将其中一份传给左边（mov right left），
另一份累加到自己的 acc 里（add right）。
（mov right left）
（add right）
（mov right left）
（add right）
当 5 号节点把所有该传的数字都传来后，本轮的和就计算完毕了，栈里的【前 3 个数～当前数】就理所当然地变成了【前 4 个数～前 1 个数】。此时 4 号节点把本次算好的【最近 5 个数的和】发给 7 号节点，让 7 号节点把这个值送往 OUT.5 的输出口（mov acc down）。
以上代码中我们用到了一个特殊的寄存器 nil：当你读取 nil 寄存器时，读到的是恒 0（执行 mov nil acc 后，acc 会被置为 0）；而如果你把一个值写入 nil 寄存器，该值会被丢弃。注意 4 号节点里的 mov right nil 这行代码，它的作用就是将 5 号节点第一次发来的【前 3 个数】丢弃。4 号节点的 acc 寄存器已经被用来存储累加和了，如果想要不使用 nil 寄存器把这个值丢弃的话，就只能存入 bak 寄存器。而存入 bak 寄存器则需要 3 行代码（swp, mov right acc, swp），所以这里不如简单点，直接丢给 nil 寄存器，让 nil 寄存器销毁掉这个值。
3 号节点的逻辑稍微简单点，它会从 4 号节点收到【前 2 个数】、【前 1 个数】和【当前数】，直接将它们累加起来发给下方的 6 号节点，让 6 号节点把这个值送往 OUT.3 的输出口（mov right acc, add right, add right, mov acc down）。
6 号节点和 7 号节点都是从它们的上方接收本次的计算结果并输出（mov up down, mov up down）。
点击左下角的【RUN】，稍等片刻，便会弹出结算界面：
利用【滑动窗口】算法优化程序
以上方案并不是最优的，因为我们做了太多的重复计算。以求最近 5 个数的和为例：
计算 sum[4] 时，我们读取了 num[0~4] 的值，并将它们累加了起来，这无可厚非；可是计算 sum[5] 时，我们仍然老老实实地读取了 num[1~5] 的值，并将它们累加了起来。这就导致了两个问题：①num[1~4] 的这部分和被重复算了一遍，效率上有损失；②上一项 sum[4] 的值没有被有效利用。这时候，我们不妨换一种思路：
后一项可以由前一项推导而来，只要在前一项的基础上，加上【当前值】，减去【前 5 个数】，就 OK 了。
最近 3 个数的和同理，改为在前一项的基础上加上【当前值】并减去【前 3 个数】即可。这样的话，我们计算任何一项结果，都只要在前一项的基础上【加一个数】并【减一个数】，这样我们的计算量就大大减少，效率肉眼可见地提升了。优化后的代码如下：
这次因为要用到前 5 个数，所以栈里要多放一个 0，2 号节点写了五句 mov 0 right。当然你也可以改成计数循环的写法，省去 1 行代码行数（1: mov 5 acc, 2: mov 0 right, 3: sub 1, 4: jnz 2）。写完 5 个 0 后，剩余的操作都是在 1、3、4、5 号节点间进行，没有 2 号节点什么事了。2 号节点此时一条 jro 0，永久停在当前位置挂机。
1 号节点收到【当前数】后，向 3 号节点发送 3 遍（mov up acc, mov acc down * 3）。这 3 次分别用在这 3 个地方：①作为【最近 3 个数之和】的累加项；②作为【最近 5 个数之和】的累加项；③存入栈里，作为将来要用到的【前 3 个数】及【前 5 个数】。
3 号节点在收到三个【当前数】时，按照“先传话，后干事”的原则，将前两次收到的数发给右边，然后第三次收到的数再累加到自己的 acc 里（mov up right, mov up right, add up）。
4 号节点会从 3 号节点收到两个【当前数】。同样按照“先传话，后干事”的原则，把第一次收到的数发给 5 号节点，把第二份收到的数累加到自己的 acc 里（mov left right, add left）。
接下来是 5 号节点：
5 号节点会从 4 号节点收到【当前数】，将它放入右下角的栈里暂存（mov left down）。
接着从右上角的栈里取出【前 1 个数】和【前 2 个数】暂存到右下角（mov up down）
（mov up down）
取到【前 3 个数】时，将它复制一份（mov up acc）
发给左边（mov acc left），
再存到右下角的栈里（mov acc down）。
取到【前 4 个数】时，直接扔下去（mov up down）。
取到【前 5 个数】时，拿出来直接扔给左边，这个值以后就没用了，可以直接废弃掉了（mov up left）。
至此，右下角的栈里存着【前 4 个数～当前数】这 5 个数字，将它们倒回右上角的栈（mov down up * 5）。同样地，这 5 条同样的语句也能改写成循环的方式，以节省一行代码（9: mov 5 acc, a: mov down up, b: sub 1, c: jnz a）。
4 号节点首先收到的是【前 3 个数】，这个数是 3 号节点要减去的，我们将这个数传给 3 号节点（mov right left）；然后 4 号节点会收到【前 5 个数】，4 号节点减去这个数（sub right）。
3 号节点在收到 4 号节点发来的【前 3 个数】时，令 acc 减去这个数（sub right）。至此，3 号节点和 4 号节点都通过【滑动窗口】的方式计算好了最近 3 个数和最近 5 个数之和，他俩把算好的值分别发给下方的 6 号和 7 号节点（mov acc down, mov acc down）。
6 号节点和 7 号节点都是从它们的上方接收本次的计算结果并输出（mov up down, mov up down）。
点击左下角的【RUN】，稍等片刻，便会弹出结算界面：
运行时长由原先的 2153 周期骤降到 973 周期，代码行数也由 38 行减少到了 35 行，针不戳。如果你按照我的指示把两段重复的代码都改写成了循环的形式，代码行数甚至能减少到 33 行。
