【TIS-100 攻略】第 10~11 關(guān)：信號模式檢測器、序列峰值檢測器
本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請注明出處。
第 10 關(guān)《信號模式檢測器》（Signal Pattern Detector）關(guān)卡展示
本關(guān)的 IN 會源源不斷地提供數(shù)字。當(dāng)最近三個數(shù)字均為 0 時，向 OUT 發(fā)送 1；否則向 OUT 端口發(fā)送 0。
由于提供的數(shù)字都是非負(fù)數(shù)，所以可以用【求和法】檢查前三個數(shù)字是否都是 0：僅當(dāng)三者相加的和為 0 時，三者才均為 0。那么，本算法的難點就在于【如何存下最近的三個數(shù)】。本題的代碼如下：
上方的兩個節(jié)點純粹給中央節(jié)點傳話（mov up right, mov left down）。
然后是中央節(jié)點。
首先將第一個數(shù)存入 bak（mov up acc）
（swp）
再將第二個數(shù)存入 acc（mov up acc）。
從收到第三個數(shù)開始，就需要不斷往下傳【最近的三個數(shù)】，由下方來計算三者之和了。現(xiàn)在 acc 里存的是【前一個數(shù)】，bak 里存的是【前兩個數(shù)】。為了減少寄存器的交換次數(shù)，這里我們選擇先把【前一個數(shù)】往下傳（mov acc down），
再把【前兩個數(shù)】從 bak 換到 acc 里（swp）
并往下傳（mov acc down）。
傳完后，我們從上方收取【當(dāng)前數(shù)】，覆蓋掉已經(jīng)無用的【前兩個數(shù)】（mov up acc）
并往下傳（mov acc down）。
至此，acc 里存的是【當(dāng)前數(shù)】，bak 里存的是【前一個數(shù)】。那么在收到下一個數(shù)的時候，acc 和 bak 就理所當(dāng)然地變成了下一個數(shù)的【前一個數(shù)】和【前兩個數(shù)】，和之前的邏輯又完全對上了。因此，我們在這時跳回第 4 行，將這套邏輯無限循環(huán)下去（jmp 4）。
最后是下方節(jié)點。
首先無腦向下傳兩個 0（mov 0 down）
（mov 0 down）
并清空 acc（sub acc）。
接下來就要開始從上方收取【最近的三個數(shù)】了。我們將收到的三個數(shù)相加（add up）
（add up）
（add up）
并檢查和是否為 0。若和不為 0，則跳到第 2 行，向 OUT 傳一個 0 并清空 acc（jnz 2, mov 0 down, sub acc）。
若和為 0，則改為向 OUT 傳 1（mov 1 down）。
同時，由于此時 acc 已經(jīng)為 0，所以不需要再額外執(zhí)行清空 acc 的任務(wù)，直接跳到第 4 行（jmp 4）開始下一次的累加任務(wù)即可。
點擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
優(yōu)化運行時間和代碼行數(shù)
求和法是一種方案，但不是最好的解決方案。題目要求遇到 3 個或更多連續(xù)的 0 時輸出 1，那么我們就按字面意思來理解：我們用一個計數(shù)器記錄連續(xù) 0 的個數(shù)，并以此為依據(jù)輸出信號不就行了嗎，干嘛非得用求和法來做呢？
因此，我們將代碼由原先的【求和法】改為現(xiàn)在這樣的【計數(shù)法】：
上方的兩個節(jié)點都沒有變化，直接從中央節(jié)點開始看：
中央節(jié)點收到 IN 里的數(shù)字后（mov up acc），根據(jù)其是否為 0 向下發(fā)送不同的跳轉(zhuǎn)信號。
若收到的是非 0 值，跳到第 5 行（jnz 5）。
若收到的是 0 值，則向下傳 1（mov 1 down）。
傳完 1 后跳回第 1 行，避免執(zhí)行第 5 行的代碼（jmp 1）。
若收到的是非 0 值，則跳轉(zhuǎn)到此，向下傳 8（mov 8 down）。
然后我們看下方節(jié)點：
首先等待上方傳來的 1 或 8 信號（jro up）?，F(xiàn)在已知收到 0 值時向下跳 1 行，收到非 0 值時向下跳 8 行。
收到 0 值時，我們需要令計數(shù)器 +1，并判斷此時計數(shù)器是否 >= 3。判斷 acc + 1 >= 3 相當(dāng)于判斷 acc >= 2，相當(dāng)于判斷 acc > 1，相當(dāng)于判斷 acc - 1 > 0。因此這里我們令 acc - 1（sub 1），
然后判斷對應(yīng)的值是否大于 0。大于 0 時，跳轉(zhuǎn)到第 6 行執(zhí)行（jgz 6）。
第 4~5 行的代碼理所當(dāng)然地僅當(dāng) acc - 1 <= 0 時才會被執(zhí)行，此時 IN 里的確出現(xiàn)了連續(xù)的 0，但連續(xù)的數(shù)量尚未到達(dá) 3 個。我們需要向 OUT 傳 0（mov 0 down），
接下來無條件跳轉(zhuǎn)到第 7 行，跳過 jgz 判斷成立時執(zhí)行的第 6 行代碼（jmp 7）。
當(dāng) acc - 1 > 0 時，按照要求，程序跳轉(zhuǎn)到了第 6 行執(zhí)行，此時 IN 里出現(xiàn)了 3 個或更多的 0，向 OUT 傳 1（mov 1 down）。
傳值完成后，我們需要將 acc - 1 還原成 acc + 1，執(zhí)行 +2 指令便可還原（add 2）。
執(zhí)行完畢后，跳回第 1 行，避免執(zhí)行第 9 行的代碼（jmp 1）。
而如果一開始收到的是非 0 值，那么我們會從上方收到 8 信號。此時向下跳 8 行，跳轉(zhuǎn)到第 9 行，無腦向 OUT 傳 0（mov 0 down）
并重置計數(shù)器（sub acc）。
點擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
還能再快一點嗎？
如果計數(shù)器從 0 開始計的話，那么判斷計數(shù)器是否 >= 3 的過程非常繁瑣。那么我們不妨換一種思路：讓計數(shù)器從 -2 開始計，這樣每次只要 +1 并直接判斷是否 > 0 就 OK 了，不需要又減又加。最終版本的程序如下：
中央節(jié)點發(fā)送的跳轉(zhuǎn)偏移量由原先的 1、8 變成了 1、7。下方節(jié)點實實在在少了一行代碼。下方節(jié)點的邏輯變成了這樣：
首先將計數(shù)器置為 -2（mov -2 acc），
然后聽取上方的指示（jro up）。
收到 0 值時，檢查計數(shù)器是否到達(dá)了 0。已到達(dá) 0 時，跳到第 7?行（jez 7）；尚未到達(dá) 0 時，按順序執(zhí)行。
若計數(shù)器尚未到達(dá) 0，給 OUT 傳 0（mov 0 down）
并令計數(shù)器 +1（add 1）。
執(zhí)行至此跳回第 2 行，避免執(zhí)行后續(xù)代碼（jmp 2）。
若計數(shù)器到達(dá)了 0，說明此前已經(jīng)從 IN 收到了兩個 0，此時收到的自然是第三個 0，這時候我們當(dāng)然要給 OUT 傳 1（mov 1 down）。
與此同時，當(dāng)計數(shù)器到達(dá)了這個值以后，再計下去也是沒有意義的事情了，因為除非收到非 0 值將計數(shù)器重置，否則向下傳的數(shù)字都是 1。計數(shù)器不論是到達(dá) 0 還是到達(dá)更大的正數(shù)，我們對應(yīng)的行為都是一樣的，自然而然，計數(shù)器累加到 0 以后就沒有再繼續(xù)累加的必要了，直接跳回第 2 行等待下一次指令就 OK 了（jmp 2）。此時的計數(shù)器更像是一個 CD（冷卻）計數(shù)指示，冷卻完畢后的確沒有再繼續(xù)計數(shù)的必要了。
收到非 0 值時，向下跳 7 行，無腦給 OUT 傳 0，然后自動跳回第一行，將計數(shù)器重置為 -2（mov 0 down, mov -2 acc）。
點擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
最終的三項指標(biāo)為：運行時長 199，節(jié)點數(shù)量 4，代碼行數(shù) 16。
第 11 關(guān)《序列峰值檢測器》（Sequence Peak Detector）關(guān)卡展示
本關(guān)的 IN 會不斷提供一些以 0 結(jié)尾的序列，你需要將每個序列的最小值傳給 OUT.I，最大值傳給 OUT.A。本關(guān)的代碼如下：
上方的節(jié)點純粹向下傳話（mov up down）。
中央靠左的節(jié)點邏輯如下：
收到序列的第一個數(shù)字時（mov up acc）
先復(fù)制一份發(fā)給中間靠右的節(jié)點（mov acc right），
再向下傳一份（mov acc down）。
從第二個數(shù)字開始（mov up acc）
首先還是復(fù)制一份給中間靠右的節(jié)點（mov acc right），然后需要判斷收到的數(shù)字是否為 0，并以此為依據(jù)給下方節(jié)點發(fā)送不同的信號。
收到數(shù)字 0 時，說明達(dá)到了序列的結(jié)尾，跳到第 10 行代碼處（jez a）。
收到非 0 數(shù)字時，給下方發(fā)送 1 的信號值（mov 1 down），
再將當(dāng)前收到的數(shù)字發(fā)送兩遍。先發(fā)送第一遍（mov acc down），
然后跳回到第 3 行復(fù)用代碼，發(fā)送第二遍（jmp 3, mov acc down）。
收到 0 數(shù)字時，按照規(guī)定跳到第 10 行，給下方發(fā)送 5?的信號值（mov 5?down）。
中間靠右的節(jié)點的代碼跟中間靠左的節(jié)點基本一致，只做了兩處改動：①因為是從其左側(cè)收取 IN 的數(shù)據(jù)，所以該節(jié)點里所有的 up 都改成了 left；②由于不需要再向它的右邊傳話，所以所有的 mov acc right?指令都被注釋掉了。
下方的兩個節(jié)點收到的都是同樣的數(shù)據(jù)流，只不過左邊找的是序列里的最小值，右邊找的是序列里的最大值。我們把左邊的節(jié)點當(dāng)作典型來解釋這段代碼的含義。
首先，收到序列里的第一個數(shù)，將它設(shè)為迄今為止的最小值（mov up acc）。
接下來，上方節(jié)點會在收到非 0?值時發(fā)送一個 1 的信號，或在收到 0 值時發(fā)送一個 5?的信號。我們等待這個信號的出現(xiàn)（jro up）。
上方收到非 0 值時，我們會收到 1 信號，向下跳 1 行，計算歷史最小和新挑戰(zhàn)者的差值（sub up）。
若差值為正，說明挑戰(zhàn)者比歷史最小值還小，我們跳回第 1 行，將 acc（歷史最小）置為新的挑戰(zhàn)者的值（jmp 1, mov up acc）。
若差值為 0 或負(fù)，說明挑戰(zhàn)者沒有小過歷史最小值。此時我們不改寫歷史最小值，令其維持原狀。這里 acc 的值為【歷史最小 - 挑戰(zhàn)者】的值，所以我們需要在此基礎(chǔ)上令 acc【+ 挑戰(zhàn)者】，把 acc 的值恢復(fù)成歷史最小值（add up）。
執(zhí)行完第 5 步后，跳回到第 2 行，準(zhǔn)備接收序列里的下一個數(shù)字（jmp 2）?？梢钥吹?，對于每個挑戰(zhàn)者的值，下方節(jié)點都需要讀兩遍，一遍用于計算和歷史最小值的差值，另一遍用于更新或維持最小值。所以上方節(jié)點僅在收到序列里的第一個數(shù)時向下傳一遍，從第二個數(shù)開始，每個數(shù)都要向下傳兩遍。
上方收到 0 值時，我們會收到 5 信號，向下跳 5?行。因為 acc 記錄的是歷史最小，當(dāng)?shù)竭_(dá)序列末尾時，歷史最小就成了全局最小。我們直接將 acc 中記錄的全局最小值向下輸出，即完成任務(wù)（mov acc down）。然后跳回第 1 行，準(zhǔn)備收取下一個序列里的第一個數(shù)。
下方靠右的節(jié)點求的是序列里的最大值，acc 里存的是歷史最大，不再是歷史最小。另外第 4 行的 jgz 1 改成了 jlz 1。求最大值時，仍然是計算歷史最大值和挑戰(zhàn)者的差值。差值為負(fù)時，說明挑戰(zhàn)者比歷史最大值還大，此時需要更新歷史最大值；差值為 0 或正時，說明挑戰(zhàn)者比歷史最大值小，此時需要維持歷史最大值不變。該節(jié)點代的邏輯正好是左邊節(jié)點的相反邏輯，所以將第 3 行的條件翻轉(zhuǎn)一下就 OK 了，其余的代碼都不需要改變。
點擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：
