【TIS-100 攻略】TIS-NET 第 23~24 關(guān)：T20 節(jié)點(diǎn)模擬器、T31 節(jié)點(diǎn)模擬器
本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請注明出處。
我們翻閱數(shù)據(jù)手冊，可以發(fā)現(xiàn)數(shù)據(jù)手冊上有這么奇怪的兩頁：
手冊里提到了 T20 和 T31 這兩個(gè)特殊的節(jié)點(diǎn)，其中 T31 節(jié)點(diǎn)是“隨機(jī)訪問存儲器”（Random Access Memory, RAM）節(jié)點(diǎn)，T20 則是一個(gè)神秘節(jié)點(diǎn)，我們對它的內(nèi)部細(xì)節(jié)毫無所知。我們現(xiàn)在面臨的?TIS-NET?第 23、24 關(guān)則正好要求我們手動實(shí)現(xiàn)這兩個(gè)特殊的節(jié)點(diǎn)。
TIS-NET 第 23 關(guān)《T20 節(jié)點(diǎn)模擬器》（T20 Node Emulator）關(guān)卡展示
T20 節(jié)點(diǎn)有兩個(gè)輸入量：IN.I 和 IN.V，分別代表指令（instruction）和數(shù)值（value）。我們要為 T20 節(jié)點(diǎn)實(shí)現(xiàn)如下操作：
收到 0 指令時(shí)，讀入一個(gè)數(shù)值，將其存為 p；
收到 1 指令時(shí)，讀入一個(gè)數(shù)值，將其存為 q；
收到 2 指令時(shí)，交換 p 和 q；
收到 3 指令時(shí)，將 p 加上 q 并覆蓋原始的 p；
收到 4 指令時(shí)，將當(dāng)前的 p 值送往輸出口。
本關(guān)的代碼如下：
IN.V 下方的兩個(gè)節(jié)點(diǎn)接力將當(dāng)前的 value 發(fā)給中央節(jié)點(diǎn)（mov up down, mov up left）。
IN.I 下方的節(jié)點(diǎn)從 IN.I 處讀入一個(gè)指令?x，并將它映射為 2x+1 發(fā)給下方的中央節(jié)點(diǎn)（mov up acc, add acc, add 1, mov acc down）。原始指令 0、1、2、3、4 分別被映射成了 1、3、5、7、9 命令。
中央節(jié)點(diǎn)的 acc 用來存儲 p 的值，bak 用來存儲 q 的值。它隨時(shí)聽候上方節(jié)點(diǎn)的命令（jro up）：
收到命令 1 時(shí)，說明原始指令是 0。我們向下跳 1 行，從右邊讀入一個(gè)數(shù)值 v，視為 p，將其存入 acc 中（mov right acc, jmp 1）；
收到命令 3 時(shí)，說明原始指令是 1。我們向下跳 3 行，從右邊讀入一個(gè)數(shù)值 v，視為 q，將其存入 bak 中（swp, mov right acc, swp, jmp 1）；
收到命令 5 時(shí)，說明原始指令是 2。我們向下跳 5 行，交換 acc 和 bak（swp, jmp 1）；
收到命令 9 時(shí)，說明原始指令是 4。我們向下跳 9 行，將 acc 里的 p 值發(fā)給下方（mov acc down）；
以上四種命令沒啥好說的，都非常簡單。最麻煩的是收到命令 7 時(shí)的操作，此時(shí)原始指令是 3。我們向下跳 7 行，執(zhí)行令 p 加上 q 的操作。由于 bak 不能直接參與跟 acc 的運(yùn)算，所以我們得先將 bak 發(fā)到左邊的鄰居節(jié)點(diǎn)處暫存（swp, jmp c, mov acc left, swp），然后再從這個(gè)左邊鄰居處讀入 bak，累加到 acc 中（add left）。注意執(zhí)行第一條 swp 指令后，要強(qiáng)制跳到第 12 行繼續(xù)執(zhí)行，因?yàn)榈?10?行是收到命令 9 時(shí)的操作，收到命令 7 時(shí)不能執(zhí)行。
左邊的鄰居節(jié)點(diǎn)只有一條指令：mov right right。它的讀取目標(biāo)和寫入目標(biāo)都是 right，這意味著：當(dāng)右側(cè)節(jié)點(diǎn)向我們寫入一個(gè)數(shù)字時(shí)，我們將它暫存起來，并等待右側(cè)節(jié)點(diǎn)接下來發(fā)起讀請求時(shí)，將該數(shù)字原封不動地還給它。這就像在【踢皮球】：右側(cè)節(jié)點(diǎn)會首先會將 bak 中值為 q?的皮球踢過來，我們先接住；然后右側(cè)節(jié)點(diǎn)切換到 acc 時(shí)，會請求我們將 q 皮球踢回去，累加到 p 上。這時(shí)候我們原封不動地把 q 這個(gè)皮球踢回去就行了。
最下方的節(jié)點(diǎn)僅當(dāng)本次命令為 9?時(shí)才工作，將上方發(fā)來的 p 值送給 OUT（mov up down）。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
TIS-NET 第 24 關(guān)《T31 節(jié)點(diǎn)模擬器》（T31 Node Emulator）關(guān)卡展示
終于到了我們的隨機(jī)存儲器了。本題需要維護(hù)一個(gè)長度為 8 的 nums 數(shù)組（索引從 0 開始，8 個(gè)元素的索引分別為 0~7），然后：
當(dāng)你從 IN 收到 0 時(shí)，接著從 IN 里讀入兩個(gè)數(shù)字 i 和 v，然后將 nums[i] 的值設(shè)為 v；
當(dāng)你從 IN 收到 1 時(shí)，接著從 IN 里讀入一個(gè)數(shù)字 i，然后將?nums[i] 的值輸出給 OUT 口。
維護(hù)一個(gè)數(shù)組——有沒有覺得很眼熟？沒錯(cuò)，之前我們求眾數(shù)（傳送門：【TIS-100 攻略】TIS-NET 第 10 關(guān)：序列眾數(shù)計(jì)算器）以及計(jì)數(shù)排序（傳送門：【TIS-100 攻略】TIS-NET 第 20 關(guān)：超長序列排序器）的時(shí)候，都維護(hù)了一個(gè)頻數(shù)數(shù)組，用于記錄各個(gè)元素的出現(xiàn)次數(shù)。之前的這兩個(gè)關(guān)卡，我們已經(jīng)相當(dāng)于實(shí)現(xiàn)了一個(gè)小型的 T31 節(jié)點(diǎn)。本關(guān)我們則是要實(shí)現(xiàn)一個(gè)完整的 T31 節(jié)點(diǎn)。
本關(guān)的代碼如下：
首先看 IN 下方的節(jié)點(diǎn)：
初始化長度為 8 的 nums 數(shù)組，向上方的棧中放入 8 個(gè) 0（mov 8 acc）
（mov 0 left）
（sub 1）
（jnz 2）
接下來不斷將 IN 中的數(shù)字發(fā)給中間靠右的節(jié)點(diǎn)（mov up down）
（jmp 5）
然后看中間靠右的節(jié)點(diǎn)：
中間靠右的節(jié)點(diǎn)首先接收 0 或 1 的指令，將其放入 bak 暫存（mov up acc）
（swp）
然后，題目假設(shè)數(shù)組的索引是從 0 開始的，但是我們以往維護(hù)的都是以 1 索引起始的數(shù)組。這里我們還是按既往經(jīng)驗(yàn)來，將收到的 i 加上 1，得到真實(shí)的數(shù)組索引 j（mov 1 acc）
（add up）
并發(fā)給左邊（mov acc left）。
接下來，我們檢查 bak 中的命令值是 0 還是 1（swp）：
如果命令值為 1，則跳到第 11 行執(zhí)行（jnz b）
命令值是 0（存命令）時(shí)，需要從 in 讀取一個(gè)新的數(shù)值?v，并將 nums[j] 設(shè)置為 v。我們按順序執(zhí)行，給左邊發(fā)送一個(gè) 1 指令（mov 1 left），
并將新的 v 值一并發(fā)送給左邊（mov up left）
（jmp 1）
命令值是 1（取命令）時(shí)，需要輸出?nums[j] 的值。我們給左邊發(fā)送一個(gè) 3 指令（mov 3 left），
并將左邊傳來的 nums[j] 的值發(fā)給下方（mov left down）。
接下來看中間靠左的節(jié)點(diǎn)：
中間靠左的節(jié)點(diǎn)在收到右邊發(fā)來的 j 值后（mov right acc），
先令上方的棧彈棧 j 次（sav）
（mov up down）
（sub 1）
（jnz 3）
然后從下方棧的棧頂處獲得 nums[j] 的值，將其放入 acc（mov down acc）
并等待右邊節(jié)點(diǎn)發(fā)來新的命令（jro right）。
當(dāng)你收到了 1 指令時(shí)，說明要把?nums[j] 的值更新為 v。我們向下跳 1 行，將右邊發(fā)來的 v 值放入下方棧的棧頂（mov right down），
然后跳到第 12 行，避開 10~11 行的邏輯互斥的代碼（jmp c）。
當(dāng)你收到了 3 指令時(shí)，說明要將 nums[j] 的值發(fā)給右邊輸出。我們向下跳 3 行，將 acc 中的 nums[j] 值發(fā)給右邊（mov acc right），
然后 nums[j] 原樣放回下方棧的棧頂（mov acc down）。
操作完成后，下方的棧向上彈棧 j 次（swp）
（mov down up）
（sub 1）
（jnz d）
右下角節(jié)點(diǎn)沒啥好說的，遇到上方傳來的需要輸出的值時(shí)，無腦向下傳就 OK 了（mov up down）。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
優(yōu)化代碼行數(shù)
我們將以上代碼做一些微調(diào)，即可省去 6 行代碼，同時(shí)其他兩項(xiàng)指標(biāo)也不會惡化。
中間靠左的節(jié)點(diǎn)得到 nums[j] 的值后，將該值發(fā)往右邊，同時(shí)從右邊接收新的 nums[j] 的值，既存又取；
中間靠右的節(jié)點(diǎn)在收到指令 0（存指令）時(shí)，先丟棄掉左邊返回的 nums[j]，然后將讀到的?v 值發(fā)給左邊，作為新的 nums[j]；
中間靠右的節(jié)點(diǎn)在收到指令 1（取指令）時(shí)，將左邊返回的 nums[j] 存入 acc，向下方發(fā)一份后，將原始的 nums[j] 傳回去，相當(dāng)于讓左邊節(jié)點(diǎn)把 nums[j] 仍設(shè)置成之前的值。
優(yōu)化后的代碼如下：
上方和下方節(jié)點(diǎn)的代碼沒有任何變化。然后看中間靠右的節(jié)點(diǎn)：
中間靠右的節(jié)點(diǎn)首先接收 0 或 1 的指令，將其放入【acc】暫存（mov up acc）。
然后將上方發(fā)來的 i?值【直接發(fā)給左邊】（mov up left），由左邊去計(jì)算對應(yīng)的 j 值。
接下來，我們檢查【acc】中的命令值是 0 還是 1：若命令值是 1，跳到第 7 行執(zhí)行（jnz 7）。
命令值是 0（存命令）時(shí)，我們丟棄掉左邊發(fā)來的 nums[j] 的值（mov left acc），
然后將新的 v 值發(fā)給左邊，作為新的 nums[j]（mov up left）
（jmp 1）
命令值是 1（取命令）時(shí)，我們將左邊返回的 nums[j] 存入 acc（mov left acc），
原樣返回（mov acc left），
同時(shí)復(fù)制一份發(fā)給下方（mov acc down）。
接下來看中間靠左的節(jié)點(diǎn)：
首先將右方傳來的 i 加上 1 映射成 j（mov 1 acc）
（add right）
然后：令上方彈棧 j 次（sav）
（mov up down）
（sub 1）
（jnz 4）
將下方棧頂?shù)?nums[j] 發(fā)給右方（mov down right），
從右方接收新的 nums[j] 放入下方棧頂（mov right down），
令下方彈棧 j 次（swp）
（mov down up）
（sub 1）
（jnz a）
這樣的話，這個(gè)節(jié)點(diǎn)變成了【既存又取】的樣子，和具體的存取命令解耦了。另外，由于多出了許多代碼空間，所以 i 映射成 j 的操作可以由本節(jié)點(diǎn)親自完成，中央靠右的節(jié)點(diǎn)可以不占用自己的 bak 寄存器，少執(zhí)行了很多次 swp 指令，代碼行數(shù)進(jìn)一步減少。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
34 行代碼減少到了 28 行，同時(shí)其他兩項(xiàng)指標(biāo)也沒有增加。本方案完爆了上一版方案。
