窓辺の小石 第51回 The Wordle-Bug
Hit&BlowとHangmanを合わせたようなWordleというゲームがはやっているらしい。Hit&Blowのようなゲームは、いまでもプログラミング学習の課題として使われる。筆者もBASICが動くマシンを手に入れたとき作ってみたことがある。三山崩しのように必勝アルゴリズムがあるゲームは、ゲームを作る過程で自分も学んでしまうため、ゲームなのに、ちっとも楽しくない。だが、それに気がつくのはプログラムを作ったあとだ。背が伸びないとアトムをサーカスに売り払う天馬博士に同情したくなる。
UNIXにはwordsという英単語のリストが含まれている。これは、スペルチェックなどを想定したもの。そもそもUNIXの開発時には、ワードプロセッシングのシステムを開発するといって予算を取ったという話がある。筆者は、その存在と利用方法を雑誌サイエンスに連載されていたコラム記事で知った。1980年台のことで今となっては記憶があいまいだが、メタマジックゲームかコンピュータリクリエーションだったと思う。wordsを使えば英単語全体を対象にするような処理ができる。
Linuxでは、wordsファイルはSCOWL(注01)のパッケージとして入手可能だ。Ubuntuなどで使われるdpkg系の「wamerican」パッケージには収録単語数の違いで5つのパッケージがある。筆者が試してみたところ、wamerican-smallには含まれない単語がWordleの正解になったことがあり、それ以上の収録数のパッケージでは、Wordleで辞書にないとして入力ができないものがあった。ということで境界にあたるwamericanパッケージが適当と考えられる。このパッケージをインストールすると/usr/share/dict/wordsファイルが作られる。
※注01: Spell Checker Oriented Word Lists
http://wordlist.aspell.net/
Wordleの答えは大文字で5文字なので、大文字で5文字の英単語だけのリストを予め作っておく。grepとtrを使いsortで並べ替え、重複行を抜く(先頭が大文字になった固有名詞が含まれるため)。
egrep -i '^\w{5}$' /usr/share/dict/words | tr a-z A-Z | sort -u >word5
Wordleでは6回の試行で5文字の単語を探す。1回目、2回目の試行を、どの文字が含まれているのかを探すことに専念して、出現頻度の高い文字を含む単語を探す。文字の出現頻度は、あちこちにあるが注意すべき点がある。相手はWordleの中の辞書(単語リスト)であり、辞書なら見出し語は原則1つだけ、このため一般的な英文から計算された文字の出現頻度とは異なるパターンになる。
ここでは、Concise Oxford Dictionary(11th edition revised, 2004)から求めた文字の出現頻度を使う(注02)。筆者がまとめ直した表を(表01)に示す。出現頻度を高い順に並べると「EARIOTNSLCUDPMHGBFYWKVXZJQ」となる。
※注02: Which letters in the alphabet are used most often?
https://www.lexico.com/explore/which-letters-are-used-most
累積出現頻度50%以上の「EARIOTN」から5文字を含む単語は17個ある(写真01)。以下のコマンドで、先頭のgrepは探索用に文字が重複しない単語を抽出するもの。否定的先読み“(?!……)”の中で、カッコによるグループ化“(\w)”と、参照“\1”を利用して同じ文字を含むパターンが先行しないアルファベット文字の並び“\w+”を探す。2つめのgrepは「EARIOTN」のうち5文字を含むパターンを探す。
grep -P '^(?!\w*(\w)\w*(\1))\w+' words5 | grep -P '[EARIOTN]{5}' | wc
この17個の単語に文字の出現順序に対して評価値をつけ、単語に含まれている文字の評価値合計を出す。それを計算して上位5個を表示するのが、下のコマンドだ。
grep -P '^(?!\w*(\w)\w*(\1))\w+' words5 | grep -P '[EARIOTN]{5}' | awk -v FS='' 'BEGIN{ st="EARIOTNSLCUDPMHGBFYWKVXZJQ"; for(i=1; i