【TIS-100 攻略】TIS-NET 第 17 关：动态模式检测器

2022-11-09 17:37 作者:ココアお姉ちゃん 0人读过 | 我要投稿

本文首发于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原创不易，转载请注明出处。

TIS-NET 第 17 关《动态模式检测器》（Dynamic Pattern Detector）关卡展示

本关的 IN.P 会给你一个模式序列，以 0 结尾，不过测试发现长度固定为 3。

然后 IN.S 会给你源源不断地提供一些数字，仅当包括当前数字在内的近 3 个数字和 IN.P 完全匹配时，向 OUT 输出 1，否则向 OUT 输出 0。

本关没有栈，同时还需要用节点记住 p[-2]、p[-1]、p[0]、s[-2]、s[-1]、s[0] 这六个值，和上一关相比甚至还要多记一个值。有点累了，干脆换一种方法——把连续的三个值映射成一个特征值（hash），然后对特征值进行判等。这样子的做法，虽然有概率会出错，但是写起来不费劲，而且最终的运行效率很高。

这里，我们使用公式 $hash(x)%20%3D%204x_%7B-2%7D%20%2B%202x_%7B-1%7D%20%2B%20x_%7B0%7D%20$ ，将 p[-2]、p[-1]、p[0] 映射成特征值 4p[-2] + 2p[-1] + p[0]，将 s[-2]、s[-1]、s[0] 映射成特征值 4s[-2] + 2s[-1] + s[0]，然后比较两个特征值是否一致。原先需要比较三组数是否一致，现在就只需要比较一组数了。

以上算法有概率得出错误的结论。随便举一个反例：假如 p 序列是 [1, 2, 3]，s 序列是 [1, 3, 1] 时，计算可得 p 序列的特征值是 4×1 + 2×2 + 3 = 11，s 序列的特征值是 4×1 + 2×3 + 1 = 11，两者的特征值相等，但两者很明显不是同一个序列。

本关的代码如下：

IN.P 下方的节点接收 p[-2]、p[-1]、p[0] 的值，然后计算该序列的 hash 值：

计算完成后，不断向右边提供该常数（mov acc right, jmp 6）。

该节点右边的节点纯粹充当传输 hash(p) 的桥梁（mov left right）。

IN.S 下方的节点用来向下传输 s[-2]、s[-1]、s[0] 和 hash(p) 的值。这里用到了和上一关类似的滚动存储法来维护序列中最近 3 个数的值。只是由于本关只需要维护前两个数，所以复杂度相比于上一关大幅减少：

节点 B 存储 s[-2]，节点 A 存储 s[-1]、IN.S 存储 s[0]

第 3 步，节点 B 向节点 C 发送 s[-1]，节点 A 从 IN.S 接收 s[0]

具体到代码上：

A 节点将 s[-1] 传下去后（mov acc down），
用 s[0] 覆盖 s[-1]（mov up acc）
并往下传（mov acc down），
最后传 hash(p)（mov left down）。

然后：

B 节点向 C 节点传完 s[-2] 后（mov acc down），
将 A 节点发来的 s[-1] 覆盖 s[-2]（mov up acc）
并传给 C（mov acc down），
再接下来的 s[0]（mov up down）
和 hash(p) 则直接传给 C，不保存（mov up down）。

右下角的节点会依次收到 s[-2]、s[-1]、s[0] 和 hash(p)，首先根据前 3 个值计算 hash(s)：

计算完成后，和后面发来的 hash(p) 做差值运算（sub up）。只要差值不为 0，就说明 hash(s) 和 hash(p) 不相等，跳到第 10 行向 OUT 发送 0（jnz a, mov 0 down）；差值为 0 时，说明 hash(s) 和 hash(p) 相等，向 OUT 发送 1（mov 1 down, jmp 1）。

点击左下角的【RUN】，运行程序。本算法是投机取巧的算法，前三个固定的测试样例能通过，但是最后的随机样例会有概率不通过：

如上图所示，序列 [39, 33, 37] 和序列 [37, 39, 33] 不一样，但因为特征值一样：4×39 + 2×33 + 37 = 4×37 + 2×39 + 33 = 259，所以错误地输出了一个 1。遇到这样的情况，请点击左下角的【STOP】停止运行，然后再点击【RUN】重新运行一遍。随便试几次就能过了。