Game Boy Wordle clone:如何将12972个五字母单词压缩到17871字节

2022-02-20 12:21:01

Wordle有一个GameBoy版本,使用bloom过滤器、精简的词汇表和精简的猜测单词列表,所有这些都安装在一个32K盒带上。我下定决心挑战自己,看看我是否能适应12972个单词的词汇表,以及2315个单词的答案列表。因此,挑战在于:

我管理它(在这里下载ROM),它在游戏机模拟器中工作。有不止一种方法,我所做的可能过于复杂,但我对游戏机的运行速度感觉不好,所以我做了一些速度优化。

第0步:我们从12972开始 × 5. = 64860字节的未压缩数据。

第一步:根据单词的第一个字母,将12972个单词列表分成26个列表。因为在每个列表中,第一个字母是相同的,所以我们现在每个单词只需要存储四个字母,并且每个列表都有一些开销。(最终分析的开销为108字节。)如果我们停在这里,

步骤2:每个四个字母的“字”(或字尾)可以以每个字母5位的形式存储,从而生成一个20位无符号整数。如果我们停在这里,我们可以将每个单词存储在2.5字节中,总计32430个。如果没有代码的话,它可以安装在盒带上,但这是一个进步。

第三步:这是我的一个聪明的想法。每一个由四个字母组成的“单词”列表都是按字母顺序排列的,并且按照自然方式编码为20位数字,数字将按升序排列。我们不需要存储这些数字,只需要存储它们的算术差,从初始(无效)0开始。

第四步:由于差异总是至少为1,我们可以从每个差异中减去一个,使数字稍微小一些。(这是一个不必要的并发症,但我有过,不想把它去掉。)

第5步:存储一个字节流,对差减1进行编码。每个数字编码为1、2或3个字节,每个字节中有7位,如果是最后7位序列,则每个字节的高位为1,如果不是,则为0。结果是,结果是17763字节,加上108字节的开销,总共17871字节,或原始列表的28%,压缩非常非常简单。

第6步:现在我们用词表索引替换字母排序答案列表中的每个单词。由于每个索引都包含2个字节,因此我们可以将答案中的2315个单词存储为2315个 × 2. = 4630字节。

第7步:然而,事实证明,两个连续索引之间的差值永远不会大于62。因此,我们可以重复使用存储连续差异的技巧,并将答案存储在2315字节中。(事实上,由于我们只需要6位的差异,我们可以降低到1737字节,但这会使代码复杂化。)

结果:词汇加答案下降到108+17763+2315=20186字节。这太大了,无法使用现有代码安装在32K的Cartridge上。但事实证明,现有的大多数代码都是gprintf()的库支持代码,用gprint()替换单个gprintf()调用似乎可以让所有内容都适合32K。

将其编码为20位整数,再加上一个初始零,我们得到0729915281760718024328332840。

每一个都适合14位(考虑到高比特使用率,两个字节),最后一个适合7位。实际上,7位中有很多差异,所以这最终比前六个字看起来更具代表性。

使用如上所述的代码,盒带中有250个字节可供使用。

人们可能想知道,与使用标准的通用压缩器相比,编写压缩算法是否节省了大量内存。对gzip在64860字节的未压缩词汇表上运行会产生30338字节,这比我的17871字节压缩词汇表要差得多。另外,我预计解压代码会更复杂一些。

通过将步骤2中的四个字母“单词”编码为base-26,而不是四个5位序列,可以节省一点内存。但它只会节省大约0.5K的内存,而且代码会更加糟糕(Game Boy使用库函数进行除法!)。

答案可以存储为长度为12972的位图,即1622字节。但这会使生成arandom单词的代码更加复杂和缓慢。