【TIS-100 攻略】TIS-NET 第 1 关：序列合并器
本文首发于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原创不易，转载请注明出处。
恭喜你完成了 TIS-100 SEGMENT MAP 系列里的所有关卡，现在请点击右上角的【TIS-100 NET DIRECTORY】按钮，开始挑战难度更大的 TIS-NET 系列关卡。
TIS-NET 第 1 关《序列合并器》（Sequence Merger）关卡展示
IN.A 和 IN.B 会不断给你提供一些以 0 结尾的序列（两者长度不一定相等）。你收到的两个序列里的数字都已按从小到大的顺序排好序。请你将 IN.A 和 IN.B 这两个序列合并成一个序列，同时确保合并后的序列仍然有序。
将两个序列里的数都放进栈里，再使用第 21 关的做法对栈里的数字排序是一种容易想到的做法。但问题在于，本关的两个栈相隔太远，传话非常不便。而且这样做也没有利用【得到的序列已经有序】这样的特征。
其实，两个有序数组合并成一个数组，是有专门的算法的，这叫做【双指针算法】。两个指针 i、j 一开始分别指向两个数组的头部，然后我们比较两个数字的大小，选择其中较小的一项输出，然后指向较小项的指针向后移动，指向较大项的指针不动。中途若有一个指针指向了数组末端，那么剩下的元素就全从另一个数组里拿。如图所示：
我们将以上算法写成 C 语言代码（a 和 b 数组一定以 0 结尾，表示数组的末端）：
以上的算法里，两个数组的哨兵都是 0。考虑到每次都是选择两个目标数中的较小数，如果我们把哨兵换成一个足够大的数（比如 999），那么当其中一个量到达数组末端，另一个量却没到达时，比较大小时就一直是另一个小，我们在合并的时候就不需要特殊判定两个指针是否指到了末端。当两者中的较小值都为 999 时，我们自然会知道，两个指针都指向了末端，此时输出最后的 0。改进后的算法代码如下：
现在我们将以上 C 语言代码转写成 TIS-100 的汇编代码，如下：
本关用到了 6 个节点，我分别用它们所在的方向（左上、右上、左、中、右、下）来指代。
左上和左下的节点分别把 IN.A 和 IN.B 提供的值发给中路靠左和中路靠右的节点（mov up down）。接下来是中路靠左的节点：
中路靠左的节点会收到左上发来的【指针 i 所指向的数】，即 a[i]，将它存入 acc（mov up acc）。
此时判断收到的数是否为哨兵 0。若不是哨兵 0，跳到第 4 行执行（jnz 4），
否则令 acc 加上 999，将哨兵 0 变为哨兵 999（add 999）。
到了第 4 行后，左节点会将 a[i] 的值发给中央节点（mov acc right），
然后听从中央节点的指令（jro right）。中央节点发送 -1 时，表示保留住当前的 a[i]，指针 i 不向后移动，那么我们就跳回第 4 行，继续向中央节点发送当前的 a[i]；而当中央节点发送 -4 时，表示丢弃掉当前的 a[i]，指针 i 向后移动，那么我们就跳回第 1 行，从左上节点接收下一个 a[i]。
接下来看中路靠右的节点：
中路靠右的节点会收到右上发来的【指针 j 所指向的数】，即 b[j]，将它存入 acc（mov up acc）。
此时判断收到的数是否为哨兵 0。若不是哨兵 0，跳到第 4 行执行（jnz 4），
否则令 acc 加上 999，将哨兵 0 变为哨兵 999（add 999）。
到了第 4 行后，右节点会将 b[j] 的值向中央节点发两遍（mov acc left）
（mov acc left）。我们在之前的攻略里反复强调了：取出两者中的较小／较大值时，其中一方必然要将自己的数提供两遍。我的代码里选择了把 b[j] 提供两遍，其实改为把 a[i] 提供两遍的话，道理也是一样的。
把 b[j] 发送两遍后，右节点开始听从中央节点的指令（jro left）。中央节点发送 -2 时，表示保留住当前的 b[j]，指针 j 不向后移动，那么我们就跳回第 4 行，继续向中央节点发送当前的 b[j]；而当中央节点发送 -5 时，表示丢弃掉当前的 b[j]，指针 j 向后移动，那么我们就跳回第 1 行，从右上节点接收下一个 b[j]。
中央节点是算法的核心部分。
首先我们计算 a[i] 和 b[j] 的差值（mov left acc）
（sub right）
差值大于 0 时，跳到第 11 行执行（jgz b）。
那么第 4 行仅当差值小于等于 0 时能执行到。差值小于等于 0 时，我们肯定是输出 a[i] 并令指针 i 后移。首先必然给左边节点发送 -4，让左边节点丢弃掉当前的 a[i]（mov -4 left）。
然后我们注意到，中央节点的 acc 的值是 a[i] - b[j] 的值，此时我们加回右边节点第二次提供的 b[j]，让 acc 变成 a[i] - b[j] + b[j] = a[i]（add right）。
到了这一步，我们还不能直接输出这个值，我们需要进一步判定 a[i] 是不是哨兵 999。因此我们再将 acc 减去 999（sub 999）并判定 acc 是否变成了 0。
如果变成了 0，说明 i、j 指针都指向了各自的末端，右边节点自然也要把当前的 b[j] 给丢弃掉。acc 为 0 时，我们空降到第 13 行，给右边节点发送 -5，让右边节点丢弃掉当前的 b[j]，并将最后的 0 往下发（jez d, mov -5 right, mov acc down）。
acc 不为 0 时，说明 i 指针尚未到达 a 数组的末端，a[i] 并不是哨兵 999。这时候只有 i 指针向后移动，j 指针不变，我们按照规则，向右边节点发送 -2，令右边节点保持当前的 b[j] 不动（mov -2 right）。
接着我们将 acc 加回一个 999，得到原始的 a[i] 值（add 999），
然后跳过第 11~13 行的互斥逻辑，直接空降到第 14 行，将得到的 a[i] 值往下发（jmp e, mov acc down）。
第 11~13 行仅当 a[i] - b[j] 的差值大于 0 时才能执行到。差值大于 0 时，说明 b[j] 比 a[i] 小，那么当前项我们自然是输出较小的 b[j]，并令 j 指针向后移动。我们从右边节点拿到第二次提供的 b[j]，放入 acc 暂存（mov right acc）。
接下来，i 指针不动，按照规则，向左边节点发送 -1，令左边节点保持当前的 a[i] 不动（mov -1 left）；
j 指针需要后移一格，按照规则，向右边节点发送 -5，令右边节点丢弃掉当前的 b[j]（mov -5 right）。
最后，我们将 acc 中的值发给下方节点（mov acc down）。
下方的节点没啥好说的，老老实实把中央节点传来的数送给 OUT.S 端口就 OK 了（mov up down）。
点击左下角的【RUN】，稍等片刻，便会弹出结算界面：
