【深圳 IO 攻略】第 26 关：电子门锁

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

关卡展示

本关的读卡器会不定期地发送一些长度为 10 的数据包。收到数据包时，若【学习】信号处于激活状态，则将门锁密码更改为刚才收到的 10 位数字。若【学习】信号处于非激活状态，则表示尝试用对应密码的房卡开锁。仅当房卡密码与门锁密码一致，或房卡密码为 9999999999（10 个 9）时才能打开房门，生成时长 6 秒的解锁信号。题目保证【学习】时不会将门锁密码置为万能密码 9999999999。

这道题我们分两部分完成。首先完成【学习】信号激活时存储新密码的部分。

第一块芯片连接读卡器需要用掉一个 x 口，连接 RAM 需要用掉两个 x 口，至此已经占用掉了三个 x 口。因此，第一块芯片已经不可能用 MC4000，要么 MC4000X，要么 MC6000。这里我们还剩下一个 p 口的【学习】信号需要连接。考虑到只有 7 行代码，且没用到 dat 寄存器，这里我们选择使用 MC4000X 型号的芯片，同时再用一块 DX-300 将【学习】p 信号转成 x 信号。因为 MC4000X + DX-300 组合可以比单纯的 MC6000 省下 1 块钱的成本。

首先我们等待读卡器将芯片唤醒（slx x0）。唤醒后将 RAM 的地址口清零，准备读取或写入卡号（mov 0 x3）。此时检查学习信号是否处于激活状态（tcp x1 0）。若不处于激活状态，则表明当前不处于学习状态，而处于开房状态。而判定开房与否，不是这块芯片的工作，是之后放在右侧的芯片的工作。对于左侧芯片来说，关闭一切 + - 号指令，直接跳到最后睡觉就完事了（slp 6）。仅当学习信号处于激活状态时，才轮到这块芯片干事。我们需要不断将读卡器中的数字写入 RAM。每写入一位卡号（+ mov x0 x2），就检查是否存满了 10 位数（+ tlt x3 10）。尚未存满 10 位数时，跳回到第 4 行继续存（+ jmp 4），直到存满 10 位数后，休眠 6 秒（slp 6），等待下一个数据包。

现在开始尝试写解锁部分的代码。满足以下条件之一即可解锁：①房卡密码与 RAM 中前 10 位完全对应；②房卡密码是 9999999999。那么，我们可以使用位运算的方法来判断两个条件是否满足任意一个。当任意一位数不是 9 时，就将个位置 1，不再回 0；当任意一位数与 RAM 无法对应时，就将十位置 1，不再回 0。10 位数字都判断完之后，如果最终 acc 的值是 11（房卡密码既不与 RAM 完全对应，又出现了至少一个非 9 数字），那么就不开门。如果是其他的值，那么就开门。

最终的电路图和代码如下：

注意一下电路图里的导线。读卡器既和左侧芯片的 x0 相连，又和右侧芯片的 x3 相连。但是因为两块芯片最多只会有一块处于工作状态，不会同时处于工作状态，所以在读卡号时不会出现两块芯片竞争读取的现象，也就不会导致最终读取到错误的卡号。

然后是 RAM 的地址口和数据口。左侧芯片的 x3，以及右侧芯片的 x0 都连在了 RAM 的 a0 口上；左侧芯片的 x2，以及右侧芯片的 x1 都连在了 RAM 的 d0 口上，也就是说，虽然 RAM 提供了左右两个数据指针，但是这里，我们选择了左右芯片共享同一个数据指针。可为什么要这样做呢，明明右边连 a1 和 d1 更美观一点啊？因为这样做实属无奈。因为卡号是 10 位，不是 14 位，所以我们在读/写 RAM 前，都是需要将 RAM 指针归零的，否则会读到错误的卡号／将卡号写在错误的位置上。而右侧芯片的代码逻辑已经写满了整整 14 行，无法再多容纳哪怕“将地址清零”这样一行代码。所以我们在这里选择了这样的一种行为模式：两块芯片共享同一个数据指针，一旦读卡器有信号传来，就由左侧的芯片统一将指针归零。这样右边的芯片就可以省下关键的一行“将 a1 指针清零”的代码。

现在开始看代码。首先我们等待读卡器将芯片唤醒（slx x3），唤醒后检查学习信号是否处于激活状态（tcp x2 0）。若处于激活状态，说明现在正处于设置新密码的状态。而这些事是左侧芯片的工作，右侧芯片这时候只需要跳到最后去睡觉就完事了（+ jmp d）。仅当学习信号不处于激活状态时，才轮到这块芯片干事。此时我们需要从读卡器中读取一位数。因为收到的这一位数需要判断两次，先判断是否是 9，再判断是否与 RAM 里的数字对应。所以我们需要先将它缓存到 dat 寄存器里（mov x3 dat）。缓存完后，首先判断这位数是否是 9（teq dat 9）。如果是 9，不改变个位数。一旦出现非 9 数字，就将个位数置为 1（- dst 0 1）。再判断这位数是否与 RAM 里对应位置的数一致（teq dat x1）。一致时，不改变十位数。一旦出现不一致的数字，就将十位数置为 1（- dst 1 1）。至此，判断 RAM 的指针是否小于 10（tlt x0 10）。如果小于 10，就说明仍有等待接收的数字，跳回到第 4 行继续接收（+ jmp 4），直到 10 个数字全部接收完毕后，判断 acc 的值是否是 11（teq acc 11）。如果 acc 是 11，说明密码【既不和 RAM 中的数字一致，又出现了至少一位非 9 数字】，直接睡觉，不开房门（slp 6）。如果 acc 不是 11，就说明【密码一致】、【密码全 9】两个条件至少满足一个，打开房门（- mov 100 p1, slp 6）。做完以上操作后，将 acc 和解锁信号都清除，等待下一次开门任务的来临（mov p1 acc）。

点击左下角的【模拟】，稍等片刻，便会弹出结算界面：

优化成本和代码行数

其实即使是 21 行代码，也是可以压缩到 14 行，合并到一块 MC6000 里的。关键的操作在于【逻辑合并】，即使处于学习状态，我也照样进行位运算。只需要学习状态下，每一位密码都“视为和原密码不一致”，恒定地将十位置为 1 即可。这样就不用害怕会“错误地打开房门”了。电路图和代码如下：

首先我们等待读卡器将芯片唤醒（slx x0）。唤醒后，我们读取一位数字，并放到 dat 里（mov x0 dat）。首先判断这位数字是不是 9（teq dat 9），若是 9，则无事发生；若不是 9，则将 acc 的个位置 1（- dst 0 1）。接下来，我们检查当前是否处于学习状态（teq p0 0）。处于学习状态时，覆盖 RAM 对应位置原先的数，并一律视为和原先的数不相等，直接将 acc 的十位置 1（- mov dat x2, - dst 1 1）。不处于学习状态时，我们从 RAM 中读取一位数，并判断 dat 是否与之一致（+ teq dat x2）。一致时，无事发生；不一致时，将 acc 的十位置 1（- dst 1 1）。每读／写完一位数，就判断 RAM 的指针是否小于 10（tcp x3 10）。如果小于 10，就说明仍有等待接收的数字，跳回到第 2 行继续接收（- jmp 2），直到 10 个数字全部接收完毕后，判断 acc 的值是否是 11（teq acc 11）。如果 acc 是 11，可能是处于学习状态，还可能是密码既不是全 9，又与门锁密码不一致。不论是上面所说的两种情况中的哪种，我们都不开门。仅当不处于学习状态时，房卡密码【与门锁密码一致】、【是全 9】满足两者之一时，打开房门（- gen p1 6 0）。做完这些事后，将用于位运算的 acc 和用于读／写密码的 RAM 地址全部归零，准备迎接下一次任务（mov 0 x3, sub acc）。

本方案里，耗电上升到了 484。这是因为，我们将【学习】和【开房】的逻辑做了大规模合并，在【学习】的过程中我们做了很多多余的操作：①学习时我们依然跟开房时一样，将数据包中的数放入 dat 缓存；②学习时我们依然跟开房时一样在进行位运算，并以位运算的结果作为最后是否应该开门的判定依据；③为了压缩到 14 行代码，开门时使用了 gen 指令，涵盖在其中的 mov 0 p1 和 slp 0 这两条“空操作”指令带来了额外的电量消耗；④因为学习的过程中依然跟开房时一样用到了 acc 和 dat，所以学习结束后依然要清除这两个寄存器。以上，我提到了三次“跟开房时一样”，这就是【逻辑合并】的表现。逻辑合并固然带来无谓的电量消耗，但好处是我们成功将代码压缩到了 14 行，成功将代码放进了一块 MC6000 里，节省代码行数的同时，也节省了成本。

成本 ￥5 以及电量 117 的方案是怎么实现的？你不用 RAM 存门锁密码的吗？

有读者可能会问了，看你这个方案里，三项指标都没有达到你的最佳，你是不是有所保留了？我的回答如下：本关的主题是【安全门锁】，一切设计方案都需要首先保证安全。如果为了优化三项指标而牺牲安全性，将错误的密码判断成了正确的密码，那就只是骗过了测试样例，实际却不符合题意了。

我曾经写出过的一切“优化过三项指标”的方案都是不安全的方案，存在用【和门锁密码不一致，且不是 9999999999】的房卡开锁的可能性，安全性无法得到保障。在不牺牲安全性的前提下，以上方案是我能想到的最优方案。如果读者有更好的，不以牺牲安全性为代价的方案，请给我留言。

2023 年 2 月 21 日更新

时隔半年，我竟然收到了 Discord 上热心网友的留言

ta 说，可以记录并比较前缀和。因为十位密码都是 0~9，所以和最多为 90，多出来的百位可以用于标记是否出现了不匹配的数字。这样就把原先的两个标记位减少为了一个。优化后的代码如下：

我们先看处于学习状态（即 p0 = 100）时会发生什么。忽略掉不会执行的代码后，代码看起来是下面这样的：

读卡器信号出现后（slx x0），将 acc 初始化为 100（mov 100 acc）。接下来，每从读卡器读取一位数字，就将读到的数字累加到 acc 里（add x0），并将实时的前缀和写入 RAM（tcp p0 50, + mov acc x2）。至此，判断 RAM 的指针是否小于 10（tcp x3 10）。如果小于 10，就说明仍有等待接收的数字，跳回到第 3 行继续接收（- jmp 3）。直到 10 个数字全部接收完毕后，将 RAM 指针归零（mov p1 x3）。

接下来再看处于非学习状态（即 p0 = 0）时会发生什么。忽略掉不会执行的代码后，代码看起来是下面这样的：

也就是只忽略掉了第 5 行代码。读卡器信号出现后（slx x0），将 acc 初始化为 100（mov 100 acc）。接下来，每从读卡器读取一位数字，就将读到的数字累加到 acc 里（add x0），并判断此时的 acc 和 RAM 里对应位置的前缀和是否匹配（tcp p0 50, - teq acc x2）。匹配时，无事发生；一旦出现了不匹配的数字，就将 acc 的百位置为 0（- dst 2 0）。至此，判断 RAM 的指针是否小于 10（tcp x3 10）。如果小于 10，就说明仍有等待接收的数字，跳回到第 3 行继续接收（- jmp 3）。直到 10 个数字全部接收完毕后，判断 acc 的值是否大于 89（teq p0 0, + tcp acc 89）。

开门的前提条件是以下两者之一：①十位房卡密码完全匹配；②房卡密码是 9999999999。我们知道，在循环的过程中，如果出现了不匹配的前缀和，百位会被立刻置零。而又因为房卡密码自身的和不会是三位数，acc 的百位仅用作标记，所以根据原命题和逆否命题等价的原则，只要最终的 acc 是三位数，就说明房卡密码完全匹配。而如果累加和是两位数的话，就说明至少有一位不匹配的数字。当出现了不匹配的数字时，仅当 acc 为 90，即每一位都为 9 时，才能打开房门。综上所述，仅当 acc 的值大于 89 时，才触发 6 秒的解锁信号（+ mov 100 p1, + slp 6）。执行完毕后，同时将解锁信号和 RAM 地址归零（mov p1 x3）。

点击左下角的【模拟】，稍等片刻，便会弹出结算界面：

电量 484→357，其他两项指标不变，完爆了我的上一版方案。