知っている人が多いと思いますが、2022年はじめころに流行って話題になったWordleという英単語当てゲームがあります。このnoteでは、Wordleを見ていてふと思いついた問題をプログラムで解く話を書きたいと思います。Wordle自体を解こうとするわけではないです。また、実際に書いたPythonプログラムの部分は有料ですが、メインは文章の方です。

この段落、2022年9月27日に追記しています。この記事を書いた時、冒頭の問題を12時間かかるPythonのプログラムで解きました。その後、急に競技プログラミングにハマり、その内容に衝撃を受けていまして、もっと速く解けるアルゴリズムあるだろうなぁと思っています。競技プログラミングを通じていろいろ勉強することで、いつか短時間で冒頭の問題に回答するプログラムが書けるかもしれないなぁと思っています。参加している競プロはAtCoder Beginner Contestです。

ひとまずWordleの内容を説明すると、5文字の英単語を6回以内に当てるゲームです。単語を入力するたびにヒントを得ることができます。正解の単語と同じ文字が含まれているが位置は異なる場合、その文字が黄色で、正解の単語と同じ文字が同じ位置にある場合は緑色で示されることによって、正解に近づいていきます。やったことがない人は、1度やってみるとわかります↓

午前0時に問題が更新され、1日1回しかできないというのが、やりすぎて飽きたりしないちょうど良い負荷です。そして世界中の人がその日の同じ問題を解き、自分が解いた結果をSNSなどにコピペして共有できるようになっているのがすごくいいデザインです。こんな風に。
Wordle 322 5/6
⬜⬜🟨⬜⬜
⬜⬜⬜⬜🟨
⬜⬜⬜🟨🟨
🟨🟩🟨🟨⬜
🟩🟩🟩🟩🟩

その後New York TimesがWordleを買収しました。買収額はlow seven figures！夢のある話です。

ぼくも何かの記事で見かけて2022年1月の後半からやりはじめ、それ以来ほぼ毎日やっています。すでに200回超えです。こういうのを一度始めると習慣化してなかなかやめられない性格でして^^;

さすがにしんどいのでプログラムとかで楽に解けるようにするかぁ、と思ったのがきっかけでWordleを見ながら考えごとをしていました。今回プログラムで解いた問題はそんな中で思いついた問題の1つです。

Wordleで次に入力する単語を決める時に、ヒントを引き出すためには、まだ使ってない文字をできるだけ多く含む単語を入力したいというのがあるんですよね。つまり文字がかぶっていない単語を使いたい。仮に文字が全くかぶっていない単語を選び続けると、単語2つで10文字、3つで15文字、4つで20文字、5つで25文字、6つで30文字使うことになります。しかしアルファベットは全部で26文字です。よって6つの単語を書くと必ずどこかで文字がかぶることがわかります。Wordleの入力回数は6回までですが、ちょうど文字数がアルファベットの26文字を超える回数になっているんですね。これはWordleがちょうどいい難易度になっている秘密なんでしょうか？そして、ふと思いついた問題というのは記事の最初に書いたこれです。

こうやって問題を書くと答えが気になります。単語一覧は日本語 WordNet (1.1) 最新版のJapanese Wordnet and English WordNet in an sqlite3 databaseをダウンロードして、そこから以下のように抽出しました。5文字で、アルファベットのみで、重複を削除しています。5文字の英単語一覧はこれを使用することとします。

import sqlite3
conn = sqlite3.connect("wnjpn.db")
cur = conn.cursor()
cur.execute("select lemma from word where lang='eng'")
words = list({i[0] for i in cur.fetchall() if len(i[0]) == 5 and i[0].isalpha()})
conn.close()

len(words)とすると、単語数は5371でした。ただし、都市名など固有名詞もたくさん入っており、Wordleが参照しているであろう単語セットと完全に一致しているわけではないです。Googleで「5371 choose 6」と入力すると5371個から6個選ぶ組み合わせの数を計算できます。3.32495e+19と出たので、組み合わせは全部で3300京通りもあります。

最初ランダムに単語を6個選び、1つだけでも偶然単語の組み合わせを見つけられるかやってみましたが、きびしそうでした。

import random
max_count = 0
while True:
    sample = random.sample(words,6)
    count = len(set("".join(sample)))
    if count > max_count:
        max_count = count
        print(count, sample)
        if count == 26:
            break

24文字まできたら、いけそうな気もしてきますが。

その後テキトーに全探索してもやはり1つも見つけられず、普段は何も考えずに景色を眺めている趣味のランニング中も、その日はこの問題のことが頭から離れず、どうやって解けばいいか考えながら走ってました。テキトーにやっても解けなさそうなので、ちゃんと処理の流れを整理してプログラム書こう、と思い直して書き出し、ようやく答えが出力されるプログラムを書けました。

ぼくは普段こういった問題をプログラムで解く機会がないので、久しぶりに頭を使いました。状態の評価と処理の分岐、ステップ、そして枝刈り、あープログラムってこんなんだったなぁと思い出しました。

実行は、Intel Core i7-9700 @ 3.00GHzで12時間かかり、84066通りの組み合わせが見つかりました。最初テキトーにやったら1個も見つからなかったのにそんなにあるんかい！感動モノです。ただしさきほど書いたように、Wordleでは入力できないような固有名詞や数字も多く含まれています。見つかった組み合わせを1つ挙げます。以下の英単語はすべてWordleに入力できました。そして確かに、6つの英単語で、アルファベット26文字、すべて使用しています。

ぼくが知らないだけで、この問題に適用する確立されたアルゴリズムがあるかもしれません。ちょっとした変更で何倍も短い時間で処理が終わるかもしれません。また、84066通りというのは正しい結果を出力していると考えていますが、なにかバグがあったらすみません。そういったことがあれば、教えていただけるとうれしいです。逆に84066通りで正しいという報告もありがたいです。

疑問。使用している文字をカウントする時に、1つ目の単語はlen(set(word))、2つ目以降追加するときはlen(set_used_chr | set(word))としてsetを使ってカウントしていましたが、文字をフラグで表現した方が処理が速くなるのではないか？'たとえば、a'を0b1、'b'を0b10というように文字とビットを対応させると、単語を1つの整数で表現できます。

chr_flag = {}
for a in range(ord('a'), ord('z')+1):
    chr_flag[chr(a)] = 1 << a-ord('a')

words_with_flag = []
for word in words:
    word_flag = 0
    for a in word:
        word_flag |= chr_flag[a]
    words_with_flag.append((word, word_flag))

# ビットフラグ表示
for word, flag in words_with_flag:
    print('{:026b}'.format(flag), word)

なんとタイミングの良いことに、バイナリ表現で1の個数を数えるint.bit_count()という関数が、Python3.10で追加されていたのです。これを使うと、単語に対応する整数をビット演算のorでつなげてからint.bit_count()することで、使われている文字数をカウントすることができます。実際にsetを使っていたところをビット演算に置き換えて実行してみたところ、同じ結果が少し短い時間で得られました。が、残念ながら劇的な改善にはなりませんでした。

ちょ、待てよ。単語を1つの整数で表したことの意味はそれだけではないですね。この探索問題においては、単語でどの文字が使用されているか？に注目すればよいので、同じ数字で表される単語は同じとみなしておけばよいです。つまり、同じ数字788497で表される'tesla', 'stale', 'slate', 'stael', 'lates', 'steal', 'least', 'stela'を別々に調べる必要はなく、1回調べれば良いことがわかります。ちなみに同じ数字で表される単語数で一番多いのがこのTeslaでした！Tesla好きなのでここで偶然出会えてうれしい。

上に書いたように5文字の英単語数は5371でしたが、対応する数字の数はいくつになったかというと、4107でした。なんか期待したほど減ってなくてちょっとがっかりなので、コードに適用していないです。

などと思いながら、同じようなこと考えてる人いないかなーとネットで探していて、Stack Overflowの次の質問を発見。質問者は、ぼくと同じようにWordleをやっていて「5文字の英単語5つで25文字使う組み合わせを見つけることはできるか？」と考え、正しいプログラムを書けずに質問したようです。これも気になる問題です。それに対してGoのプログラムで回答がついていました。

このGoプログラム、むちゃくちゃ速く、数秒で終わります。しかも「5文字の英単語5つで25文字使う組み合わせは存在しない」という結論を導き出します。は？バグってんのでは？と疑い、入力を変更して試してみると、正しく動作しているようです。とりあえずこの記事で書いた自分のPythonプログラムを修正して同じ問題を解いたところ、やはりそのような組み合わせは見つかりませんでしたが、かかった時間は30分。一般論としてPythonよりGoの方が速いです。Goだから速いのか？アルゴリズムの違いなのか？秘密を探るべくGoをインストールし、Goの文法をググりながらコードを読みました。そして同じロジックでPythonコードを書き直してみたところ数秒で終了しました。笑。Goプログラムは再帰関数を使っているのが1つ大きな違いで、これは速度に影響してるかも。ぼくの実装は再帰関数を使っておらず状態を1つの場所に覚えておいてがんばって更新しているんですが、再帰関数って状態をスタックに積んでいくような動作をするので、がんばって更新しなくていい上に無駄な処理がないのかも。他にはこのGoプログラム、枝刈りの方法がおもしろく、効いてそうです。ていうか、5文字の英単語5つで25文字使う組み合わせ、ないんですね。ちょっと意外でした。

というわけでこのGoプログラムから得られた知見を、6つの英単語の問題に活かして高速化できるかなと思い、探索の再帰関数化や枝刈りやビット演算の多用で少し試行錯誤しましたが、結論として、またもや速くはなりませんでした。コードがスッキリしたし、ビット演算は書いてておもしろくて良かったのですが。5つの英単語の問題は「1文字もかぶってはいけない」分、ぼくが提示した6つの英単語の問題に比べて圧倒的にシンプルで簡単なため、2つの問題は似てるようでいて、ずいぶん性質が異なりますね。6つの英単語の問題に関しては、どうもぼくがやった枝刈りが効いてるようです。

それにしても、この記事をnoteに書いたことで、そのあとどうしても考え続けてしまう中でいろいろな発見があり、追記し、勉強になっているので、「書く」って不思議な行為ですね。

ビットフラグなど記事の後半で考察したことは反映してないですが、プログラムの部分は夏休みの1日の苦労（そのあともごちゃごちゃいじってて1日どころではない）に対して1000円です。またふと思いついた問題の解き方を考える時に、コメダ珈琲で粉チーズとタバスコをかけてナポリタンを食べます。