用程序解决 Draw Something

Draw Somthing 是最近很流行的一个游戏,iOSAndroid 平台都有对应的版本。
游戏很简单,玩家看到单词,然后画给网络对面的玩家。对方看到图片,根据下面给出的候选字母拼出单词。

仔细想了一下,编程解决猜图画,难度比较大。但是可以解决根据已单词长度和候选字母,在字典中寻找符合这两个条件的单词作为候选,之后再由人肉方式得到最终答案。
首先需要准备字典,如果使用标准的字典序,在搜索时需要根据长度过滤单词。其实没有必要每次搜索的时候做,重新对单词进行排序,先按照长度比较大小,只有当长度相同时才按照字典序比较大小。之后就可以将单词整理成按照长度分隔的字典。
搜索时,参考拼写检查算法,将候选字母按照字母顺序排序成列表,将单词依次取出后,也把单词变形,将单词内的字母按照字母顺序排列。看单词的字母表是不是候选字母表的子集,如果是子集,者加入候选单词表。

使用一个有300,000单词组成的大字典字典进行测试。由于大部分情况下, Draw Something 的候选字母数量都是12,测试结果表明,对于长单词的猜测效果很好,比如这个例子:
目标单词长度为7,候选字母是:BEMPRTTTUWXZ。
在字典中搜索结果,唯一符合的是:TRUMPET。即正确答案,完全无须根据绘制的图像猜测单词。

对于短单词,则使用一个只有5000个单词组成的小字典,比如这个例子:
目标单词长度为3,候选字母是:BEHIKLNRSSUU。
最终的到10个候选单词,大大降低了猜测难度。

通过这个小程序的辅助,对于一些完全不着边际的情况,比如某律师画的这个:

e785a7e78987

很快就可以找到答案为 ROBOT。

大字典下载:http://115.com/file/e7lyhye9

小字典下载:http://115.com/file/c2xgbqnu

*字典按照 Creative Common-署名-相同方式共享

4 thoughts on “用程序解决 Draw Something

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>