【TIS-100 攻略】第 12 關(guān)：序列反轉(zhuǎn)器
本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請(qǐng)注明出處。
第 12 關(guān)《序列反轉(zhuǎn)器》（Sequence Reverser）關(guān)卡展示
本關(guān)的 IN 會(huì)不斷提供一些以 0 結(jié)尾的序列。你需要反轉(zhuǎn)讀到的序列，并將反轉(zhuǎn)后的序列輸出。注意反轉(zhuǎn)后的序列也要保持以 0 結(jié)尾，比如，當(dāng)你讀到 1、2、3、4、5、0 時(shí)，你需要輸出 5、4、3、2、1、0。
本關(guān)我們需要用到一個(gè)特殊的節(jié)點(diǎn)：棧存儲(chǔ)節(jié)點(diǎn)（Stack Memory Node）。普通節(jié)點(diǎn)里只有 acc 和 bak 兩個(gè)寄存器可以存儲(chǔ)額外的數(shù)字，而且使用上會(huì)有很多限制：acc 被三條算術(shù)指令和四大條件跳轉(zhuǎn)指令所依賴，難以恒久地存儲(chǔ)一個(gè)值；而 bak 雖然可以恒久地存儲(chǔ)一個(gè)值，但是使用上非常不便，需要通過 swp 指令換到 acc 里，使用完畢后再 swp 回去。同時(shí) bak 里的值還不能直接參與跟 acc 的運(yùn)算，也不能和 acc 比大小。
除了使用節(jié)點(diǎn)自身的 acc 和 bak 來存值以外，我們還可以把值存到鄰居節(jié)點(diǎn)里，并在需要的時(shí)候，委托鄰居節(jié)點(diǎn)把存儲(chǔ)的值傳來。但是這樣做依舊有很多不便：
首先你要清楚地知道存在鄰居節(jié)點(diǎn)里的值我需要讀幾次。當(dāng)你把值存入鄰居節(jié)點(diǎn)后，再想拿出來就必須要通過同步通訊的方式來取，鄰居發(fā)幾次，我收幾次，必須完全一致，任何一方多了少了都不行，輕則讀取到錯(cuò)誤的數(shù)據(jù)，重則直接導(dǎo)致程序被徹底阻塞住。
其次一個(gè)普通節(jié)點(diǎn)在任何時(shí)候要么只收數(shù)據(jù)，要么只發(fā)數(shù)據(jù)，兩項(xiàng)任務(wù)不能同時(shí)完成。所以如果你要把一個(gè)鄰居節(jié)點(diǎn)配置成收發(fā)兩用節(jié)點(diǎn)的話，這個(gè)鄰居節(jié)點(diǎn)的第一行需要寫一條 jro 指令用于接收【收／發(fā)】的命令信號(hào)，同時(shí)你自己在從鄰居節(jié)點(diǎn)里取值時(shí)，也需要先給一個(gè)【收／發(fā)】的命令信號(hào)，再執(zhí)行【存／取】的任務(wù)。這樣的話代碼行數(shù)往往會(huì)捉襟見肘。
從本關(guān)開始出現(xiàn)的棧節(jié)點(diǎn)就是為了解決以上問題而出現(xiàn)的：首先它有額外的 15 格存儲(chǔ)空間，可以用來存儲(chǔ)大量短時(shí)間內(nèi)無法送往輸出口的數(shù)據(jù)；其次這個(gè)節(jié)點(diǎn)里的數(shù)據(jù)可以隨時(shí)讀取或?qū)懭?，不需要向普通?jié)點(diǎn)那樣同步通訊。
那么問題來了：當(dāng)我往棧里存入了大量的數(shù)據(jù)后，如果這時(shí)我讀取棧里的數(shù)據(jù)，我怎么知道我讀到的是哪個(gè)數(shù)？這就不得不仔細(xì)說明一下棧這個(gè)數(shù)據(jù)結(jié)構(gòu)了：棧是一個(gè) FILO（First In Last Out，先進(jìn)后出）的數(shù)據(jù)結(jié)構(gòu)，越先存入的數(shù)據(jù)越靠后被取出。這就像一個(gè)儲(chǔ)物柜一樣：當(dāng)你在一個(gè)柜子里塞滿了物品后，最先放入的物品會(huì)被壓到最里面，而最后放入的物品在最外面。當(dāng)你想把東西取出來時(shí)，肯定是在外層的，最后放入的物品先取出，隨著外層的物品不斷被取出，里層的物品逐漸暴露出來，直到最后將第一件放進(jìn)去的物品拿出來。
同時(shí)你肯定也發(fā)現(xiàn)了：我們從棧里把存進(jìn)去的數(shù)字取出來時(shí)，得到的數(shù)字序列正好跟原始序列完全反過來。所以這道題我們先用棧將輸入序列里的數(shù)存起來，當(dāng)?shù)竭_(dá)序列末尾時(shí)，再將棧里的數(shù)字一一取出，得到的就是反轉(zhuǎn)的序列了。本題的代碼如下：
上方節(jié)點(diǎn)和兩個(gè)中央節(jié)點(diǎn)純傳話（mov up down, mov up right, mov left down）。
然后我們看右下角的節(jié)點(diǎn)：
首先給棧里塞了一個(gè) 0（mov 0 left），這個(gè) 0 是一個(gè)【哨兵】，是用來兜底的。我們?cè)趶臈＠锶?shù)字的時(shí)候，如果棧里沒有數(shù)字，那么程序會(huì)因?yàn)闊o法從棧里取到數(shù)字而阻塞住，直到另外一個(gè)節(jié)點(diǎn)給棧里塞了一個(gè)數(shù)字，阻塞才能解除。我們放入的這個(gè) 0，就是為了在后期取數(shù)字的時(shí)候通知操作的節(jié)點(diǎn)：你已經(jīng)取到了最后的 0，不要再繼續(xù)取了，否則我就沒有數(shù)字可以提供給你了。
放入 0 這個(gè)哨兵后，我們會(huì)從上方源源不斷地收到新數(shù)字。收到新數(shù)字后（mov up acc），我們檢查這個(gè)收到的數(shù)字是否是標(biāo)志著序列結(jié)束的 0。
若是 0，則跳到第 6 行去執(zhí)行（jez 6）。
若不是 0 時(shí)，說明這個(gè)數(shù)字是序列的一部分，我們將收到的數(shù)字存入棧里（mov acc left），
然后跳回第 2 行，繼續(xù)從上方收取新的數(shù)字（jmp 2）。如此反復(fù)，直到收到 0 為止，進(jìn)入下一段過程。
第 6~8 行是從棧里取出數(shù)字并向 OUT 口輸出的過程。我們從棧里取出數(shù)字放到 acc 里（mov left acc），
并將該數(shù)字送往下方的 OUT 口（mov acc down）。
此時(shí)我們判斷剛才取到的數(shù)字是否是哨兵 0。若不是哨兵 0，說明棧里還有別的待取出的數(shù)字，跳回到第 6 行繼續(xù)?。╦nz 6），直到取到最終的 0 為止。棧里所有的數(shù)字都取出來后，回到第 1 行，開始執(zhí)行下一次任務(wù)。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會(huì)彈出結(jié)算界面：
三項(xiàng)指標(biāo)都在直方圖的最左端，以上方案是十全十美的方案。
解鎖成就 NO MEMORY
該成就的說明是 Solve SEQUENCE REVERSER without writing any values to a stack memory node，不往棧里寫入任何數(shù)字完成本關(guān)。
看來本關(guān)的十全十美解法太容易拿了，Zachtronics 官方選擇了給該題增加第四種指標(biāo)，強(qiáng)行不給十全十美。
如果不能用棧存，那就只能用節(jié)點(diǎn)存了。好在本題給的所有序列都不會(huì)超過 5 個(gè)數(shù)字，我們想辦法用 5 個(gè)節(jié)點(diǎn)把這 5 個(gè)數(shù)字存下來就好了。代碼如下：
不使用棧的話，本關(guān)需要用 6 個(gè)節(jié)點(diǎn)，其中 5 個(gè)用于存儲(chǔ)序列，1 個(gè)用于輸出，沒有純傳話的節(jié)點(diǎn)。為了方便說明，我給上方的 5 個(gè)節(jié)點(diǎn)編了號(hào)。
每個(gè)節(jié)點(diǎn)都使用 acc 來接受 IN 的輸入，用 bak 寄存器來存儲(chǔ)值。那么我們首先看 1 號(hào)節(jié)點(diǎn)：
首先將 IN 里的值讀入 acc（mov up acc），然后判斷該值是否是 0。
如果是 0，則跳到第 8 行執(zhí)行（jez 8）。
讀入的值不為 0 時(shí)，說明我們要將該值存入序列里。1 號(hào)節(jié)點(diǎn)先使用交換指令將 bak 的值拿出來（swp），檢查 bak 是否為 0。
如果 bak 為 0，說明 bak 之前并沒有存入一個(gè)值，我們之前的 swp 指令正好將該值存入了 bak，直接跳回第 1 行接收下一個(gè)值即可（jez 1）。
如果 bak 不為 0，說明 1 號(hào)節(jié)點(diǎn)的 bak 已經(jīng)有值了，那么新拿到的這個(gè)值必須交給后面的節(jié)點(diǎn)來保存。我們將剛才收到的值重新?lián)Q出來（swp），
然后交給 2 號(hào)節(jié)點(diǎn)來處理（mov acc left）。
以上代碼執(zhí)行完畢后，強(qiáng)制跳回第 1 行，避免執(zhí)行后續(xù)代碼（jmp 1）。
如果從 IN 里收到的值是 0，說明該輸出序列了。此時(shí)將 0 信號(hào)通知給 2 號(hào)節(jié)點(diǎn)（mov 0 left），讓它一傳十十傳百，直到最終通知所有的節(jié)點(diǎn)將自己存儲(chǔ)的值拿出來。
通知完畢后，1 號(hào)節(jié)點(diǎn)將自己的 bak 里存儲(chǔ)的數(shù)字拿出來發(fā)給左邊（swp）
發(fā)給左邊（mov acc left）。
接下來看 2 號(hào)節(jié)點(diǎn)。2 號(hào)節(jié)點(diǎn)收到信號(hào)時(shí)，要么收到了序列里的第二個(gè)數(shù)字（非 0），要么收到了輸出的廣播信號(hào)（0）。2 號(hào)節(jié)點(diǎn)的前 7 行代碼除了方向跟 1 號(hào)節(jié)點(diǎn)不一樣之外，其余邏輯是一樣的：收到正數(shù)時(shí)把 acc 和 bak 進(jìn)行交換，檢查換出來的數(shù)字是否為 0。換出來的數(shù)字為 0 時(shí)，說明 bak 原先為空，剛才的一次交換操作正好把收到的數(shù)字放到了 bak 里；換出來的數(shù)字不為 0 時(shí)，說明 bak 原先不為空，我們需要把剛才收到的數(shù)字再換出來，交給 3 號(hào)節(jié)點(diǎn)處理。最開始收到的數(shù)字為 0 時(shí)，跳到第 8 行，將 0 信號(hào)再發(fā)給 3 號(hào)節(jié)點(diǎn)，一傳十十傳百，然后依次把自己 bak 里的數(shù)字（第二個(gè)數(shù)字）和 1 號(hào)節(jié)點(diǎn)發(fā)來的數(shù)字（第一個(gè)數(shù)字）傳給 3 號(hào)節(jié)點(diǎn)。
3、4 號(hào)節(jié)點(diǎn)大同小異，到了 5 號(hào)節(jié)點(diǎn)時(shí)，如果需要存儲(chǔ)數(shù)字，就不需要再判斷 bak 是否為 0 了，直接一個(gè) swp 存進(jìn)去就 OK 了。而取數(shù)字的時(shí)候，我們要依次向下發(fā)送第 5~1 個(gè)數(shù)字。所以是先用 swp 指令把 bak 里存的第 5 個(gè)數(shù)字換出來發(fā)給下面（swp, mov acc down），再從左邊依次接收傳來的第 4~1 個(gè)數(shù)字發(fā)給下面（mov left down * 4）。
最后是下方的 6 號(hào)節(jié)點(diǎn)。它收到信號(hào)時(shí)肯定是雷打不動(dòng)地收到 5 個(gè)數(shù)字，當(dāng)序列不足 5 個(gè)數(shù)字的時(shí)候，會(huì)出現(xiàn)前導(dǎo) 0。因此我們不能將收到的數(shù)字直接往下傳，必須要判定，只有收到了非 0 數(shù)字才能往下傳。
同樣的邏輯我們要循環(huán)執(zhí)行 5 遍，因此我們先將 bak 置為 5（mov 5 acc）
（swp）
然后我們從上方接收一個(gè)數(shù)字放入 acc 中（mov up acc），并判斷收到的數(shù)字是否為 0。
收到的數(shù)字為 0 時(shí)，直接跳到第 6?行，不輸出這個(gè) 0 數(shù)字（jez 6）；
僅當(dāng)收到的數(shù)字為非 0 時(shí)，才將這個(gè)數(shù)字發(fā)給 OUT（mov acc down）。
每接收一個(gè)數(shù)字，我們就令 bak -1（swp）
（sub 1）
并判斷 bak 是否減到了 0。如果尚未減到 0，跳回到第 2 行，再執(zhí)行一次 swp 指令將 bak?換回去，并準(zhǔn)備從上方接收下一個(gè)數(shù)字（jnz 2, swp, mov up acc）。
如此反復(fù)，直到 bak 減到 0 后，向 OUT 輸出序列終止標(biāo)記 0（mov 0 down）。
點(diǎn)擊左下角的【RUN】，稍等片刻，待彈出結(jié)算界面后，便可解鎖 NO BACKUP 成就。
解鎖成就 BUSY LOOP
目前為止，第一關(guān)的這個(gè)成就我們還沒有解鎖。這個(gè)成就的說明是 Solve SELF-TEST DIAGNOSTIC in over 100,000 cycles，要求花費(fèi)十萬以上的運(yùn)行周期完成第一關(guān)。
本關(guān)我們知道了怎樣使用循環(huán)結(jié)構(gòu)將同樣一份邏輯執(zhí)行多次。以上代碼我們使用 bak 作為計(jì)數(shù)器，令節(jié)點(diǎn)在 bak 從 5 減到 0 的過程中反復(fù)執(zhí)行同樣一段邏輯。同樣的套路我們也可以用在第一關(guān)：隨便一個(gè)節(jié)點(diǎn)，先把 999 到 0 之間的數(shù)字默念一遍，然后再開始傳話，用這樣的方法拖時(shí)間，想拖多久就拖多久。代碼如下：
IN.A 下方的節(jié)點(diǎn)先將 acc 置為 999（mov 999 acc），
然后減 1（sub 1）并判定 acc 是否減到了 0。
尚未減到 0 時(shí)，跳回到第 2 行繼續(xù)減，直到 acc 減到 0 為止（jnz 2）。這樣的話，同樣的減 1 操作就會(huì)被執(zhí)行 999 次。
第 4~6 行的邏輯跟第 1~3 行完全一致，再從 999 減一遍純粹是為了拖時(shí)間。
施法前搖唱完后，再將 IN.A 口的數(shù)字往后傳（mov up left）。遇到下一個(gè)數(shù)字時(shí)，也是用同樣的方法拖時(shí)間。
由于至少要花十萬個(gè)周期才能完成，這時(shí)候我們別點(diǎn)左下角的【RUN】，直接點(diǎn)【FAST】快速運(yùn)行。漫長的兩分鐘過去后，結(jié)算界面終于彈出，你也就相應(yīng)地解鎖了 BUSY LOOP 成就。
