【TIS-100 攻略】TIS-NET 第 3~5 关：取值范围限制器、信号纠错器、子序列提取器
本文首发于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原创不易，转载请注明出处。
TIS-NET 第 3 关《取值范围限制器》（Sequence Range Limiter）关卡展示
本关的 IN 会源源不断地给你一些以 0 结尾的序列，你需要将序列中的每一个数字进行边界检查：如果序列中的数字高于 IN.H 指示的上限值，或低于 IN.L 指示的下限值时，将它修改为最近的边界值输出，否则直接原样输出。每个序列都对应一组不同的 IN.H 和 IN.L。
本关写成 C 语言代码的话非常简单：
因为涉及到跟边界值做比较，所以由既往经验可得，边界值和原数中的一方需要提供两遍。这里我们选择提供两遍边界值。另外我们注意到题目中所有序列的长度都为 5，也就是说，同样的 IN.H 和 IN.L 需要提供 10 遍后，才能切换为下一组数据。那么本关的代码就很简单了：
首先是右上角节点：
右上角节点将 acc 置为 IN.H（mov up acc），
将 bak 置为 10（swp）
（mov 10 acc）
（swp）
每提供一次 IN.H（mov acc left），
就令 bak 减去 1（swp）
（sub 1）并判断是否减到了 0。
尚未减到 0 时，说明当前的 IN.H 没有提供满 10 次，跳回到第 4 行继续提供（jnz 4），直到提供满 10 次为止，跳回第 1 行读取下一个 IN.H。
左上角节点的逻辑跟右上角类似，获得 IN.L 的值，并向上方居中的节点提供 10 次。一笔带过。现在看上方居中的节点：
上方居中的节点首先从 IN 里读一个数字 nums[i]（mov up acc）。
如果读到了 0，说明到达了序列末尾，直接跳到第 13 行输出这个 0 即可（jez d, mov acc down）。
读到非 0 值时，需要跟两个边界值各做一次比较。首先计算 nums[i] - H 的值（sub right），并令差值和 0 比大小。
若差值小于 0，则跳到第 7 行执行（jlz 7）。
差值大于等于 0 时，说明 nums[i] 等于或高于上限值 H，nums[i] 需要强制缩小到上限值，此时我们强行用上限值 H 覆盖 nums[i]（mov right acc）
并跳过第 7 行的互斥逻辑（jmp 8）。
差值小于 0 时，说明 nums[i] 低于上限值 H，nums[i] 不需要更新为上限值，此时加回一个 H（add right），将 acc 还原成 nums[i] 自身。
和上限值比较完后，我们需要将 nums[i] 再和下限值做一次比较。计算 nums[i] - L 的值（sub left），并令差值和 0 比大小。
若差值大于 0，则跳到第 12 行执行（jgz 7）。
差值小于等于 0 时，说明 nums[i] 等于或低于下限值 L，此时我们强行用输出下限值 L，忽略 nums[i] 自身的值（mov left down）
并跳过第 12 行的互斥逻辑（jmp 1）。
差值大于 0 时，说明 nums[i] 高于下限值 L，nums[i] 不需要更新为下限值，此时加回一个 L，将 acc 还原成 nums[i] 自身（add left）
并输出（mov acc down）。
中央节点和下方节点纯传话（mov up down）。
点击左下角的【RUN】，稍等片刻，便会弹出结算界面：
优化运行速度
以上代码做一点微小的调整即可提高 40% 的运行速度：
首先上方居中的节点对于两个边界值一直是迫不及待的状态，所以左右两侧的节点可以改为把同样的 mov acc left/right 连写十遍，而不是使用循环计数的方法提供十遍。这样虽然会增加代码行数，但是省下了循环计数的时间，上方居中的节点可以更快地和边界值做差值运算。
其次，上方居中的节点如果在和其中一个边界值比较的时候，已经被强制修正为边界值了，那就没有必要再和另一个边界值做比较了，此时可以直接把另一侧两次提供的边界值丢弃掉。优化后的代码如下：
左／右上角的节点没啥好说的，原先用循环的方式将 L 和 H 提供十遍，现在变成了连写十行同样的代码来提供（mov up acc, mov acc right/left * 10）。
上方居中的节点注意一下第 5~7 行，当 nums[i] - H >= 0 时，直接将 nums[i] 重置为右边提供的 H 值（mov right acc），然后减去一个 L（sub left），再跳到第 13 行加上一个 L（jmp 13, add left），就相当于消耗掉了本轮两次提供的 L 值，无需再多此一举跟 L 比较一次。其他地方除了行号外，和上一版方案一致。
点击左下角的【RUN】，稍等片刻，便会弹出结算界面：
运行时长由 580 周期减少到了 327 周期，效率提升了 (580-327) / 580 ≈ 43.6%，很好。
TIS-NET 第 4 关《信号纠错器》（Signal Error Corrector）关卡展示
你会从 IN.A 和 IN.B 收到两个信号。通常情况下原样输出即可，但如果其中一路的信号为负数，则该路信号无效，改为输出另一路的信号。题目保证两路信号不会同时为负。本关的代码如下：
IN.B 下方的节点将收到的 B 路信号汇总到左路（mov up left）。
IN.A 下方的节点先传自己的 A 路信号（mov up down），再传右边发来的 B 路信号（mov right down）。
中央节点纯传话（mov up down）。
左下角节点将 A 路信号放入 bak（mov up acc, swp），再将 B 路信号放入 acc（mov up acc）。B 路信号为正数时，跳到第 7 行将 B 路信号原样发给右边的节点（jgz 7, mov acc right），否则 A、B 交换，将 A 路信号发给右边的节点（swp, mov acc right）。接下来有两种可能的情况：
B 路信号不正常，A、B 发生了交换：那么此时 acc 里放的是 A 路信号，bak 里放的是无效的 B 路信号（负数）。那么我们一定能判断出 bak 是负数，我们直接将 acc 里的 A 路信号发给 OUT.A 就行了；
B 路信号正常，A、B 未发生交换，那么此时 acc 里放的是 B 路信号，bak 里放的是 A 路信号。我们判断 bak 是否是负数，若是负数，说明 A 路信号无效，我们将 acc 里的 B 路信号值发给 OUT.A，否则直接将 bak 里的原始 A 路信号发给 OUT.A。
综上所述，我们接下来只需要发现 bak 是正数（swp），就输出 bak（jgz a, mov acc down），否则输出 acc（swp, mov acc down）就 OK 了。
右下角的节点会从左下角的节点处收到 B 路信号的输出值，将该值送往下方的 OUT.B 即可（mov left down）。
点击左下角的【RUN】，稍等片刻，便会弹出结算界面：
优化运行速度
以上方案的所有活都是左下角一个节点干的。现在我们采用并行操作，让右下角节点也同时干活，就能提高运行速度。优化后的代码如下：
上面的 4 个节点都纯传话（mov up down）。
下方的两个节点都将自己的信号传给对方，并接收（或丢弃）对方发来的信号。根据【一方发送信号的同时另一方必须接收】的原则，两个节点必然有一个要选择【先发自己的，再收对方的】，另一个要选择【先收对方的，再发自己的】。如果两个节点都选择【先发后收】或【先收后发】，就会导致通讯失败，程序阻塞。本程序里，左下角的节点采用了【先发后收】的策略，右下角的节点采用了【先收后发】的策略。
左下角的节点收到自己的信号后（mov up acc），先将自己的信号【发送】给右下角的节点（mov acc right），然后【接收或丢弃】对方的信号：如果我的信号是正数，那么跳到第 6 行，丢弃掉对方的信号，输出我的信号（jgz 6, mov right nil, mov acc down）；如果我的信号是负数，则输出对方的信号（mov right down, jmp 1）。
右下角的节点收到自己的信号后（mov up acc），先进行判定，并选择【接收或丢弃】对方的信号：如果我的信号是正数，那么跳到第 5 行，丢弃掉对方的信号（jgz 5, mov left nil）；如果我的信号是负数，则接收对方的信号（mov left acc, jmp 6）。处理完毕后，再将自己的信号【发送】给左下角的节点（mov acc left）并输出（mov acc down）。
这里要提一下，如果自己的信号是负数，那么由于执行了第 3 行的 mov left acc，自己的负数信号会被对方的信号所覆盖，最后传过去的值并不是原始的负数信号。不过这不影响结果的正确性。因为两路信号不会同时为负，如果你的信号是负数的话，对方的信号一定是正数，你不论传什么，对方都会丢弃掉的。
一个先发后收，一个先收后发，配合得天衣无缝。点击左下角的【RUN】，稍等片刻，便会弹出结算界面：
运行时长由 418 减少到了 286，效率提升了 (418-286) / 286 ≈ 46.2%，这就是并行的力量。
TIS-NET 第 5 关《子序列提取器》（Subsequence Extrator）关卡展示
IN.S 会提供给你一些以 0 结尾的序列，然后你需要从 IN.I 里读入两个数字，设它们为 i 和 j。你需要将给定序列里第 i~j 个数字提取出来，将提取出的子序列发送给 OUT。
这里的索引是以 0 起始的，比如，当你收到 [74, 83, 30, 89, 0] 这样的序列时，第 0 个数字是 74，第 1 个数字是 83，第 2 个数字是 30，第 3 个（最后一个）数字是 89。当你从 IN.I 读到 0 和 1 时，你需要构建一个由第 0~1 个数字组成的子序列，即输出 [74, 83, 0]。
现在我们已知 i 和 j，要想提取出序列中的第 i~j 个数字，方法很明显是这样的：
舍弃掉序列中的第 0~i-1 个数字，即舍弃掉前 i 个数字；
索引 i~j 共有 j-i+1 个数字，连续提取这么多数字发送到输出口后，输出一个哨兵 0；
舍弃掉剩下的数字，直到遇见最终的哨兵 0 为止。
代码很简单，如下：
IN.I 下方的节点将收到的 i 和 j 都传给右边（mov up right）。然后看核心的右方节点：
右边的节点首先收到的是 i（mov left acc），
将它复制一份到 bak 里备用（sav）。接下来的 13 行代码用来依次完成三步曲：
舍弃掉 IN.S 里的前 i 个数字。首先检查 i 是否已经是 0。当 i 已经是 0 时，跳过第一阶段，直接跳到第 7 行进入第二阶段（jez 7）。
当 i 尚未到达 0 时，我们每丢弃序列里的一个数字（mov up nil），
就令 i 减去 1（sub 1）并继续判定 i 是否到达了 0。
尚未到达 0 时，跳回第 4 行继续减（jnz 4），直到 i 减到 0 后，进入第二阶段。
提取序列中接下来的 j-i+1 个数字并输出。我们将 bak 里存的 i 拿出来（swp），
减去左边发来的 j（sub left）。
此时 acc 里的值是 i-j，是起始索引减去终止索引，是个负数。所以这里我们要反其道而行之，每提取出序列里的一个数字（mov up down），
就令 acc 加上 1（add 1）并判断 acc 是否加到了 0。
acc 尚未加到 0 时，跳回到第 9 行继续取（jnz 9），
直到 acc 加到 0 后，我们一共取了序列里的 j-i 个字符，还差一个字符没取，此时我们将这最后的字符取出并输出（mov up down），
然后输出哨兵 0（mov 0 down），进入第三阶段。
将序列中剩下的数字全部舍弃（mov up acc），
只要未遇见哨兵 0，就跳回第 14 行继续丢（jnz e），直到遇见哨兵 0 为止。
中央节点和下方节点纯传话（mov up down）。
点击左下角的【RUN】，稍等片刻，便会弹出结算界面：
三项指标都在直方图的最左端，看来是十全十美的解法了。
