Wordle解く

# Wordle
最近ツイッターでGithubの草が生えているみたいなツイートが流れてます。

https://twitter.com/YumizSui/status/1483463822187036676

これは進捗を生んでいるのではなくて、Wordleというゲームで遊んでいます。

Wordleは５文字の英単語を当てるゲームです。

https://www.powerlanguage.co.uk/wordle/

毎日0時に、その日の単語が更新されます。みんなで同じ単語を解くことになるので、何が出たとかはネタバレになります。

最初は[英和辞書検索](https://nmm.blog.jp/hp/tool/dictsearch/dictsearch.html)が便利で、色々やってたんですが、効率化したくなってしまったのでPythonで書きました。



# 効率的な英単語

誰でも思いつくと思いますが、英単語に頻出するアルファベットを使った単語から攻めていくのが良いです。
eが最も多くてqとかzが少ないみたいな話は[シーザー暗号](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%BC%E3%82%B6%E3%83%BC%E6%9A%97%E5%8F%B7)で有名ですね。

何を最初に入力するのが一番良いのかは諸説ですが、`arise`なんかは母音やr,sが絞れて良さそうです。

英単語を`/usr/share/dict/words`から引っ張ってきて、小文字５文字の単語を抽出します。
`cat /usr/share/dict/words |grep -E "^[a-z]{5}$" > word_dict.txt`

Wordleが同じ語彙を使っているかは不明です。

```alphabet.py
with open('word_dict.txt') as f:
    word_list = f.read().splitlines()
# 26文字取得
alphabets = [chr(ord("a")+i) for i in range(26)]
# 全部マージ
word_merged = ''.join(word_list)
alph_cnt = {c: word_merged.count(c) for c in alphabets}
```
ソートすると
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/807058/1bc9c084-48b5-f6c1-e28b-a252383ff5b0.png)
sが多いですが、5文字縛りだとこれは多分三人称単数とか複数形の寄与が大きいとかそういうのではないでしょうか。

# 正規表現で解く

このような画像の状態では　
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/807058/f12bf91d-ab76-fd69-294b-38455309d6a3.png)
どういう単語を入れるべき（入れるべきでない）でしょうか？

`stre`の４文字は確定で入らないですし、各ポジションでは`r`,`pi`,`rp`,`i`,が入りそうにないです。
つまり、頭の悪い正規表現を書くと、`^[^(r)^(stre)][^(pi)^(stre)][^(rp)^(stre)][^(i)^(stre)][^(stre)]$`が探すべき文字列です

```
import re
re_ptn = re.compile('^[^(r)^(stre)][^(pi)^(stre)][^(rp)^(stre)][^(i)^(stre)][^(stre)]$')
[word for word in words if ptn.search(word) is not None]
# ['abaci', 'aback', 'abaft', 'abase', 'abash', ...]
```
これで必ず入れてはいけない単語は篩にかけられましたが、`rpi`の3つが入ってる単語がほしいですね。

```
[word for word in words if all([c in word for c in 'rpi']) and ptn.search(word) is not None][:10]
# ['carpi', 'chirp', 'crimp', 'crisp', 'drips', ...]
```
あとはコードを書くだけです。

基本的には頻出文字から順に正規表現で検索する文字を増やす、ただし入れてはいけない単語は除外するという方針を取ると良さそうです。

コードの公開はしませんがここまで書けば実装できると思います。

# やってみよう

自分で作ったwordleもどきで試しました。

https://gist.github.com/YumizSui/7ac153fafade02ed85ae5990d8ee159b

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/807058/4ecad087-6629-041e-fbf4-9677783ec734.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/807058/5f525ea3-6ed7-04ce-4ecc-00a44f9a7235.png)

1手目では`arose`という単語が出てきました。今回使ってる単語群の中ではこれが最も効率の良い単語みたいです。

2手目では`islet`か`until`が候補として出てきました。
既にわかっている情報を全て活用する「当てに行く」と、2手目で当てることを諦めて、使用される単語を「絞る」の2パターンがあります。
1手目で3文字当ててしまった状態で当てに行こうとすると、1手順あたり2文字しか探索できないので、候補数との兼ね合いで決めるとよさそうです。

3手目までは当てに行って、4手目では残りの1文字に対して候補が6通りあったため、絞る方針を取りました。
絞る選択肢の実装は適当です。この場合の最善手は`woven`だと思います。

色々雑なのでもっといいやり方もあるかもしれません。

ちなみに全ての手順で当てに行く戦略をとったときの解答までの平均手順数は4.37（回数制限無し）らしいです（単語数4594）。


回数制限無しで探索したときの手数の分布
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/807058/438bb2d5-745a-cef1-268f-e28887b1577b.png)
8割は6手順以内に解けるらしい(3780/4594)。

一番悪かったのは`sears`で14手でした。あたまがわるい。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/807058/5bf2c1a2-03fc-0258-535a-b6587bb689fa.png)


# いかがでしたか？

**結論：どう考えても自分で考えて解くほうが楽しい**

https://twitter.com/YumizSui/status/1484387535162081282