【TIS-100 攻略】TIS-NET 第 3~5 關：取值范圍限制器、信號糾錯器、子序列提取器
本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請注明出處。
TIS-NET 第 3 關《取值范圍限制器》（Sequence Range Limiter）關卡展示
本關的 IN 會源源不斷地給你一些以 0 結(jié)尾的序列，你需要將序列中的每一個數(shù)字進行邊界檢查：如果序列中的數(shù)字高于 IN.H 指示的上限值，或低于 IN.L 指示的下限值時，將它修改為最近的邊界值輸出，否則直接原樣輸出。每個序列都對應一組不同的 IN.H?和 IN.L。
本關寫成 C 語言代碼的話非常簡單：
因為涉及到跟邊界值做比較，所以由既往經(jīng)驗可得，邊界值和原數(shù)中的一方需要提供兩遍。這里我們選擇提供兩遍邊界值。另外我們注意到題目中所有序列的長度都為 5，也就是說，同樣的 IN.H 和 IN.L 需要提供 10 遍后，才能切換為下一組數(shù)據(jù)。那么本關的代碼就很簡單了：
首先是右上角節(jié)點：
右上角節(jié)點將 acc 置為 IN.H（mov up acc），
將 bak 置為 10（swp）
（mov 10 acc）
（swp）
每提供一次 IN.H（mov acc left），
就令 bak 減去 1（swp）
（sub 1）并判斷是否減到了 0。
尚未減到 0 時，說明當前的 IN.H 沒有提供滿 10 次，跳回到第 4 行繼續(xù)提供（jnz 4），直到提供滿 10 次為止，跳回第 1 行讀取下一個 IN.H。
左上角節(jié)點的邏輯跟右上角類似，獲得 IN.L 的值，并向上方居中的節(jié)點提供 10 次。一筆帶過。現(xiàn)在看上方居中的節(jié)點：
上方居中的節(jié)點首先從 IN 里讀一個數(shù)字 nums[i]（mov up acc）。
如果讀到了 0，說明到達了序列末尾，直接跳到第 13 行輸出這個 0 即可（jez d, mov acc down）。
讀到非 0 值時，需要跟兩個邊界值各做一次比較。首先計算 nums[i] - H 的值（sub right），并令差值和 0 比大小。
若差值小于 0，則跳到第 7 行執(zhí)行（jlz 7）。
差值大于等于 0 時，說明?nums[i] 等于或高于上限值?H，nums[i] 需要強制縮小到上限值，此時我們強行用上限值 H?覆蓋 nums[i]（mov right acc）
并跳過第 7 行的互斥邏輯（jmp 8）。
差值小于 0 時，說明 nums[i] 低于上限值 H，nums[i] 不需要更新為上限值，此時加回一個 H（add right），將 acc 還原成 nums[i] 自身。
和上限值比較完后，我們需要將 nums[i] 再和下限值做一次比較。計算 nums[i] - L 的值（sub left），并令差值和 0 比大小。
若差值大于 0，則跳到第 12 行執(zhí)行（jgz 7）。
差值小于等于 0 時，說明 nums[i] 等于或低于下限值 L，此時我們強行用輸出下限值 L，忽略 nums[i] 自身的值（mov left?down）
并跳過第 12 行的互斥邏輯（jmp 1）。
差值大于 0 時，說明 nums[i] 高于下限值 L，nums[i] 不需要更新為下限值，此時加回一個 L，將 acc 還原成 nums[i] 自身（add left）
并輸出（mov acc down）。
中央節(jié)點和下方節(jié)點純傳話（mov up down）。
點擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
優(yōu)化運行速度
以上代碼做一點微小的調(diào)整即可提高 40% 的運行速度：
首先上方居中的節(jié)點對于兩個邊界值一直是迫不及待的狀態(tài)，所以左右兩側(cè)的節(jié)點可以改為把同樣的 mov acc left/right 連寫十遍，而不是使用循環(huán)計數(shù)的方法提供十遍。這樣雖然會增加代碼行數(shù)，但是省下了循環(huán)計數(shù)的時間，上方居中的節(jié)點可以更快地和邊界值做差值運算。
其次，上方居中的節(jié)點如果在和其中一個邊界值比較的時候，已經(jīng)被強制修正為邊界值了，那就沒有必要再和另一個邊界值做比較了，此時可以直接把另一側(cè)兩次提供的邊界值丟棄掉。優(yōu)化后的代碼如下：
左／右上角的節(jié)點沒啥好說的，原先用循環(huán)的方式將 L 和 H 提供十遍，現(xiàn)在變成了連寫十行同樣的代碼來提供（mov up acc, mov acc right/left * 10）。
上方居中的節(jié)點注意一下第 5~7 行，當 nums[i] - H >= 0 時，直接將 nums[i] 重置為右邊提供的 H 值（mov right acc），然后減去一個 L（sub left），再跳到第 13 行加上一個 L（jmp 13, add left），就相當于消耗掉了本輪兩次提供的?L 值，無需再多此一舉跟 L 比較一次。其他地方除了行號外，和上一版方案一致。
點擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
運行時長由 580 周期減少到了 327 周期，效率提升了 (580-327) / 580 ≈ 43.6%，很好。
TIS-NET 第 4 關《信號糾錯器》（Signal Error Corrector）關卡展示
你會從 IN.A 和 IN.B 收到兩個信號。通常情況下原樣輸出即可，但如果其中一路的信號為負數(shù)，則該路信號無效，改為輸出另一路的信號。題目保證兩路信號不會同時為負。本關的代碼如下：
IN.B 下方的節(jié)點將收到的 B?路信號匯總到左路（mov up left）。
IN.A 下方的節(jié)點先傳自己的 A 路信號（mov up down），再傳右邊發(fā)來的 B 路信號（mov right down）。
中央節(jié)點純傳話（mov up down）。
左下角節(jié)點將?A 路信號放入 bak（mov up acc, swp），再將 B 路信號放入 acc（mov up acc）。B 路信號為正數(shù)時，跳到第 7 行將 B 路信號原樣發(fā)給右邊的節(jié)點（jgz 7, mov acc right），否則 A、B 交換，將 A 路信號發(fā)給右邊的節(jié)點（swp, mov acc right）。接下來有兩種可能的情況：
B 路信號不正常，A、B 發(fā)生了交換：那么此時 acc 里放的是 A 路信號，bak 里放的是無效的 B 路信號（負數(shù)）。那么我們一定能判斷出 bak 是負數(shù)，我們直接將 acc 里的 A 路信號發(fā)給?OUT.A 就行了；
B 路信號正常，A、B 未發(fā)生交換，那么此時 acc 里放的是 B 路信號，bak 里放的是 A 路信號。我們判斷 bak 是否是負數(shù)，若是負數(shù)，說明 A 路信號無效，我們將 acc 里的 B 路信號值發(fā)給 OUT.A，否則直接將 bak 里的原始 A 路信號發(fā)給 OUT.A。
綜上所述，我們接下來只需要發(fā)現(xiàn) bak 是正數(shù)（swp），就輸出 bak（jgz a, mov acc down），否則輸出 acc（swp, mov acc down）就 OK 了。
右下角的節(jié)點會從左下角的節(jié)點處收到 B 路信號的輸出值，將該值送往下方的 OUT.B 即可（mov left down）。
點擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
優(yōu)化運行速度
以上方案的所有活都是左下角一個節(jié)點干的?，F(xiàn)在我們采用并行操作，讓右下角節(jié)點也同時干活，就能提高運行速度。優(yōu)化后的代碼如下：
上面的 4 個節(jié)點都純傳話（mov up down）。
下方的兩個節(jié)點都將自己的信號傳給對方，并接收（或丟棄）對方發(fā)來的信號。根據(jù)【一方發(fā)送信號的同時另一方必須接收】的原則，兩個節(jié)點必然有一個要選擇【先發(fā)自己的，再收對方的】，另一個要選擇【先收對方的，再發(fā)自己的】。如果兩個節(jié)點都選擇【先發(fā)后收】或【先收后發(fā)】，就會導致通訊失敗，程序阻塞。本程序里，左下角的節(jié)點采用了【先發(fā)后收】的策略，右下角的節(jié)點采用了【先收后發(fā)】的策略。
左下角的節(jié)點收到自己的信號后（mov up acc），先將自己的信號【發(fā)送】給右下角的節(jié)點（mov acc right），然后【接收或丟棄】對方的信號：如果我的信號是正數(shù)，那么跳到第 6 行，丟棄掉對方的信號，輸出我的信號（jgz 6, mov right nil, mov acc down）；如果我的信號是負數(shù)，則輸出對方的信號（mov right down, jmp 1）。
右下角的節(jié)點收到自己的信號后（mov up acc），先進行判定，并選擇【接收或丟棄】對方的信號：如果我的信號是正數(shù)，那么跳到第 5 行，丟棄掉對方的信號（jgz 5, mov left nil）；如果我的信號是負數(shù)，則接收對方的信號（mov left acc, jmp 6）。處理完畢后，再將自己的信號【發(fā)送】給左下角的節(jié)點（mov acc left）并輸出（mov acc down）。
這里要提一下，如果自己的信號是負數(shù)，那么由于執(zhí)行了第 3 行的 mov left acc，自己的負數(shù)信號會被對方的信號所覆蓋，最后傳過去的值并不是原始的負數(shù)信號。不過這不影響結(jié)果的正確性。因為兩路信號不會同時為負，如果你的信號是負數(shù)的話，對方的信號一定是正數(shù)，你不論傳什么，對方都會丟棄掉的。
一個先發(fā)后收，一個先收后發(fā)，配合得天衣無縫。點擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
運行時長由 418 減少到了 286，效率提升了 (418-286) / 286 ≈ 46.2%，這就是并行的力量。
TIS-NET 第 5 關《子序列提取器》（Subsequence Extrator）關卡展示
IN.S 會提供給你一些以 0 結(jié)尾的序列，然后你需要從 IN.I 里讀入兩個數(shù)字，設它們?yōu)?i 和 j。你需要將給定序列里第 i~j 個數(shù)字提取出來，將提取出的子序列發(fā)送給 OUT。
這里的索引是以 0 起始的，比如，當你收到 [74, 83, 30, 89, 0] 這樣的序列時，第 0 個數(shù)字是 74，第 1 個數(shù)字是 83，第 2 個數(shù)字是 30，第 3 個（最后一個）數(shù)字是 89。當你從 IN.I 讀到 0 和 1 時，你需要構(gòu)建一個由第 0~1 個數(shù)字組成的子序列，即輸出 [74, 83, 0]。
現(xiàn)在我們已知 i?和?j，要想提取出序列中的第 i~j?個數(shù)字，方法很明顯是這樣的：
舍棄掉序列中的第 0~i-1 個數(shù)字，即舍棄掉前?i?個數(shù)字；
索引 i~j 共有 j-i+1 個數(shù)字，連續(xù)提取這么多數(shù)字發(fā)送到輸出口后，輸出一個哨兵 0；
舍棄掉剩下的數(shù)字，直到遇見最終的哨兵 0 為止。
代碼很簡單，如下：
IN.I 下方的節(jié)點將收到的 i 和 j 都傳給右邊（mov up right）。然后看核心的右方節(jié)點：
右邊的節(jié)點首先收到的是 i（mov left acc），
將它復制一份到 bak 里備用（sav）。接下來的 13 行代碼用來依次完成三步曲：
舍棄掉 IN.S 里的前 i 個數(shù)字。首先檢查 i 是否已經(jīng)是 0。當 i 已經(jīng)是 0 時，跳過第一階段，直接跳到第 7 行進入第二階段（jez 7）。
當 i 尚未到達 0 時，我們每丟棄序列里的一個數(shù)字（mov up nil），
就令 i 減去 1（sub 1）并繼續(xù)判定 i 是否到達了 0。
尚未到達 0 時，跳回第 4 行繼續(xù)減（jnz 4），直到 i 減到 0 后，進入第二階段。
提取序列中接下來的 j-i+1 個數(shù)字并輸出。我們將 bak 里存的 i 拿出來（swp），
減去左邊發(fā)來的 j（sub left）。
此時 acc 里的值是 i-j，是起始索引減去終止索引，是個負數(shù)。所以這里我們要反其道而行之，每提取出序列里的一個數(shù)字（mov up down），
就令 acc 加上 1（add 1）并判斷 acc 是否加到了 0。
acc 尚未加到 0 時，跳回到第 9 行繼續(xù)?。╦nz 9），
直到 acc 加到 0 后，我們一共取了序列里的 j-i 個字符，還差一個字符沒取，此時我們將這最后的字符取出并輸出（mov up down），
然后輸出哨兵?0（mov 0 down），進入第三階段。
將序列中剩下的數(shù)字全部舍棄（mov up acc），
只要未遇見哨兵 0，就跳回第 14 行繼續(xù)丟（jnz e），直到遇見哨兵 0 為止。
中央節(jié)點和下方節(jié)點純傳話（mov up down）。
點擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
三項指標都在直方圖的最左端，看來是十全十美的解法了。
