本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請注明出處。

第 21 關(guān)《排序器》（Sequence Sorter）關(guān)卡展示

出現(xiàn)了，第一大章公認(rèn)的最難關(guān)卡——排序。你會不斷從 IN 里收到一些以 0 結(jié)尾的序列。你需要將序列中的數(shù)字從小到大排序后，輸出給 OUT。

排序一直是計(jì)算機(jī)編程中一個最基礎(chǔ)的，但又有一定難度的挑戰(zhàn)。這里我介紹幾種常見的排序算法：

①選擇排序：顧名思義，選擇排序就是每次選出序列中最小的那個數(shù)，將它輸出并從序列中拿出后，原先第二小的數(shù)就變成了新的最小數(shù)。我們再用同樣的方法找出序列里第二小的、第三小的……直到最終的最大數(shù)，即可完成排序。選擇排序的示意圖如下：

C 語言代碼如下（提供的 nums 數(shù)組一定以 0 結(jié)尾）：

②插入排序：選擇排序是先將所有的輸入量都讀入內(nèi)存，再一個一個從小到大篩選。插入排序則稍微做了一點(diǎn)調(diào)整：維護(hù)一個有序列表，每讀入一個數(shù)字，就檢查它應(yīng)該放在列表中的什么位置。假如列表是從小到大排序的，那么找到【剛好大于等于新數(shù)字】的那個數(shù)，并將新數(shù)字插在那個數(shù)字的前面，就可以保持列表有序。本算法相比于選擇排序，讀數(shù)據(jù)和排序是同時進(jìn)行的，不像選擇排序是先將所有數(shù)字讀進(jìn)來再一個一個挑，效率上比選擇排序要高一點(diǎn)。

由于新進(jìn)入的數(shù)字可能有“插隊(duì)”的需求，所以本算法需要使用棧來輔助完成。插入排序的示意圖如下：

C 語言代碼如下：

③計(jì)數(shù)排序，輸入數(shù)字的取值范圍很窄時比較適用。統(tǒng)計(jì)取值范圍內(nèi)所有數(shù)字的出現(xiàn)次數(shù)，輸出時從小到大檢查，每個數(shù)字出現(xiàn)了幾次就輸出幾次。計(jì)數(shù)排序的示意圖如下：

以下代碼假設(shè)提供的 nums 一定在 1~9 的范圍內(nèi)：

本題因?yàn)樘峁┑臄?shù)字均為兩位數(shù)，取值范圍為 10~99，而 TIS-100 里的棧只有 15 格空間，沒有足夠大的空間用來記錄 10~99 各出現(xiàn)了多少次。而且序列里最多就 5 個數(shù)字，也就是說 10~99 里絕大多數(shù)的數(shù)字出現(xiàn)的次數(shù)都為 0。本題首先沒有這么多空間支撐計(jì)數(shù)排序，即使有，那也是對空間的巨大浪費(fèi)。所以本題不考慮使用計(jì)數(shù)排序。

以上我們也看到了，插入排序算法和棧是完美契合的。本題我就是用插入排序法完成的。代碼如下：

我們將上排的那個棧視為 1 號棧（即 C 語言代碼里的 stk1），將下排的視為 2 號棧（即 C 語言代碼里的 stk2）。

1 號和 3 號節(jié)點(diǎn)都能用來操作 1 號棧（即 C 語言代碼里的 stk1）。這里我們做了一項(xiàng)分工：3 號節(jié)點(diǎn)用來放最初的 999 哨兵，以及最終從棧里取數(shù)輸出；中間的排序工作則由 1 號節(jié)點(diǎn)來完成。

3 號節(jié)點(diǎn)在放入 999 哨兵后（mov 999 up），會等待 2?號節(jié)點(diǎn)發(fā)來啟動命令（jro left）。如果序列中的所有數(shù)字都已放入棧中，2?號節(jié)點(diǎn)會發(fā)送一個 1，然后我們再往下跳 1 行，繼續(xù)執(zhí)行收尾任務(wù)?，F(xiàn)在 3?號節(jié)點(diǎn)只需停留在第 2 行即可。

1 號節(jié)點(diǎn)專門從來從 IN 獲得新的數(shù)字，并將數(shù)字放入 1 號棧的合理位置。1 號節(jié)點(diǎn)每從 IN 收到一個數(shù)字，都先復(fù)制一份到自己的 acc 里（mov up acc），再將這個數(shù)字傳給下方的 2 號節(jié)點(diǎn)（mov acc down）。此時檢查：如果收到的數(shù)字是 0，說明到達(dá)了序列末尾，剩下的工作就由 3 號節(jié)點(diǎn)完成，我則是跳回第 1 行，準(zhǔn)備對下一組數(shù)據(jù)進(jìn)行排序（jez 1）。

如果收到的數(shù)字不是 0，說明尚未到達(dá)序列末尾。這時候，我從棧里彈一個數(shù)字發(fā)給 2 號節(jié)點(diǎn)（mov right down），再把當(dāng)前數(shù)字也發(fā)給 2 號節(jié)點(diǎn)（mov acc down），令 2 號節(jié)點(diǎn)對這兩個數(shù)字做差。傳完后，聽從 2?號節(jié)點(diǎn)的指令（jro down）。

2 號節(jié)點(diǎn)一共可能發(fā)兩種不同的指令：

• 我們需要在棧中找到【剛好大于等于當(dāng)前數(shù)字的數(shù)】，并將當(dāng)前數(shù)字放在那個數(shù)的前面。如果棧中的數(shù)字 - 當(dāng)前數(shù)字 < 0，說明剛彈出的數(shù)字【小于當(dāng)前數(shù)】，尚未找到插入點(diǎn)，此時向上發(fā)送 -2 令 1 號節(jié)點(diǎn)【繼續(xù)彈?！?。

• 如果棧中的數(shù)字 - 當(dāng)前數(shù)字 ≥ 0，說明剛彈出的數(shù)字【大于等于當(dāng)前數(shù)】，我們找到了插入點(diǎn)，此時向上發(fā)送 1 令 1 號節(jié)點(diǎn)【停止彈?！?，然后 2 號節(jié)點(diǎn)將之前彈出的所有數(shù)依次返還。

收到?-2?時，說明 2?號節(jié)點(diǎn)要求我們重新從棧里彈一個數(shù)交給它。此時我們向上跳 2 行，重新從 1 號棧里彈一個數(shù)字，將新彈出的數(shù)字和當(dāng)前數(shù)字重新發(fā)給 3 號節(jié)點(diǎn)（mov right down, mov acc down）。

收到 1 時，說明我們找到了插入點(diǎn)。首先 2?號節(jié)點(diǎn)會將最后一次彈出的數(shù)（也就是剛好大于等于當(dāng)前數(shù)的那個數(shù)）還給我們，我們向下跳 1 行，接收這個數(shù)并將它放回?1 號棧（mov down right），然后把當(dāng)前數(shù)放在那個數(shù)的前面（mov acc right）。接下來，2?號節(jié)點(diǎn)會把你之前彈出的更小的數(shù)都交還給你，最后還會給你一個值為 0 的哨兵。我們來者不拒，全部接收（mov down acc），然后判斷收到的數(shù)是否是 0。收到的數(shù)不為 0 時，我們要跳回第 7 行，將收到的數(shù)放回到棧里（jnz 7, mov acc right），并繼續(xù)從 2?號節(jié)點(diǎn)收取，直到收取到最終的哨兵 0?后，跳回第 1 行，從 IN 獲得序列中的下一個數(shù)。

1 號節(jié)點(diǎn)的工作就是這么多。接下來我們看正中央的 2?號節(jié)點(diǎn)。2 號節(jié)點(diǎn)首先給 2 號棧放入一個值為 0 的哨兵（mov 0 down），然后從 1 號節(jié)點(diǎn)收取當(dāng)前 IN 里的數(shù)字（mov up acc）。收到的數(shù)字不為 0 時，說明尚未到達(dá)序列的末尾，我們跳到第 7 行執(zhí)行（jnz 7）。此時我們先從 1 號節(jié)點(diǎn)收取彈出的【棧數(shù)字】，將其放入 2 號節(jié)點(diǎn)暫存（mov up acc, mov acc down），然后再從 1 號節(jié)點(diǎn)收取【當(dāng)前數(shù)字】，對兩者做差（sub up）。差值為負(fù)時，按照計(jì)劃，向 1 號節(jié)點(diǎn)發(fā)送 -2 命令并繼續(xù)判斷下一組數(shù)字（jlz 6, mov -2 up, mov up acc, mov acc down, sub up），直到差值為非負(fù)為止，向 1 號節(jié)點(diǎn)發(fā)送 1 命令（mov 1 up），并將 2 號棧里的所有數(shù)字全部推上去。每從 2 號棧里拿一個數(shù)（mov down acc），都往上推（mov acc up）。尚未拿到最后的哨兵?0 時，跳回第 12?行繼續(xù)拿（jnz c），直到拿到最后的 0 為止，跳回第 1 行繼續(xù)從 1 號節(jié)點(diǎn)收取下一個 IN 里的數(shù)字。

當(dāng) 2?號節(jié)點(diǎn)收到了表示序列末尾的 0 時，1 號棧里的數(shù)字就是當(dāng)前序列從小到大排列好的樣子了。這時候我們給右邊的 3 號節(jié)點(diǎn)發(fā)送一個 1，讓 3?號節(jié)點(diǎn)把棧里的所有數(shù)字都取出來并往下發(fā)（mov 1 right）。棧中的數(shù)字取完后，我們會從 3?號節(jié)點(diǎn)收到一個 -3，我們順勢向上跳?3 行，準(zhǔn)備繼續(xù)為下一個序列排序（jro right）。

3 號節(jié)點(diǎn)給 1 號棧放完 999 的哨兵后（mov 999 up）就一直在等待 2?號節(jié)點(diǎn)發(fā)送一個 1（jro left）。收到 1 表示序列中的所有數(shù)字都已經(jīng)有序地放在 1 號棧里了，這時候我們才能從棧里取數(shù)字并一一發(fā)往輸出口。每取一個數(shù)字，就將它減去 999（mov up acc, sub 999）并判斷是否為 0。不為 0 時，說明尚未取到末尾的 999 哨兵，此時加回 999 恢復(fù)成原數(shù)傳給 4 號節(jié)點(diǎn)（add 999, mov acc down），并跳回第?3?行繼續(xù)?。╦nz 3），直到取到最終的 999 哨兵后，1 號棧徹底空掉后，我們給 4 號節(jié)點(diǎn)發(fā)完最后的 0（jez 7, mov acc down）后，再給 2?號節(jié)點(diǎn)節(jié)點(diǎn)發(fā)送 -3，示意可以開始讀下一個序列了（mov -3?left）。

4 號節(jié)點(diǎn)直接無腦將 3 號節(jié)點(diǎn)傳來的數(shù)送往輸出端口即可（mov up down）。

點(diǎn)擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：

至此，我們終于把第一大章里的最難關(guān)卡搞定了，可喜可賀。

第 22 關(guān)《已存儲圖像解碼器》（Stored Image Decoder）關(guān)卡展示

本關(guān)的 IN 會給你一些數(shù)字，其中第奇數(shù)個數(shù)字表示線條長度，第偶數(shù)個數(shù)字表示顏色。設(shè)提供給你的數(shù)字是 w1, c1, w2, c2, ..., wn, cn。那么你需要從左上角 (0, 0) 點(diǎn)開始，依次：

• 畫一條長度為 w1，顏色為 c1 的水平線；

• 畫一條長度為 w2，顏色為 c2 的水平線；

• ……

• 畫一條長度為 wn，顏色為 cn 的水平線。

如果中途畫筆到達(dá)了右端點(diǎn)，則切換到下一行，回到左端點(diǎn)繼續(xù)畫（CRLF）。

本關(guān)的思路其實(shí)跟第 15 關(guān)畫國際象棋棋盤的思路有點(diǎn)像（傳送門：【TIS-100 攻略】第 14~17 關(guān)：測試圖 1、測試圖 2、曝光遮罩查看器、直方圖查看器）。只不過第 15 關(guān)的無限流提供的是 3、0 相間的數(shù)字，本關(guān)的無限流改為依次提供 w1 次 c1，w2 次 c2……一直到最終的 wn 次 cn 就好了。代碼如下：

上方的兩個節(jié)點(diǎn)純傳話。

左下角的節(jié)點(diǎn)將收到的 w 放入 acc 里（mov up acc），將收到的 c 放入 bak 里（swp, mov up acc, swp）。接下來我們要給右邊發(fā)送 w 次 c，每發(fā)送一次?c（swp, mov acc right, swp），就令 w 減去 1（sub 1）。此時判斷 w 是否減到了 0。尚未減到 0 時，跳回到第 5 行繼續(xù)發(fā) c（jnz 5），直到 w 減到 0 后，從上方接收新的 w 和 c。

右下角的節(jié)點(diǎn)跟第 15 關(guān)的代碼幾乎一樣，只是由于這次提供顏色的無限流在左邊，所以代碼里的 right 全部換成了 left。另外，本關(guān)的循環(huán)次數(shù)也由之前的 31 還原成了 30。除此之外，該節(jié)點(diǎn)的代碼和第 15 關(guān)一模一樣，沒有做任何改變。我就不再解釋了。

點(diǎn)擊左下角的【RUN】，稍等片刻，你的屏幕會突然被畫上一個神秘圖片，然后在你面前會呈現(xiàn)出一些難度更大的全新關(guān)卡。

以上圖片只有第一次通過本關(guān)后才會呈現(xiàn)。當(dāng)你后續(xù)再次通過本關(guān)時，就只會展示直方圖了。至此，恭喜你完成了第一大章的所有關(guān)卡，并解鎖 100 PERCENT V1 成就（Solve every puzzle in the TIS-100 SEGMENT MAP，解出 TIS-100 SEGMENT 地圖里的所有謎題）。