grep で Wordle を解く

話題の Wordle だが、自力で解ける予感などまったくしないので、最初に試した時から grep 系のツールと正規表現を使うことしか考えなかった。

同案多数なのでさらっと書いておくと、こんな正規表現を作れば候補を絞り込むことができるというわけだ。それぞれのパターンの最後の行がマッチするパターン。その前の２行は、含まれる文字と含まれない文字に対応するものだ。

# salet
(?=.*l)(?=.*e)
(?!.*[sat])
[^s][^a][^l][^e][t]

# field
(?=.*l)(?=.*e)
(?!.*[satfid])
[^sf][^ai][^le][^el][td]

# clone
(?=.*l)(?=.*e)
(?!.*[satfidcn])
[^sfc][l][o][^eln][e]

# glove
(?=.*l)(?=.*e)
(?!.*[satfidcngv])
[^sfc][l][o][^eln][e]

# blore
(?=.*l)(?=.*e)
(?!.*[satfidcngvr])
[b][l][o][^eln][e]

これを実行すると、３つ目のパターンを辞書で検索した時点で、候補は９個に絞り込まれ、４つ目では２つ、５つ目では１つになってしまう。だから、はっきり言ってあまり面白くない。

grep で Wordle を作る

解くのはつまらないので、grep で Wordle を作ってみることにしよう。

上の例の正解は BLOKE なので、これにマッチして色を付けるパターンを作ればいい。

黄：どこかに出てくる文字

どこかに出てくる文字にマッチするパターンは超簡単で [BLOKE]。

黒：出てこない文字

出てこない文字にマッチするパターンも簡単で [^BLOKE]。ただし、これだと改行文字も含むアルファベット以外の文字にもマッチしてしまうので、(?=[A-Z])[^BLOKE] としてあげることでアルファベットにだけマッチする。

緑：正しい場所にある文字

最初の文字が B に対応するパターンは ^B で、2文字目の L は ^.L でマッチすることができる。

ただ、これだと一度に1文字しかマッチさせることができないので、look-behind （後読みと呼ばれることが多い）のパターンを使って工夫する。最初の B は (?<=^)B、２番目の L は (?<=^.)L となる。まとめると、次のようなパターンになる。

(?<=^)B|(?<=^.)L|(?<=^..)O|(?<=^...)K|(?<=^....)E

grep で試してみる

上のパターンを grep 系のコマンドに与えれば、対応する文字を探すことはできるし、最近のコマンドには大概着色する機能があるので、それを使ってハイライトさせることができるはずだ。

macOS 上の GNU grep (ggrep)、最近気に入ってる ripgrep (rg)、pcregrep、自作の greple で試してみると、次のような結果になった。

rg、pcregrep、greple からは期待した出力が得られたが、ggrep は最初の1文字しかマッチしてくれない。

元来、行単位で検索するツールなので、１つでもマッチすれば十分という考え方もあるが、上のように -o オプションを付けた場合には結果が大きく変わってしまう。ggrep も . ならすべての文字にマッチするので look-behind が影響しているようだ。

ちなみに look-behind の (?<=^.)L ではなくて ^.\KL では期待した動作とならない。これらは等価に使えると思っていたので、ちょっと意外だった。

greple モジュールを作る

grep を3回実行すれば一応ヒントは作ることができるし、頑張れば混ぜて出すこともできるかもしれない。ただ、それはあまりに無駄な努力な気がするので、greple のモジュールとして実装することにする。

greple は他のツールと違って、複数の色を扱うことができる。複数のパターンを指定した場合、それぞれに別の色を割り当てることができるのだ。また、先に指定したパターンが優先されるので、緑のパターンを先に指定しておけば、その後で黄色のパターンにマッチしても無視される。

できあがったものはこれだ。使っている正規表現は、上の説明とは少し違うが意味は同じ。

わかりやすいようにデバッグオプションで検索パターンを表示している。使い方はシンプルなので、特に説明は不要だと思うが、簡単に特徴を挙げるとこんな感じ。

ルールはオリジナルのゲームとほぼ同じで、一日毎に問題が変わって、6回トライできる。
解答は同じ単語リストから選んでいるが、シャッフルしているので同じにはならない。
--compat オプションをつけると、オリジナルと同じ問題になる。
--random オプションをつけると、毎回問題が変わる。
辞書にない単語を入力すると 💥 が、正解すると 🎉 が表示される。
辞書にない単語は何回でも入れられるが、合わせて30回入力すると終了する。
ハードオプションはない。

--random オプションをつければ毎回問題が変わるので、オフラインで練習したい人にはいいんじゃないでしょうか。

バッチモード

入力がターミナルでない場合には、通常の動作をする。つまり、１行ずつ読み込んでパターンにマッチしたら色を付けて出力する。5文字の単語ならマッチするので、単語のリストを与えれば色をつけて表示する。正解のリストを与えると、次のような結果になった。ネタバレにならないように、シャッフルしたデータにしてある。

この中に1つだけ正解があるのだが、探すのも一苦労だ。結果を画面に収めるために ansicolumn というコマンドを使っている。基本的な機能は column コマンドと同じだが、ご覧のように、ANSI シークエンスが入っていても、正しく文字列の幅を判断してくれる。

インストール

CPAN にあげてあるので、cpanm でどうぞ。

cpanm App::Greple::wordle

リポジトリはこちら。

App::Greple::wordle で工夫しているところ

greple は、本来テキストファイルからパターンを検索するためのツールだが、今回のように、ちょっと変わった目的に利用することもできる。ただ、普通の使い方とは違うので、いろいろ工夫している。

若干無理やり感がなくもないが、パターン生成の15行程度のコードで Wordle の基本機能が実装できているので、フレームワークとしては悪くないんじゃないかと思っている。

Getopt::EX が提供するのは、こんな風にオプションと関数定義の間で制御が行ったり来たりできる機能だ。オプションから関数を呼び出すことができるし、関数の中でオプションを定義したり設定したりすることができる。

`/dev/stdin` を30回読んでいる

greple は、ファイルを全部読んでから処理するので、入力が終わらなければ処理が始まらない。どうやって１行毎に処理しているかというと、毎回 /dev/stdin を読んでいる。つまり検索対象ファイルとして /dev/stdin を30回指定している。

入力フィルターに `head -1` を指定

/dev/stdin から読み込むと ^D を打ち込まなければ入力が終了しない。だから、１行でやめるために入力フィルターとして head -1 を指定している。/usr/bin/read コマンドも使えそうだが、どの OS にもあるのかわからないのでやめた。

ここは、自前でフィルター関数を実装すれば、行編集もできて使いやすくなるので、そのうち暇ができたら実装するかもしれない。

オプション処理のタイミングが難しい

今回、メインの処理をパターンマッチで行うことにしたので、コマンドの検索オプションとして最初にそのパターンを与えなければならない。そのパターン生成に関するコマンドオプションを作ろうとした場合、普通のようにコマンドの実行が始まってからオプション解析をしていては手遅れなのだ。

greple は Getopt::EX というオプション処理のライブラリを使っている。というか、もともと greple のために作った機能を独立させたものだ。これは、本体のコマンドが実行される前に、コマンド引数を処理して、いろいろやってくれる。

Getopt::EX には mode function というのがあって、& で始まる引数があると、定義された関数を実行して、その結果で引数を置き換えることができる。今回は、その機能を使ってオプションを処理して、検索パターンも同様に生成している（コード）。

結果は１行戻って表示している

最初は、評価結果や出現文字に関する情報を普通に表示していたのだが、どうも間伸びして見づらくなってきた。同じ行に出力したいところだが、普通に端末から入力した行を読み込んでいるので、入力が終了した時点で改行してしまうのはどうしようもない。

というわけで、無理やり１行上に戻って表示している。該当するコードは次のようなものだ。

sub respond {
    print ansi_code("{CUU}{CUF(8)}");
    print s/(?<=.)\z/\n/r for @_;
}

ansi_code は Getopt::EX::Colormap の中で定義されていて、与えられた指示に従った ANSI のエスケープシークエンスを返す。CUU は Cursor Up、CUF は Cursor Forward の意味で、１行上に移動して、8文字右に移動するという意味だ。表記は ECMA-48 の仕様に従っている。

`--need 1`

検索の際には --need 1 というオプションを指定している。greple に複数のパターンを与えた場合、デフォルトではすべてのパターンにマッチする行だけを出力する。正解の単語は緑のパターンにしかマッチしないので、その行は出力されくなってしまうわけだ。それでは困るので、1つだけでもマッチしたら出力するように指示するのが --need 1 オプションだ。

おしまい

以上 greple の wordle モジュールのお話でした。自分は、本家に行かずに、案外これで満足しちゃってます。

grep で Wordle を解くのではなく grep で Wordle を作る