導入
こんにちは。
ランターンです。
（結論ファースト）
皆さんは、ポケモンWordleというゲームをご存知でしょうか。
ルールについては知っている方も多いので、ここでは改めて紹介はしません（気になる方は上記URLより確認＆実際にプレイしてみることをお勧めします）。
今回は、人類にとっての永遠の謎、
という問題を考えていきます。
何をもって「最適」とするか
例えば、以下の2組のポケモン名があったとします：
このとき、
名前が似通っているポケモンの組は？
と聞かれた場合、皆さんはどちらを答えますか。
十中八九がAと答えますよね。
理由は、単純で、ピカチュウとライチュウはチュウの部分が同じだからです。 逆に、ピカチュウとスターミーは1文字も掠っていません。 Aの組は2文字違いなのに対して、Bの組は5文字違いなわけです。
さて、このように、異なる2つの文字列が与えられたとして、それらがどれだけ離れているかについては、数値化ができそうです。
というわけで、今回は
という流れで、諸々を定義、実装していきます。
（あ、今回結構まじめな記事なんだ）
距離の導入
さて、距離には、距離の公理と呼ばれる性質があります。
詳細はWikipediaを参照してください。
数学にあまりなじみのない方は、距離と聞くと
ある地点とある地点の道のり
を思い浮かべると思います。
数学の世界では、このイメージに挙げられるような2点間の距離をより一般化して、例えば、関数間の距離や集合間の距離を定義します。
また、2点間の距離と言っても、直線距離（ユークリッド距離）や、碁盤の目に沿った距離（マンハッタン距離）など、その測り方は様々です。
そんな感じで、点や集合、関数については、さまざまな距離を考えることができます。
文字列もまた、言うなれば「記号の集合」ですので、何か適切な距離が定義できそうですね。
というわけで少し調べてみますと…
ありました。
上記URL内で解説されているレーベンシュタイン距離（編集距離）が、 文字列間の距離の定義としてちょうどよさそうです。
編集距離について少し解説します。
編集距離とは、以下の4つの手順を繰り返し、ある文字列がある文字列に最短で何手で一致するかを算出する値になります：
- 文字の追加
- 文字の置換
- 文字の削除
例えば最初の例であれば、 ピカチュウはライチュウという文字列にするためにピカとライの2文字置換するわけですから、編集距離は2となります。
同じように考えると、ピカチュウとスターミーの間の編集距離は5になります。
また、例えばオタチをオオタチにするには先頭にオを1文字追加すればいいですし、 逆にオオタチをオタチにするには先頭のオを1文字削除すればよいでしょう。
なお、この編集距離は、距離の公理を満たします。
軽く確認をしましょう。
（本当はしっかり証明を書こうと思ったのですが、そのためには文字列の同値を定義する必要があって、そもそも50音の定義が必要になって、…と、どんどん本筋のポケモンWordleから離れて行ってしまうので、さっと考え方だけ確認します。）
非退化性
任意の文字列XをXに変えるために行う手順は0手です（はじめから一致しているため）。 よって編集距離は0です。
また、編集距離が0以外であるとき、つまり最低でも1手は処理を行わないと一致しない文字列同士は、文字列の意味で異なるものでしょう。
対称性
ある文字列Xを別の文字列Yに変える際の編集距離がdとします。 文字列Yから文字列Xに変えるときは文字列Xから文字列Yに変えるときの手順を逆にたどればよいので、文字列Yと文字列Xの編集距離もまたdとなります。
三角不等式
背理法を使うのが良いです。ある文字列X, Y, Zで三角不等式を満たさないものがある場合、手順を最小性に矛盾が生じるでしょう。
…少し長くなりましたが、一旦まとめましょう。
ポケモンの名称間の編集距離を算出すれば、ポケモンWordle初手に最適な回答は何か問題のひとつの答えが出せそうですね。
ポケモンのデータ取得
というわけで、今度はデータを取得します。
ポケモンの名称一覧を簡単に取得できる方法はないかな～、と思っていたところ、次のようなAPIを見つけました。
PokeAPI。 名前の通りポケモンに関する情報を取得できる無料APIのようです。
ドキュメントが英語なので、ひょえ～（地声）となりましたが、勇気を出して読んでみるとポケモンの内容なので、そこまで難しくなかったり。
利用できそうなのは、以下のURLでしょうか：
世代ごとのポケモンの情報を取得する
https://pokeapi.co/api/v2/generation/{ポケモンの世代}
例えば
https://pokeapi.co/api/v2/generation/3
とすれば、第3世代、すなわちホウエン地方のポケモンの情報をJSON形式で取得することができます：
各ポケモンの情報を取得する
上記のpokemon_species内のurlがのような形になっています：
https://pokeapi.co/api/v2/pokemon-species/{ポケモンの図鑑番号}
これは、各ポケモンの情報を取得するためのものです。
例えば
https://pokeapi.co/api/v2/generation/252/
とすれば、図鑑番号252のポケモン、すなわちキモリの情報を取得できます。
…とこんな感じで、
ということを繰り返すことで全ポケモンのデータを取得できそうです。 （ちなみに、PokeAPIには、ポケモン全取得に相当する機能はありません。）
…となると、900回近くのリクエストを毎回発行することになりますね。
ちょっと、このままだと毎回処理を実行するのは重いし、リクエスト投げすぎで向こうのサーバに負荷がかかってしまうので、処理フローを見直します。
今回実装の際には以下の2つのバージョンを作成します：
ダウンロードバージョン
算出バージョン
exeは一つにして、上記2つの機能をオプションで使い分ける、といった作りがよさそうです。
実装を始める
- 使用言語：C#
- ターゲット：.Net Framework 4.8
まずはじめに、ポケモンに関連するクラスを作成していきます。
Generation.cs
/// <summary>
/// 世代を表す列挙子。
/// </summary>
public enum Generation : int
{
/// <summary>
/// 赤・緑。
/// </summary>
RG = 1,
/// <summary>
/// 金・銀。
/// </summary>
GS = 2,
/// <summary>
/// ルビー・サファイア。
/// </summary>
RS = 3,
/// <summary>
/// ダイヤモンド・パール。
/// </summary>
DP = 4,
/// <summary>
/// ブラック・ホワイト。
/// </summary>
BW = 5,
/// <summary>
/// X・Y。
/// </summary>
XY = 6,
/// <summary>
/// サン・ムーン。
/// </summary>
SM = 7,
/// <summary>
/// ソード・シールド。
/// </summary>
SS = 8,
}
Monster.cs
/// <summary>
/// モンスター。
/// </summary>
public class Monster
{
/// <summary>
/// インスタンスを初期化します。
/// </summary>
/// <param name="id">図鑑番号。</param>
/// <param name="name">名称。</param>
/// <param name="generation">世代。</param>
public Monster(MonsterID id, MonsterName name, Generation generation)
{
this.ID = id;
this.Name = name;
this.Generation = generation;
}
/// <summary>
/// 図鑑番号。
/// </summary>
public MonsterID ID { get; }
/// <summary>
/// 名称。
/// </summary>
public MonsterName Name { get; }
/// <summary>
/// 世代。
/// </summary>
public Generation Generation { get; }
}
次に編集距離に関連するクラスを作成し、そこに編集距離算出ロジックを記述します。
EditDistance.cs
/// <summary>
/// レーベンシュタイン編集距離。
/// </summary>
public class EditDistance : IEquatable<EditDistance>
{
/// <summary>
/// インスタンスを初期化します。
/// </summary>
/// <param name="value">値。</param>
public EditDistance(int value = 0)
{
if (!IsValue(value))
{
throw new ArgumentException();
}
this.Value = value;
}
/// <summary>
/// 値。
/// </summary>
public int Value { get; }
public static bool operator ==(EditDistance left, EditDistance right)
{
return left.Value == right.Value;
}
public static bool operator !=(EditDistance left, EditDistance right)
{
return !(left == right);
}
/// <summary>
/// 2つの文字列の編集距離を算出します。
/// </summary>
/// <param name="text1">文字列1。</param>
/// <param name="text2">文字列2。</param>
/// <returns>編集距離。</returns>
public static EditDistance GetEditDistance(string text1, string text2)
{
_ = text1 ?? throw new ArgumentNullException(nameof(text1));
_ = text2 ?? throw new ArgumentNullException(nameof(text2));
if (text1.Length == 0)
{
return new EditDistance(text2.Length);
}
if (text2.Length == 0)
{
return new EditDistance(text1.Length);
}
if (text1[0] == text2[0])
{
return GetEditDistance(text1.Substring(1), text2.Substring(1));
}
var costForAdd = GetEditDistance(text1, text2.Substring(1));
var costForRemove = GetEditDistance(text1.Substring(1), text2);
var costForChange = GetEditDistance(text1.Substring(1), text2.Substring(1));
var minCost = new[] { costForAdd, costForRemove, costForChange, }.Min(d => d.Value);
return new EditDistance(1 + minCost);
}
/// <inheritdoc/>
public override int GetHashCode()
{
return new { this.Value, }.GetHashCode();
}
/// <inheritdoc/>
public override bool Equals(object obj)
{
return obj is EditDistance other && this.Equals(other);
}
/// <inheritdoc/>
public override string ToString()
{
return this.Value.ToString();
}
/// <inheritdoc/>
public bool Equals(EditDistance other)
{
return this == other;
}
private static bool IsValue(int value)
{
return value >= 0;
}
}
なお、編集距離算出ロジックは以下のサイトをパクリました…、
ゴホンゴホン。
C#に書き起こしました（りっぱ！）：
次に、算出結果を記録するためのクラスを作成しておきます。
Result.cs
/// <summary>
/// 算出結果。
/// </summary>
public class Result
{
/// <summary>
/// インスタンスを初期化します。
/// </summary>
/// <param name="monster">算出対象。</param>
/// <param name="average">編集距離の平均値。</param>
public Result(Monster monster, decimal average)
{
this.Monster = monster;
this.Average = average;
}
/// <summary>
/// 算出対象。
/// </summary>
public Monster Monster { get; }
/// <summary>
/// 平均距離の平均値。
/// </summary>
public decimal Average { get; }
}
次に、リポジトリを作成します。
今回、Input/Outputを行う対象は
の2つですので、それに対してリポジトリを定義します：
IMonsterRepository.cs
/// <summary>
/// <see cref="Monster"/>のリポジトリ。
/// </summary>
public interface IMonsterRepository
{
/// <summary>
/// <see cref="Monster"/>を全件取得します。
/// </summary>
/// <returns><see cref="Monster"/>の一覧。</returns>
IEnumerable<Monster> GetMonsters();
/// <summary>
/// <see cref="Monster"/>の一覧を追加します。
/// </summary>
/// <param name="monsters"><see cref="Monster"/>の一覧。</param>
void AddRange(IReadOnlyCollection<Monster> monsters);
}
IResultRepository.cs
/// <summary>
/// <see cref="Result"/>のリポジトリ。
/// </summary>
public interface IResultRepository
{
/// <summary>
/// <see cref="Result"/>の一覧を追加します。
/// </summary>
/// <param name="results"><see cref="Result"/>の一覧。</param>
void AddRange(IReadOnlyCollection<Result> results);
}
ここまだやったら、いったん全体の処理フローに合わせて、実処理を実装します。
まずは以下のようなinterfaceを用意して、
IMonsterService.cs
/// <summary>
/// サービスクラスのインターフェース。
/// </summary>
public interface IMonsterService
{
/// <summary>
/// 処理を実行します。
/// </summary>
void Execute();
}
ダウンロード用の実装クラスと、
MonsterDownloadService .cs
/// <summary>
/// <see cref="IMonsterService"/>の実装クラス。
/// </summary>
/// <remarks>ダウンロード用。</remarks>
public class MonsterDownloadService : IMonsterService
{
private readonly IMonsterRepository inputRepository;
private readonly IMonsterRepository outputRepository;
/// <summary>
/// インスタンスを初期化します。
/// </summary>
/// <param name="inputRepository">入力用リポジトリ。</param>
/// <param name="outputRepository">出力用リポジトリ。</param>
public MonsterDownloadService(IMonsterRepository inputRepository, IMonsterRepository outputRepository)
{
this.inputRepository = inputRepository;
this.outputRepository = outputRepository;
}
/// <inheritdoc/>
public void Execute()
{
var monsters = this.inputRepository.GetMonsters();
this.outputRepository.AddRange(monsters.ToArray());
}
}
算出処理用の実装クラスを作成します：
MonsterDistanceService .cs
/// <summary>
/// <see cref="IMonsterService"/>の実装クラス。
/// </summary>
/// <remarks>編集距離算出用。</remarks>
public class MonsterDistanceService : IMonsterService
{
private readonly IMonsterRepository monsterRepository;
private readonly IResultRepository resultRepository;
/// <summary>
/// インスタンスを初期化します。
/// </summary>
/// <param name="monsterRepository"><see cref="Monster"/>に関するリポジトリ。</param>
/// <param name="resultRepository"><see cref="Result"/>に関するリポジトリ。</param>
public MonsterDistanceService(IMonsterRepository monsterRepository, IResultRepository resultRepository)
{
this.monsterRepository = monsterRepository;
this.resultRepository = resultRepository;
}
/// <inheritdoc/>
public void Execute()
{
var monsters = this.monsterRepository.GetMonsters().ToArray();
// 編集距離を算出
var results = this.GetResults(monsters);
// 算出結果を出力する
this.resultRepository.AddRange(results.ToArray());
}
private IEnumerable<Result> GetResults(IReadOnlyCollection<Monster> monsters)
{
foreach (var monster in monsters)
{
// 各モンスターごとに編集距離の平均を算出する
var average = monsters.Average(x => (decimal)EditDistance.GetEditDistance(monster.Name.Value, x.Name.Value).Value);
yield return new Result(monster, average);
}
}
}
あとは、リポジトリの実装を行えば完成しそうです。
今回作成するのは
の2つです。
前者は以下のように実装を行います：
WebAPIRepositoryBase.cs
/// <summary>
/// WebAPIリポジトリの基底クラス。
/// </summary>
public abstract class WebAPIRepositoryBase
{
/// <summary>
/// HTTPクライアント。
/// </summary>
private static readonly HttpClient Client = new HttpClient();
/// <summary>
/// インスタンスを初期化します。
/// </summary>
public WebAPIRepositoryBase()
{
}
/// <summary>
/// <paramref name="url"/>に対してリクエストを送信し、そのレスポンスをjson形式で非同期に取得します。
/// </summary>
/// <param name="url">URL。</param>
/// <returns>json形式の文字列。</returns>
/// <exception cref="InvalidOperationException">HTTPステータスが<see cref="HttpStatusCode.OK"/>以外だった場合。</exception>
protected async Task<string> GetJson(string url)
{
var response = await Client.GetAsync(url);
if (response.StatusCode != HttpStatusCode.OK)
{
throw new InvalidOperationException();
}
var content = await response.Content.ReadAsStringAsync();
return content;
}
}
MonsterWebAPIRepository .cs
/// <summary>
/// <see cref="IMonsterRepository"/>のWebAPI実装リポジトリ。
/// </summary>
public class MonsterWebAPIRepository : WebAPIRepositoryBase, IMonsterRepository
{
/// <summary>
/// 取得した<see cref="Monster"/>の一覧。
/// </summary>
/// <remarks>繰り返しリクエストしないように内部メモリに保持します。</remarks>
private IEnumerable<Monster> monsters;
/// <summary>
/// インスタンスを初期化します。
/// </summary>
public MonsterWebAPIRepository()
{
}
/// <inheritdoc/>
public void AddRange(IReadOnlyCollection<Monster> monsters)
{
throw new NotImplementedException();
}
/// <inheritdoc/>
public IEnumerable<Monster> GetMonsters()
{
if (this.monsters == null)
{
// 未取得時→リクエスト送信
this.monsters = this.GetMonsterAsync().GetAwaiter().GetResult().OrderBy(x => x.ID.Value);
}
return this.monsters;
}
/// <summary>
/// <see cref="Monster"/>の一覧を非同期処理で取得します。
/// </summary>
/// <returns><see cref="Monster"/>の一覧。</returns>
private async Task<IEnumerable<Monster>> GetMonsterAsync()
{
var client = new HttpClient();
var monsters = new List<Monster>();
foreach (var generation in (Generation[])Enum.GetValues(typeof(Generation)))
{
// 世代ごとの情報を取得する
var jsonOfGeneration = await this.GetJson($"https://pokeapi.co/api/v2/generation/{(int)generation}");
var jObjectOfGeneration = JObject.Parse(jsonOfGeneration);
// 世代ごとのポケモンの詳細を取得する
var species = (JArray)jObjectOfGeneration.SelectToken("pokemon_species");
var urls = species.Select(x => x.SelectToken("url"));
foreach (var url in urls)
{
var jsonOfMonster = await this.GetJson(url.ToString());
var jObjectOfMonster = JObject.Parse(jsonOfMonster);
var id = int.Parse(jObjectOfMonster.SelectToken("id").ToString());
var names = (JArray)jObjectOfMonster.SelectToken("names");
var jaName = names.Single(x => x.SelectToken("language.name").ToString() == "ja").SelectToken("name").ToString();
monsters.Add(new Monster(new MonsterID(id), new MonsterName(jaName), generation));
}
}
return monsters;
}
}
後者はNugetよりCsvHelperを取得して、こんな感じで実装します：
FileRepositoryBase.cs
/// <summary>
/// ファイルリポジトリの基底クラス。
/// </summary>
public abstract class FileRepositoryBase
{
/// <summary>
/// インスタンスを初期化します。
/// </summary>
/// <param name="filePath">ファイルパス。</param>
public FileRepositoryBase(string filePath)
{
this.FilePath = filePath;
}
/// <summary>
/// ファイルパス。
/// </summary>
protected string FilePath { get; }
}
CsvFileRepositoryBase .cs
/// <summary>
/// csvファイルリポジトリの基底クラス。
/// </summary>
public abstract class CsvFileRepositoryBase : FileRepositoryBase
{
/// <summary>
/// エンコード。
/// </summary>
protected static readonly Encoding Encoding = Encoding.GetEncoding("shift_jis");
/// <summary>
/// csvファイルの入出力に関する設定。
/// </summary>
protected static readonly CsvConfiguration Configuration = new CsvConfiguration(System.Globalization.CultureInfo.InvariantCulture)
{
Encoding = Encoding,
Delimiter = ",",
HasHeaderRecord = true,
};
/// <summary>
/// インスタンスを初期化します。
/// </summary>
/// <param name="filePath">ファイルパス。</param>
public CsvFileRepositoryBase(string filePath)
: base(filePath)
{
}
/// <summary>
/// <typeparamref name="T"/>の一覧を書き出します。
/// </summary>
/// <typeparam name="T">モデルクラスの型。</typeparam>
/// <param name="models">モデルの一覧。</param>
protected void Write<T>(IReadOnlyCollection<T> models)
{
using (var stream = File.OpenWrite(this.FilePath))
{
using (var writer = new CsvWriter(new StreamWriter(stream, Encoding), Configuration))
{
writer.WriteRecords(models);
}
}
}
/// <summary>
/// <typeparamref name="T"/>の一覧を読み込みます。
/// </summary>
/// <typeparam name="T">モデルクラスの型。</typeparam>
/// <returns>モデルの一覧。</returns>
protected IEnumerable<T> Read<T>()
{
using (var stream = File.OpenRead(this.FilePath))
{
using (var reader = new CsvReader(new StreamReader(stream, Encoding), Configuration))
{
var models = reader.GetRecords<T>().ToArray();
return models;
}
}
}
}
MonsterCsvFileRepository .cs
/// <summary>
/// <see cref="IMonsterRepository"/>のcsvファイル実装リポジトリ。
/// </summary>
public class MonsterCsvFileRepository : CsvFileRepositoryBase, IMonsterRepository
{
/// <summary>
/// インスタンスを初期化します。
/// </summary>
/// <param name="filePath">ファイルパス。</param>
public MonsterCsvFileRepository(string filePath)
: base(filePath)
{
}
/// <inheritdoc/>
public void AddRange(IReadOnlyCollection<Monster> monsters)
{
var models = monsters.Select(x => new MonsterCsvModel { ID = x.ID.Value, Name = x.Name.Value, Generation = (int)x.Generation, }).ToArray();
this.Write(models);
}
/// <inheritdoc/>
public IEnumerable<Monster> GetMonsters()
{
var models = this.Read<MonsterCsvModel>();
return models.Select(x => new Monster(new MonsterID(x.ID), new MonsterName(x.Name), EnumUtils.Convert<Generation>(x.Generation)));
}
private class MonsterCsvModel
{
[Name(nameof(ID))]
public int ID { get; set; }
[Name(nameof(Name))]
public string Name { get; set; }
[Name(nameof(Generation))]
public int Generation { get; set; }
}
}
ResultCsvFileRepository .cs
/// <summary>
/// <see cref="IResultRepository"/>のcsvファイル実装リポジトリ。
/// </summary>
public class ResultCsvFileRepository : CsvFileRepositoryBase, IResultRepository
{
/// <summary>
/// インスタンスを初期化します。
/// </summary>
/// <param name="filePath">ファイルパス。</param>
public ResultCsvFileRepository(string filePath)
: base(filePath)
{
}
/// <inheritdoc/>
public void AddRange(IReadOnlyCollection<Result> results)
{
var models = results.Select(x => new ResultCsvModel { ID = x.Monster.ID.Value, Name = x.Monster.Name.Value, Generation = (int)x.Monster.Generation, Average = x.Average, }).ToArray();
this.Write(models);
}
private class ResultCsvModel
{
[Name(nameof(ID))]
public int ID { get; set; }
[Name(nameof(Name))]
public string Name { get; set; }
[Name(nameof(Generation))]
public int Generation { get; set; }
[Name(nameof(Average))]
public decimal Average { get; set; }
}
}
csvには世代は数値で記述されていますので、それを世代の列挙子（Generation.cs）へ変換する処理があったほうがよさそうです。なので、上記csvリポジトリでは以下のメソッドを読んでいます：
EnumUtils.cs
/// <summary>
/// 列挙子に関するユーティリティクラス。
/// </summary>
public static class EnumUtils
{
/// <summary>
/// <paramref name="value"/>を<typeparamref name="TEnum"/>型の列挙子に変換します。
/// </summary>
/// <typeparam name="TEnum">列挙子の型。</typeparam>
/// <param name="value">変換対象。</param>
/// <returns>変換後の列挙子。</returns>
/// <exception cref="InvalidCastException">変換失敗時。</exception>
public static TEnum Convert<TEnum>(object value)
where TEnum : struct
{
if (Enum.TryParse(value.ToString(), out TEnum result) && Enum.IsDefined(typeof(TEnum), result))
{
return result;
}
throw new InvalidCastException($"{nameof(TEnum)}型の列挙子変換に失敗しました：{value}");
}
}
最後に、オプションの指定はコマンドライン引数から行います。 実行イメージとしては、
[アプリ名].exe [-d:ダウンロードモード]
といった感じでしょうか。 あとはコマンドラインに応じて呼ぶサービスを変更すればOKです。
こんな感じでアプリができました。
作成したアプリ実行する
試しにダウンロードモードを実行すると…
！！
csvが出力されました。 中身を見てみると、フシギダネからバドレックスまでの全898体がちゃんと記載されています（ポケモンってそんなにいるのかよ）。
この調子で、算出モードも実行してみましょう。 ぽちぽち。
おお。
なんだかうまく計算できている気がします。
あとは「Average」列をキーとして、昇順にソートすれば、 ポケモンWordleの最適な初手は何かが判明するはずです。
ぽちぽち。
…
…！！
優勝はブルーでした。
ちなみに、僕はえっちなので、ポケモンのブルーよりも、おっぱいにモンスターボールを入れていたブルーの方が好きです。
考察
さて、このブログの冒頭で、最適な初手はランターンだと言っていたので、
「結論ファーストはいいけどさあ、
間違っていることを言ったらだめなんじゃないの？」
というクソ上司読者の声が聞こえてきそうです。
さて、この辺りを考えていきます。
上位20位のポケモンを見ていくと、以下のような性質が見えてきます。 それは、
文字数が少ない
ということです。
はい。
今回編集距離を算出するにあたり、文字の少なさというのは、大きな影響を持っています。
ピカチュウをヒトカゲにするには、必ず1文字削除という処理が現れます。
これはヒトカゲでなくて、ゼニガメでもそうですし、結構文字が似ているピチューでもそうです。
ピカチュウを4文字のポケモンに変えるには、多くて5文字変える必要が出てきます。
一方、4文字同士のポケモンで編集距離を測ると、それは多くても4です。
いくら進化ごとに名前の系統が似ているといっても、900匹もポケモンがいればそれは無作為な文字列としてみてもよいでしょうから、全文字総入れ替えはざらにあるでしょう。
そのときに、やはり文字数が少ない方が全文字総入れ替えの編集距離が少なく算出されますので、上位には文字数の少ないポケモンが多く現れるのではないでしょうか？
（難しく言えば、編集距離関数が文字列長に対して正規化されていないのです。）
さて、今度は
2文字の「ピィ」が1位なんじゃないの？
といった意見が聞こえてきそうです。
ですが、2文字のポケモンはピィ1匹しかいません。 他のポケモンになるには必ず1文字追加しないといけないです。
そうなると「ピ」と「ィ」を含むポケモンが多くないと平均値はなかなか低くならないのかな？と思います。
実際、ポケモンでは「ル」や「ー」は頻出ですので、その点「ブルー」は平均値が小さかったとも考えられますね。 他の上位のポケモンを見てみても「ル」や「ー」、あとは「ン」が多いですし。
正規化を図る
ところで、実際のポケモンWordleでは、ターゲットとなるポケモンや、基本的に回答に使用するポケモンは5文字のポケモンです。
また、「今日のお題」ではダイパまでのポケモンがお題として設定されます。 なので、ダイパ世代までの5文字のポケモンに限定して再度算出を行えば、
うえに、文字列が固定長なので
- 編集距離が実質正規化される
ということとなります。こちらの方が有効なデータっぽい気がしますので、これで再度算出を行ってみます。
実装しなおし
算出用プログラムをこのように書き換えます：
MonsterDistanceService .cs
/// <summary>
/// <see cref="IMonsterService"/>の実装クラス。
/// </summary>
/// <remarks>編集距離算出用。</remarks>
public class MonsterDistanceService : IMonsterService
{
// コンストラクタとフィールドは省略
/// <inheritdoc/>
public void Execute()
{
// 1～4世代のポケモンで、名前が5文字のものを取得する
var generations = new Generation[] { Generation.RG, Generation.GS, Generation.RS, Generation.RS, };
var monsters = this.monsterRepository.GetMonsters().Where(x => x.Name.Value.Length == 5 && generations.Contains(x.Generation)).ToArray();
// 編集距離を算出
var results = this.GetResults(monsters);
// 算出結果を出力する
this.resultRepository.AddRange(results.ToArray());
}
private IEnumerable<Result> GetResults(IReadOnlyCollection<Monster> monsters)
{
foreach (var monster in monsters)
{
// 各モンスターごとに編集距離の平均を算出する
var average = monsters.Average(x => (decimal)EditDistance.GetEditDistance(monster.Name.Value, x.Name.Value).Value);
yield return new Result(monster, average);
}
}
}
これで計算結果を算出すると…
はい。
ランターンが優勝です。
実際に試してみる
それでは最後に、本日のWordleのお題で、ランターンで勝負してみましょう。
Wordleはわりと運ゲーですが、それを凌駕するロジックの力。
見せてやりますよ。
