【TIS-100 攻略】第 21~22 关：排序器、已存储图像解码器

本文首发于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原创不易，转载请注明出处。

第 21 关《排序器》（Sequence Sorter）关卡展示

出现了，第一大章公认的最难关卡——排序。你会不断从 IN 里收到一些以 0 结尾的序列。你需要将序列中的数字从小到大排序后，输出给 OUT。

排序一直是计算机编程中一个最基础的，但又有一定难度的挑战。这里我介绍几种常见的排序算法：

①选择排序：顾名思义，选择排序就是每次选出序列中最小的那个数，将它输出并从序列中拿出后，原先第二小的数就变成了新的最小数。我们再用同样的方法找出序列里第二小的、第三小的……直到最终的最大数，即可完成排序。选择排序的示意图如下：

C 语言代码如下（提供的 nums 数组一定以 0 结尾）：

②插入排序：选择排序是先将所有的输入量都读入内存，再一个一个从小到大筛选。插入排序则稍微做了一点调整：维护一个有序列表，每读入一个数字，就检查它应该放在列表中的什么位置。假如列表是从小到大排序的，那么找到【刚好大于等于新数字】的那个数，并将新数字插在那个数字的前面，就可以保持列表有序。本算法相比于选择排序，读数据和排序是同时进行的，不像选择排序是先将所有数字读进来再一个一个挑，效率上比选择排序要高一点。

由于新进入的数字可能有“插队”的需求，所以本算法需要使用栈来辅助完成。插入排序的示意图如下：

C 语言代码如下：

③计数排序，输入数字的取值范围很窄时比较适用。统计取值范围内所有数字的出现次数，输出时从小到大检查，每个数字出现了几次就输出几次。计数排序的示意图如下：

以下代码假设提供的 nums 一定在 1~9 的范围内：

本题因为提供的数字均为两位数，取值范围为 10~99，而 TIS-100 里的栈只有 15 格空间，没有足够大的空间用来记录 10~99 各出现了多少次。而且序列里最多就 5 个数字，也就是说 10~99 里绝大多数的数字出现的次数都为 0。本题首先没有这么多空间支撑计数排序，即使有，那也是对空间的巨大浪费。所以本题不考虑使用计数排序。

以上我们也看到了，插入排序算法和栈是完美契合的。本题我就是用插入排序法完成的。代码如下：

我们将上排的那个栈视为 1 号栈（即 C 语言代码里的 stk1），将下排的视为 2 号栈（即 C 语言代码里的 stk2）。

1 号和 3 号节点都能用来操作 1 号栈（即 C 语言代码里的 stk1）。这里我们做了一项分工：3 号节点用来放最初的 999 哨兵，以及最终从栈里取数输出；中间的排序工作则由 1 号节点来完成。

3 号节点在放入 999 哨兵后（mov 999 up），会等待 2 号节点发来启动命令（jro left）。如果序列中的所有数字都已放入栈中，2 号节点会发送一个 1，然后我们再往下跳 1 行，继续执行收尾任务。现在 3 号节点只需停留在第 2 行即可。

1 号节点专门从来从 IN 获得新的数字，并将数字放入 1 号栈的合理位置。1 号节点每从 IN 收到一个数字，都先复制一份到自己的 acc 里（mov up acc），再将这个数字传给下方的 2 号节点（mov acc down）。此时检查：如果收到的数字是 0，说明到达了序列末尾，剩下的工作就由 3 号节点完成，我则是跳回第 1 行，准备对下一组数据进行排序（jez 1）。

如果收到的数字不是 0，说明尚未到达序列末尾。这时候，我从栈里弹一个数字发给 2 号节点（mov right down），再把当前数字也发给 2 号节点（mov acc down），令 2 号节点对这两个数字做差。传完后，听从 2 号节点的指令（jro down）。

2 号节点一共可能发两种不同的指令：

• 我们需要在栈中找到【刚好大于等于当前数字的数】，并将当前数字放在那个数的前面。如果栈中的数字 - 当前数字 < 0，说明刚弹出的数字【小于当前数】，尚未找到插入点，此时向上发送 -2 令 1 号节点【继续弹栈】。

• 如果栈中的数字 - 当前数字 ≥ 0，说明刚弹出的数字【大于等于当前数】，我们找到了插入点，此时向上发送 1 令 1 号节点【停止弹栈】，然后 2 号节点将之前弹出的所有数依次返还。

收到 -2 时，说明 2 号节点要求我们重新从栈里弹一个数交给它。此时我们向上跳 2 行，重新从 1 号栈里弹一个数字，将新弹出的数字和当前数字重新发给 3 号节点（mov right down, mov acc down）。

收到 1 时，说明我们找到了插入点。首先 2 号节点会将最后一次弹出的数（也就是刚好大于等于当前数的那个数）还给我们，我们向下跳 1 行，接收这个数并将它放回 1 号栈（mov down right），然后把当前数放在那个数的前面（mov acc right）。接下来，2 号节点会把你之前弹出的更小的数都交还给你，最后还会给你一个值为 0 的哨兵。我们来者不拒，全部接收（mov down acc），然后判断收到的数是否是 0。收到的数不为 0 时，我们要跳回第 7 行，将收到的数放回到栈里（jnz 7, mov acc right），并继续从 2 号节点收取，直到收取到最终的哨兵 0 后，跳回第 1 行，从 IN 获得序列中的下一个数。

1 号节点的工作就是这么多。接下来我们看正中央的 2 号节点。2 号节点首先给 2 号栈放入一个值为 0 的哨兵（mov 0 down），然后从 1 号节点收取当前 IN 里的数字（mov up acc）。收到的数字不为 0 时，说明尚未到达序列的末尾，我们跳到第 7 行执行（jnz 7）。此时我们先从 1 号节点收取弹出的【栈数字】，将其放入 2 号节点暂存（mov up acc, mov acc down），然后再从 1 号节点收取【当前数字】，对两者做差（sub up）。差值为负时，按照计划，向 1 号节点发送 -2 命令并继续判断下一组数字（jlz 6, mov -2 up, mov up acc, mov acc down, sub up），直到差值为非负为止，向 1 号节点发送 1 命令（mov 1 up），并将 2 号栈里的所有数字全部推上去。每从 2 号栈里拿一个数（mov down acc），都往上推（mov acc up）。尚未拿到最后的哨兵 0 时，跳回第 12 行继续拿（jnz c），直到拿到最后的 0 为止，跳回第 1 行继续从 1 号节点收取下一个 IN 里的数字。

当 2 号节点收到了表示序列末尾的 0 时，1 号栈里的数字就是当前序列从小到大排列好的样子了。这时候我们给右边的 3 号节点发送一个 1，让 3 号节点把栈里的所有数字都取出来并往下发（mov 1 right）。栈中的数字取完后，我们会从 3 号节点收到一个 -3，我们顺势向上跳 3 行，准备继续为下一个序列排序（jro right）。

3 号节点给 1 号栈放完 999 的哨兵后（mov 999 up）就一直在等待 2 号节点发送一个 1（jro left）。收到 1 表示序列中的所有数字都已经有序地放在 1 号栈里了，这时候我们才能从栈里取数字并一一发往输出口。每取一个数字，就将它减去 999（mov up acc, sub 999）并判断是否为 0。不为 0 时，说明尚未取到末尾的 999 哨兵，此时加回 999 恢复成原数传给 4 号节点（add 999, mov acc down），并跳回第 3 行继续取（jnz 3），直到取到最终的 999 哨兵后，1 号栈彻底空掉后，我们给 4 号节点发完最后的 0（jez 7, mov acc down）后，再给 2 号节点节点发送 -3，示意可以开始读下一个序列了（mov -3 left）。

4 号节点直接无脑将 3 号节点传来的数送往输出端口即可（mov up down）。

点击左下角的【RUN】，稍等片刻，便会弹出结算界面：

至此，我们终于把第一大章里的最难关卡搞定了，可喜可贺。

第 22 关《已存储图像解码器》（Stored Image Decoder）关卡展示

本关的 IN 会给你一些数字，其中第奇数个数字表示线条长度，第偶数个数字表示颜色。设提供给你的数字是 w1, c1, w2, c2, ..., wn, cn。那么你需要从左上角 (0, 0) 点开始，依次：

• 画一条长度为 w1，颜色为 c1 的水平线；

• 画一条长度为 w2，颜色为 c2 的水平线；

• ……

• 画一条长度为 wn，颜色为 cn 的水平线。

如果中途画笔到达了右端点，则切换到下一行，回到左端点继续画（CRLF）。

本关的思路其实跟第 15 关画国际象棋棋盘的思路有点像（传送门：【TIS-100 攻略】第 14~17 关：测试图 1、测试图 2、曝光遮罩查看器、直方图查看器）。只不过第 15 关的无限流提供的是 3、0 相间的数字，本关的无限流改为依次提供 w1 次 c1，w2 次 c2……一直到最终的 wn 次 cn 就好了。代码如下：

上方的两个节点纯传话。

左下角的节点将收到的 w 放入 acc 里（mov up acc），将收到的 c 放入 bak 里（swp, mov up acc, swp）。接下来我们要给右边发送 w 次 c，每发送一次 c（swp, mov acc right, swp），就令 w 减去 1（sub 1）。此时判断 w 是否减到了 0。尚未减到 0 时，跳回到第 5 行继续发 c（jnz 5），直到 w 减到 0 后，从上方接收新的 w 和 c。

右下角的节点跟第 15 关的代码几乎一样，只是由于这次提供颜色的无限流在左边，所以代码里的 right 全部换成了 left。另外，本关的循环次数也由之前的 31 还原成了 30。除此之外，该节点的代码和第 15 关一模一样，没有做任何改变。我就不再解释了。

点击左下角的【RUN】，稍等片刻，你的屏幕会突然被画上一个神秘图片，然后在你面前会呈现出一些难度更大的全新关卡。

以上图片只有第一次通过本关后才会呈现。当你后续再次通过本关时，就只会展示直方图了。至此，恭喜你完成了第一大章的所有关卡，并解锁 100 PERCENT V1 成就（Solve every puzzle in the TIS-100 SEGMENT MAP，解出 TIS-100 SEGMENT 地图里的所有谜题）。