Wordle是个字谜游戏,用六次机会猜一个5个字母的单词,每猜一次会告诉你猜的答案中哪些字母在谜底中。玩了几次后,我发现先猜两三个没有重复字母的单词(heterogram)可以快速缩小谜底字母的范围。那么问题来了,有没有5个单词可以覆盖25个英文字母呢?,这样猜5次几乎必然可以确定谜底中包含哪些字母。

准备工作

首先从wordle网页源代码里复制出来词汇表。Wordle有两个词汇表,词汇表1有2315个常见单词,可以作为谜底;词汇表2有12972个词,包含常见单词和生僻词,可以作为猜测的单词。这样就有了一小一大两个数据集可以测试。顺便看了一眼每日的谜题是怎么产生的,其实就是根据日期从词汇表1中按顺序拿一个词。

Code V1

由于词汇表就是JavaScript数组,我就用JavaScript来解题。至于算法,区区5个单词,当然是先从词汇表中筛选出heterogram,然后暴力5层循环,获得5个单词连接起来,看看是不是heterogram。

V1运行结果:词汇表1都跑不出结果,卒。

Code V2

看来需要优化一下代码。首先在外层循环中提前判断是否有重复字母,减少循环次数;然后提前给词汇表排序,这样能尽早发现重复字母,也能减少循环次数。

V2运行结果:词汇表1耗时45秒,没有找到可以覆盖25个英文字母的5个单词。词汇表2跑不出结果,卒。

Code V3

目前的算法是O(n⁵)的复杂度,词汇表2包含的heterogram数量是词汇表1的3.7倍,而3.7的5次方大约是700。是不是要先看看算法层面的优化,找找复杂度更低的算法呢?自己想想,没有头绪;搜索一番,找到了一个很相似的问题:maximum coverage problem。然而这个问题是NP困难的。

于是我放弃了找更好的算法的思路,继续回头寻找减少暴力5层循环的循环次数的方法:这次把词汇表中的heterogram的字符也排一下序,这样一可以去掉同字母异序词(anagram),二可以更早发现发现重复字母。

V3运行结果:词汇表1耗时22秒,词汇表2跑不出结果,卒。

Code V4

继续优化排序:按字母表排序并不是最优的,统计词汇表的字母频率,按字母频率排序,可以更早发现发现重复字母,减少循环。

V4运行结果:词汇表1耗时12秒,词汇表2在运行到11分钟的时候发现了一个解!到这一步终于可以回答开头的问题了:wordle中存在5个单词覆盖25个英文字母的情况。但我还想跑完整个词汇表2,看看一共有几个解。

Code V5

算法上的优化已经想不出来了,于是转向研究实现上的优化,尝试优化JavaScript代码:改字符串操作为数组操作,没用;不每次调.include()检查,自己维护一个state检查是否有重复字母,也没用。看来JavaScript中字符串操作的效率相对来说还挺高的。

没办法了,决定换语言,再折腾一番,用C++来实现。C++处理字符串挺难受的,改用数组和自己维护state,算法逻辑和JavaScript版本完全一样。

V5运行结果:性能暴增,词汇表1耗时0.33秒,词汇表2耗时55秒,终于跑出结果了!

Code V6

词汇表2耗时55秒还是很慢嘛,并行计算搞起。这个算法并行起来0难度,简单的用个OpenMP,循环上加一行#prama omp prallel for,boom,用上8个核了。

V6运行结果:词汇表1耗时0.13秒,词汇表2耗时16秒。

Code V7

性能还有提升空间,我就再调一下。简单的把编译器从gcc换成clang,再设一下OpenMP调度schedule(dynamic,1)

V7运行结果:词汇表1耗时0.05秒,词汇表2耗时3.6秒。

Code V8

此时忽然发现我还在一个字母一个字母的比较是否有重复字母,太弱了。早该想到换一个合适的数据结构了。Heterogram和循环中的state均可以用一个uint32_t中的26个比特位来表示,1表示出现了这个字母,0表示没出现。这样比较是否有重复字母以及在当前state中添加/去除heterogram都可以用一个位操作实现。

V8运行结果:词汇表1耗时0.02秒,词汇表2耗时1.99秒。

Code V9

算法循环中最核心的操作是比较是否有重复字母,现在只用一个&操作实现。下面自然就考虑SIMD了,AVX2指令集可以在循环中一次处理256位,就是8个比较。但是使用intrinsics来实现,体验十分痛苦,代码难以编写,可读性大幅下降,而且未必一定有正向收益。光判断一个YMM中的8个32位数是否均不为零就费了我半天的劲儿,太痛苦了。最后测试结果确实有性能提升,但很可能引入了各种bug,有种不详感。

V9运行结果:词汇表1耗时0.01秒,词汇表2耗时0.65秒。

结论

最后找到了11个解。下图是其中之一:

wordle heterograms

说是算法问题,但到最后也没有改变暴力5层循环算法,只在数据预处理和具体实现上优化。最终版本比最初naive版本性能提升估计得有1000倍,在i9-9900机器上耗时小于1秒,舒服了。