xkcd 的正则高尔夫：第 1313 期漫画背后的谜题

正则高尔夫源自 xkcd 第 1313 期漫画：写出最短的正则表达式，匹配一个列表里的每个单词，同时不匹配另一个列表里的任何单词。和真正的高尔夫一样，杆数越少越好。整个玩法都在下面这个棋盘里，来试试：

这就是全部玩法。乐趣在于，它很快就不再简单了。

01为它命名的漫画

2014 年 1 月，xkcd #1313《Regex Golf》让很多程序员认识了这个游戏。第一格画的是一个能匹配《星球大战》副标题、却不匹配《星际迷航》副标题的正则：

漫画的悬停文字把赌注加得更大：一个 63 个字符的正则，能匹配每一位当选美国总统的姓氏，却不匹配任何被他们击败的候选人。

它看起来像乱码，但请把它当成一张清单来读：被 | 隔开的每个片段负责抓住几位总统。单单一个 j 就抓住了 Jefferson、Jackson 和 Johnson。

02笑点里的 bug

同一个月，Peter Norvig——时任 Google 研究总监、经典 AI 教科书的合著者——写了一个 notebook，用程序自动解正则高尔夫。他的测试第一件事就是检查漫画的答案。结果没通过：

[rn]t 抓住了 fremont——John C. Frémont，他在 1856 年的大选中输给了 James Buchanan。Norvig 发现，Randall 把那一年的第三党候选人 Millard Fillmore 当成了 Buchanan 的对手。正则高尔夫的答案，只和它的单词列表一样可靠。

03计算机怎么玩正则高尔夫

Norvig 的求解器是一段很漂亮的推理，值得了解，因为优秀的人类玩家也是这么想的：

1. 收集候选片段。 取出胜选者名字里的所有短片段——一到四个字符，其中一些字母换成 .——比如 bu、a.a 或 r.e$。
2. 只保留安全的片段。 一个片段只有在至少匹配一个胜选者、并且不匹配任何落选者时才有用。
3. 覆盖所有胜选者。 接着挑选片段，直到每个胜选者都被匹配。这就是经典的集合覆盖问题，它是 NP 困难的——所以求解器用贪心法，每次挑选在“覆盖的胜选者”和“花费的字符”之间权衡最好的片段。
4. 用 | 把它们连起来。

结果比漫画短了 9 个字符：

它把《星球大战》那一格也缩短了——从 10 个字符缩到 9 个：

04从谜题到每日习惯

regex.alf.nu 这类浏览器游戏把这个点子做成了可以一关关刷下去的关卡包。Regex Hunter 走的是另一条路——Wordle 的路：

05来自 Norvig notebook 的一道题

Norvig 还让最受欢迎的婴儿名字互相较量。下面是五个男孩名和五个女孩名——标准杆就是他答案的长度。你能追平它，甚至更短吗？

06今天就来玩正则高尔夫

玩今天的狩猎 →每天一道新的正则高尔夫谜题：抓住怪物，放过无辜者，争取低于标准杆。免费，在浏览器里就能玩，无需注册。

如果你想学技巧而不是历史，请阅读正则高尔夫策略：如何打出低于标准杆的成绩。