高锐走进机房时,手里转着一枚白色六面骰。
他没有看满屏绿色,先把骰子放到键盘旁。
六点朝上。
“随机种子?”林一问。
“提醒你,程序说一句话之前,条件至少要比骰子多写几项。”
程野没忍住,噗地笑出声。
苏远川已经把昨天的输出表摊开,五点候选对数那一栏被他画了红框。何其安则坐在最边上,标题都写好了:
`生成协议,第一版。`
高锐拉过一把椅子,反坐着,手臂搭在椅背上。
“程序说六阶以内零反例。很好。它到底看见了多少东西?”
林一报出每个顶点数下的候选数。
“怎么生成的?”
“按块树递归生成偶有向圈,再把新圈只粘在已有的一个顶点上,得到带标号的有向仙人掌候选;随后筛最大入出度,再枚举指定路径`p`。最后去同构,对每个对象对检查全部合法`1→2`修复。”
“去同构的键?”
林一把代码翻到那一段。
屏幕上只有两部分:有向图`d`的规范编码,外加指定路径长度。
高锐看了三秒,笑了。
“你研究的对象是图吗?”
“是`(d,p)`。”林一说。
“那你的键为什么只认识`d`,不认识`p`站在哪里?”
机房一下静了。
高锐没有继续讲。他拿起红笔,在纸上画了一个四点有向圈,又在其中一个顶点接上一只二点有向圈。两个圈只共享那个顶点,整张图一共五个点。
共享点记作`z`,四圈按方向写成:
`z→a→b→c→z。`
另一个二圈是:
`z→d→z。`
第一份对象里,指定路径只有一条弧:`p?=z→a`。
第二份对象里,指定路径也只有一条弧:`p?=b→c`。
“图相同,路径长度相同。”高锐把两份输入依次喂进程序,“对`(d,p)`来说,它们等价吗?”
林一盯着共享点。
任何保留有向图结构的同构都必须把唯一入度、出度为二的`z`固定。固定`z`以后,有向四圈上的其余顶点也被方向顺序逐个固定。`z→a`不可能被送到`b→c`。
“不等价。”他说。
回车落下。
第一份输入显示:
`new object`
第二份输入紧跟着跳出:
`duplicate`
程野猛地站起来:“它把不一样的东西扔了!”
苏远川一把按住昨天的计数表:“这不是漏一两个。只要同一张图上禁修位置不同,它就可能整批往外扔。”
何其安在协议卡第一行飞快落笔,笔尖擦得纸面沙沙响:
`对象不能只写d,必须写(d,p)。`
高锐把骰子往桌上一弹。白色小方块撞过三台键盘,停在一点朝上。
“恭喜。”他说,“零反例没有了。你们得到一只会把没见过的东西叫成重复的程序。”
机房里有人笑,林一也笑了。
但他没有让笑声替自己认错。
“去同构键是我写的。路径长度被我当成路径位置的替代量,错在对象编码。”他把昨天输出页翻面,直接写下四个字,“结果作废。”
笔尖落得很重。
“怎么修?”高锐问。
林一把邻接矩阵扩成带颜色的关系结构。
普通弧记为零色,属于指定路径`p`的弧记为一色;枚举顶点重标号时,同时重排弧与颜色。每一种重标号产生一个完整编码,取字典序最小者作为`(d,p)`的规范键。
“只改键?”苏远川问。
“不够。”林一答,“昨天没有逐层计数。键错了,我们只在最终总数看见异常。六层都必须留数。”
他在白板上画出六道门。
第一道,按块树递归生成全部带标号的偶有向仙人掌候选,并记录每种圈长组合与粘合方式的数量。
第二道,独立重算强连通、最大入出度、块交叠与圈长条件,验证递归生成器没有产出非法结构;每个检查器分别报进入数和剩余数。
第三道,对每张图生成非空指定路径`p`,并检查`p`在每个圈里至多经过一条弧,形成完整对象对`(d,p)`。
第四道,以带路径颜色的规范键去同构。
第五道,穷举所有合法修复,保存第一个成功证书;若失败,保存完整反例输入,不准只报一个零。
“还少一道。”高锐说。
林一看向他。
高锐把骰子推回六点:“随机抽对象重标号。重标号前后必须得到同一个规范键、同一个可解判断。固定种子,任何人都能复跑。”
程野已经把手举到最高:“我来负责故意乱改名字。”
“你这项特长终于合法了。”高锐说。
整排机位笑翻。
苏远川接走逐层计数,每刷新一层,他都把旧数、新数和差值写到投影右侧;何其安守协议卡,谁口头说“差不多”,他就把那一格退回未完成;程野生成二十组重标号,把`z、a、b、c、d`换成毫无顺序的编号,专挑最容易把人看晕的排列。
林一负责重写规范键。
第一轮,邻接矩阵已经按新编号重排,`p`的弧颜色却还按原邻接表索引附加。同一个对象换一次名字,竟生成两个键。测试失败。
“没过!”程野喊得像报喜。
“好,抓到第二处!”苏远川立刻记数。
第二轮,彩色弧连同起点、终点一起参与重排。`p?`与`p?`终于得到不同键;同一个`(d,p?)`随机换名二十次,全部回到同一键。
“二十次,全同!”程野一巴掌拍上桌。
第三轮,求解器输出一组成功修复,却没有附每条弧两端的`I`、`o`核验表。
何其安把“求解层”重新打回空白:“只有答案,没有证书。”
林一补上证书生成。每一条改成二的弧、每个顶点的入和与出和、每一条弧两端的两个不等式,全被打印出来。
高锐挑中一份证书,先指出其中一条权为二的弧正承担着端点出和区分,再把它改回一。
断言立刻变红:
`o(u)=o(v)`
“它会拒绝假证书了!”苏远川的声音狠狠干拔高。
机房里围过来的人越来越多。
四人寝不再坐着。程野报重标号,苏远川报层数,何其安报协议格,林一敲修复代码。高锐站在中间转着骰子,哪一层通过,就把对应点数朝上。
一点,生成。
二点,筛选。
三点,对象对。
四点,彩色去同构。
五点,修复证书。
六点,重标号复跑。
最后一次回车落下。
`p?: new object`
`p?: new object`
`20 relabelings: consistent`
`certificate check: passed`
苏远川报出修正后的五点候选对数,正好与手工清单相等。
何其安把第六格涂满。
程野抓起骰子,狠狠干举过头顶:“六面全过!”
整间机房轰地炸开。
有人拍桌,有人敲椅背,有人跟着喊“六面全过”。高锐把骰子从程野手里接回来,又塞到林一掌心。
“现在程序有资格说它看见了哪些五点对象。”
“六点呢?”林一问。
“今晚重跑。先别替它抢答。”
林一点头,把昨天那行`counterexample: 0`留在失败记录里,没有覆盖。旁边新建的运行页,六道门一项项带着计数、证书和固定种子。
午后,他刚把协议卡拍进四人寝群,手机又收到一份校队共享表。
表里有两行都写着:
`30米分段。`
一行来自站立式起跑、人工见动开表。
另一行来自三点式起跑、支撑手离开压力触板起表,30米终点由光电门截停。
两行数字被放在同一列,差值还被标成绿色。
林一看了两秒,把那枚六面骰放到手机旁边。
“这张表,也没写完对象。”