3月に正規表現のネタとしてWordleを扱った記事
・窓辺の小石(51) The Wordle-Bug
https://news.mynavi.jp/article/pebbleinthe_window-51/
を書いた後、どうにもモヤモヤした感じがあった。試行2回では不十分で、やはり3回は必要なようだ。ということで、ゼロからやり直して3つの単語を探すことにした。
基本は同じである。辞書の見出し単語のアルファベット出現確率から、上位15文字からなる単語を選ぶ。これで辞書にある単語の87.51%をカバーすることができる。上位の15文字とは、“EARIOTNSLCUDPMH”である(出現確率は前記記事参照)。
問題は、単語を探すときに順位の高い文字から使ってしまうと、比較的順位が前になる母音が先に使われてしまうこと。前回は、順位の高い文字を先に探してしまったので、3つめ以降の単語に無理がかかることになった。
そこで、前回作成した5文字単語のリストから、アルファベットが重複しないものを抜き出し、そこから上記のリストの文字を対等に探すことにした。具体的には、
pgrep '^(?!\w*(\w)\w*(\1))\w+' words5 | pgrep '[EARIOTNSLCUDPMH]{5}' | head -5
として、とりあえず候補5つを出した。なお、正規表現を使う関係で前の記事と同じくWSL上のbashを使っている。
“pgrep”は筆者が定義しているbashのエイリアスで“grep --color=auto -P”が定義してある。“--color=auto”は一致した部分に色を付けるオプション、“-P”は、正規表現の仕様としてPerl互換正規表現(PCRE。Perl Compatible Regular Expressions)を使うものだ。そもそも、egrepが“grep -E”、fgrepが“grep -F”と同じだとされているので、pgrepがあってもいいじゃないかというわけだ。今やgrepの「標準正規表現」や「拡張正規表現」のほうが少数派だが、POSIXで定義されているので実装は必須だが、多くの言語で扱う正規表現はPCREやそれに準じたものだ。筆者もこっちのほうが書き慣れている。
先頭にあった“ACHED”がWordleで未知の単語であると撥ねられなかったので、仮の単語としてこれを採用する。これを使って、2つめの単語を探す(写真01)。
pgrep '^(?!\w*(\w)\w*(\1))\w+' words5 | pgrep '[EARIOTNSLCUDPMH]{5}' | pgrep '[^ACHED]{5}' | head -10
これらのなかから、3つめの単語があるかどうかを探していく。
pgrep '^(?!\w*(\w)\w*(\1))\w+' words5 | pgrep '[EARIOTNSLCUDPMH]{5}' | pgrep '[^ACHED]{5}' | pgrep '[^INPUT]{5}' | wc
のようにした。すると、“ACHED/LINUS/TROMP”が最初の組み合わせとして見つかるが、“LINUS”はWordleが単語として受理しなかった。しかし、次の“ACHED/LIONS/TRUMP”は、すべての単語をWordleが受理する。この3単語が効率のよい試行が可能な3つの単語である。他の組み合わせもあり得るが、調べる文字は同じ。なのでこの組み合わせだけ求めれば問題ない。
さて、その先だが、この3つの単語を入れると多くの場合で、答えに含まれている文字が4文字程度見つかる。またそのうちの1つぐらいは位置も正しいこともある。そうなると、以前の記事で作成した5文字単語の辞書ファイルから、正解の候補を3~4単語程度に絞ることができる。
候補を絞るには、“ACHED/LIONS/TRUMP”の中から、3回の試行で得られた情報を使って正解にマッチする正規表現を作る。文字は異なるが、正規表現の基本パターンは同じ。毎回、コマンドを打つのも面倒なので、awkのスクリプトを作った(リスト01)。このスクリプト wordle.awkは、
awk -v p='〈正解ベクトル〉' -f wordle.awk 〈5文字単語辞書ファイル〉
のように実行する。〈正解ベクトル〉は、5文字の3単語(合計で15文字)の各文字が位置まで正しい(Wordle上では緑で表示)のときには“2”、 文字は正しい(同黄色で表示)のときには“1”を入れ、それ以外の場合には“0”を入れた15文字の文字列である。たとえば、正解がFOYERのときには、“000200010001000”になる。〈5文字単語辞書ファイル〉は、 ホームディレクトリにwords5という名前で存在する場合には省略可能(処理は7行目)だ。
■リスト01
BEGIN{
if(p == "" ){
print "Usage: awk -v p=\"0110000020\" -v wd=\"ACHEDLIONSTRUMP\" -f ~/wordle.awk ~/words5"
exit ;
}
if(wd==""){ wd="ACHEDLIONSTRUMP" }
if(ARGV[1]==""){ ARGV[ARGC++]=ENVIRON["HOME"] "/words5" }
x=split(p,d,"");
y=split(wd,w,"");
non="[^"; hit[0]=""; j[0]="";
for(i=1;i <= x;i++){
if(d[i]==0){ non=non w[i]; }
if(d[i]==1){ hit[i]=w[i]; }
if(d[i]==2){ j[(i-1)%5+1]=w[i]; }
}
rx="";
for(i=1;i<=5;i++){
if(j[i] != "" ) { rx=rx j[i]; }
else if(j[i+5] != "" ) { rx=rx j[i+5]; }
else if(j[i+10] != "" ) { rx=rx j[i+10]; }
else { rx=rx non hit[i] hit[i+5] hit[i+10] "]"; }
}
}
{
x=match($0,rx);
if(x==0) next;
for(cc in hit){
x=match($0,hit[cc]);
if(x==0) next;
}
print $0;
}
前回も言ったように、これは完全な解法ではなく、あくまでも「最も効率の良い試行が行える3つの単語」を探したものだ。試行後、候補が3つ以上残るなら、5回の試行では求めることはできない可能性がある。出題用の辞書が未知であるため、候補の中にはWordleが受理しない単語が入っていることがある。正解が「OXIDE」のときには、この方法(写真02)では、3つの単語が候補として提示されたが、そのうちの1つ「JODIE」はWordleが受け付けなかった(人の名前は受け付けない確率が高いように感じる)。毎日やってるわけではないが、筆者が試した範囲では5回以内の試行で解くことは可能だった。
“World”をタイトルに含むSFは少なくない。“Lost World”(Arthur Conan Doyle,1982。邦題「失われた世界」)、“Ringworld”(Larry Niven,1970。邦題「リングワールド」)、“Rosheworld”シリーズ(Robert Forward,1982。邦題「ロシュワールド」)などだ。存在しない未知の世界や現象を記述するというテーマは、昔から人を惹きつけてきた。一歩間違うと「ほら吹き」になってしまうが、うまくいくと「傑作」になりやすいテーマでもある。
Worldを選んだのは、Wordleと綴りが似ているからで、今回は「プログラム」(awkスクリプト)を作ったので、サンプルコードの代表格である「Hello World」と組み合わせてみた。ちょっと苦しいか……。