Wordleの判定アルゴリズム

 まずはこちらをご覧ください。

灰色だと答えにその文字は含まれないと言ったな？スマンあれは嘘だ。

解説

よくWordleでは以下のような説明がされます。

• 緑だとその文字がその場所で使われる
• 黄だとその文字が別の場所で使われる
• 灰だとその文字は使われていない
  

5文字すべてが異なる場合に限っては合っています。ただ、同じ文字が2個以上含まれる場合はそうとは言えなくなるようです。

上の例のように答えがsloshでdrillを入力した場合、箇条書きで書いたルールに従って判定するとになります。なぜなら、4文字目のlも5文字目のlもlであることには変わりなく、答えの2文字目とは異なる場所で使われているためです。でも実際に4文字目のlしか色が付きません。

一方で、答えがsloshでassetを入力した場合、となりました。どちらのsも色が付いています。これは、答えの単語にsが2回使われていることが影響していると考えられます。

crossやfloodを入力した結果を見ても明らかだと思います。この挙動は、「文字の場所」というよりかは「文字の入れ替え」を意識した挙動だと考えることができます。そのほうが人間にはより直感的に理解できますからね。そして、ゲームとしても同じ文字が2個以上含まれる単語を入れても「文字数」という情報を入手することができるということになります。

実装

さて、前回の記事などでもいろいろと解析してきましたが、そもそもの判定アルゴリズムが誤っていたのですから実装しなおさなければなりません。

まずはWordleの挙動と同じように色付けをするコードを実装してみます。

static WordHint MakeHint(string input, string target)
{
	var len = Math.Min(input.Length, target.Length);
	var assigned = new bool[len];

	var ret = new WordHint(input);

	// 緑を探す
	for(int i = 0; i < len; i++) {
		if(input[i] == target[i]) {
			assigned[i] = true;
			ret.Characters[i].Hint = HintState.ExactPosition;
		}
	}

	// 黄色を探す
	for(int i = 0; i < len; i++) {
		if(ret.Characters[i].Hint != HintState.ExactPosition) {
			for(int j = 0; j < len; j++) {
				if(!assigned[j] && input[i] == target[j]) {
					assigned[j] = true;
					ret.Characters[i].Hint = HintState.NotInPosition;
					break;
				}
			}
		}
	}

	return ret;
}

こんな感じでしょうか。「入れ替え」を前提にした処理をしなければならないため、二重ループにする必要があります。

つづいて、与えられた単語とWordleの判定結果からそれを満たす単語を返すメソッドを作っていきましょう。

public static IReadOnlySet<string> Nominate(IEnumerable<IWordHint> hints, IReadOnlySet<string> words)
{
	// 入力単語の文字ごとにグループを作る
	var chargroup = hints.SelectMany(p => p.Characters.Select((p, i) => (character: char.ToLower(p.Character), pos: i, hint: p.Hint)).GroupBy(p => p.character)).ToArray();
	foreach(var cg in chargroup) {
		var count = cg.Count();		// グループの要素数=入力単語でその文字が使われている回数
		var coloredcount = cg.Where(p => p.hint != HintState.NotContained).Count();	// グループのうち色が付いている文字数

		if(count > coloredcount) {  // この条件のとき、ちょうどcoloredcount回その文字が使われている語がヒットする
			var filtered = new SortedSet<string>();
			foreach(var w in words) {
				if(w.Where(p => p == cg.Key).Count() == coloredcount &&		// ちょうどcoloredcount回その文字が使われていて
				   cg.Where(p => p.hint == HintState.ExactPosition).All(p => w[p.pos] == p.character) &&    // 緑色がそこに使われていて
				   cg.Where(p => p.hint == HintState.NotInPosition).All(p => w[p.pos] != p.character))    // 黄色がそこに使われていない
					filtered.Add(w);						
			}
			words = filtered;
		} else {    // このときはcoloredcount回以上使われている
			var filtered = new SortedSet<string>();
			foreach(var w in words) {
				if(w.Where(p => p == cg.Key).Count() >= coloredcount &&		// coloredcount回以上その文字が使われているとき
				   cg.Where(p => p.hint == HintState.ExactPosition).All(p => w[p.pos] == p.character) &&  // 緑色がそこに使われていて
				   cg.Where(p => p.hint == HintState.NotInPosition).All(p => w[p.pos] != p.character))    // 黄色がそこに使われていない
					filtered.Add(w);
			}
			words = filtered;
		}
	}

	return words;
}

こっちは結構頭を使いました。ヒントの文字数を数えるところから始めます。

例えばdrillという単語が与えられ、という判定結果となったとします。まずは文字種でグルーピングします。

d:
r:
i:
l:

という判定結果になります。これらそれぞれのグループの要素数と、色が付いている（＝黄＋緑の）要素の数をそれぞれ数えます。

d: 1, 0
r: 1, 0
i: 1, 0
l: 2, 1

(グループの要素数) > (色が付いている要素の数)の場合、答えの単語ではちょうど(色が付いている要素の数)だけその文字が含まれることがわかります。今回はd, r, i, lすべての文字がこの条件を満たしていますので、答えの単語はそれぞれの文字が0, 0, 0, 1個ずつ含まれるということがわかります。あとは、文字が含まれている場合は緑ならその場所、黄色なら異なる場所という判定をしてやればいいです。すでに文字数の判定は済ませてあるので、1個目のlがどこに割り当てられて…などと考える必要もありません。

(グループの要素数) = (色が付いている要素の数)の場合、答えの単語でその文字は(色が付いている要素の数)個以上使われていると言えます。あとは同様に緑か黄色かで場所を判断してやればいいだけです。

再評価

前回の記事でalertやtrailあたりが1語目に良いという判断をしました。これらの手数を、この修正したアルゴリズムで再評価してみました。

alert

お題	検索母集団	最小手数	平均手数	最大手数
過去問	frequent→common→all	2	3.6667	6
過去問	common→all	2	3.8551	6
過去問	all	2	4.2138	9
frequent	frequent→common→all	1	3.1905	6
frequent	common→all	1	3.8057	7
frequent	all	1	4.2008	8
common	frequent→common→all	1	3.8876	10
common	common→all	1	3.8309	9
common	all	1	4.2571	9
all	frequent→common→all	1	4.5722	13
all	common→all	1	4.5432	13
all	all	1	4.4346	11

trail

お題	検索母集団	最小手数	平均手数	最大手数
過去問	frequent→common→all	2	3.6268	7
過去問	common→all	2	3.8333	7
過去問	all	2	4.2174	9
frequent	frequent→common→all	1	3.1879	5
frequent	common→all	1	3.7902	7
frequent	all	1	4.1519	7
common	frequent→common→all	1	3.8908	9
common	common→all	1	3.8353	8
common	all	1	4.2505	9
all	frequent→common→all	1	4.6055	11
all	common→all	1	4.5181	12
all	all	1	4.4344	12

ほとんど差はありませんでしたが、アルゴリズム修正前より平均手数は微減のようです。そりゃ同じ文字があった時の情報量が微妙に増えるのですから、そうでしょう。

一方で、計算時間は結構長くなりました。まあ、複雑になったから仕方ないですね。現状のプログラムではこの本体のアルゴリズム外のところにもう少し改善の余地はありますが、本筋とは関係ないのでぼちぼちやっていくこととしましょう。

余談

Wordleに初回アクセスした際に次のようなイントロダクションが表示されます。 

"The letter U is not in the word in any spot."って書いてあるけど嘘やんけ！！！