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秒，舒服了。