Wordle で遊んでいると、「使う文字が4文字までわかって、あとは4+1文字を組み合わせるだけ」のような状況があるかと思います。そこまで行ったら全てのパターンを作ったらよいのではないかと思い、基数変換の関数を作って全パターンを列挙しました。
実行環境
Wordle とは
5文字からなる英単語を当てるゲームです。単語は日替わりで、6回まで挑戦できます。単語を入力すると、正解の単語に含まれている文字は黄色、正解に含まれていて位置まで合っている文字は緑色、含まれていない文字は黒、という風に文字の背景色が変化しますので、それを見て正解を予想します。
考え方
使う4文字を 'H', 'L', 'O', 'T'、未確認の1文字を '_' とします。計5文字を5つ組み合わせると 55 = 3125 通りできるので、0から3124までの数を 00000, 00001, 00002, 00003, 00004, 00010, 00011, ... , 44442, 44443, 44444 と5進法で表し、
'0' → 'H' '1' → 'L' '2' → 'O' '3' → 'T' '4' → '_'
という風に置換すれば全パターンできます。あとは正規表現でフィルターをかければいいです。
5進法を使う理由は前回の記事をお読みください。
完成形
前回の記事で作った基数変換の関数 radixConversion
と padWithZero
を流用します。
// 1つの整数を229進法に変換する関数 // int -> string let radixConversionOneChar number = match number with | var when var <= 9 -> string number // 0-9 | var when var <= 35 -> number - 10 + (int 'A') |> char |> string // A-Z | var when var <= 61 -> number - 36 + (int 'a') |> char |> string // a-z | var when var <= 144 -> number - 62 + ('ぁ' |> char |> int) |> char |> string // ぁ-ん | var when var <= 228 -> number - 145 + ('ァ' |> char |> int) |> char |> string // ァ-ヴ | _ -> "";; // 指定した桁数でゼロ埋めする関数 // int -> string -> string let padWithZero digit (text : string) = if digit <= text.Length then text else digit - text.Length // ゼロ埋めのゼロの個数を求める |> string |> (fun x -> (0).ToString("D" + x)) |> (fun x -> x + text);; // 先頭にゼロをつける // これを呼び出す // int -> int -> int -> string let radixConversion radix digit number = // 基数変換の本体となる再帰関数 // int -> int -> int -> string let rec radixConversionRec number radix acc = // 「整数 / 基数」の商 let quotient = number / radix // 商を基数変換したもの let quotientOneChar = radixConversionOneChar quotient // 余りを基数変換したもの let remainderOneChar = number % radix |> radixConversionOneChar match quotient with | var when var < radix -> quotientOneChar + remainderOneChar + acc | _ -> radixConversionRec quotient radix (remainderOneChar + acc) // 基数変換したあとゼロ埋めする radixConversionRec number radix "" |> padWithZero digit;;
全パターン作ってフィルターをかけます。
open System.Text.RegularExpressions // ひとつの文字列に対して、タプルで指定した組み合わせの置換を全て行う関数 // (char * char) array -> string -> string let replaceWithPairs (pairs : (char * char) array) (original : string) = (original, pairs) ||> Array.fold (fun original (oldString, newString) -> original.Replace(oldString, newString));; // 置換する組み合わせのタプルの Array // (odlChar, newChar) let pairs = [| ('0', 'H') ('1', 'L') ('2', 'O') ('3', 'T') ('4', '_') |] let radix = 5 let digit = 5 // 指定した基数・桁数での最大値(0始まりなので - 1 している) let maximum = (double radix) ** (double digit) - 1.0 |> int // 5 ** 5 - 1 = 3124 // 正規表現のパターン let regexPattern = "^[T_][LT_][O_][TO_][H]$";; // 0から最大値までの全ての数を5進法に変換して // 置換して // 目的のパターンに合うものだけ抽出する [|0..maximum|] |> Array.map (radixConversion radix digit) |> Array.map (padWithZero digit) |> Array.map (replaceWithPairs pairs) |> Array.filter (fun x -> Regex.Match(x, regexPattern).Success) |> Array.map (printfn "%s");;
実行結果
この場合は36通りでした。
TLOOH TLOTH TLO_H TL_OH TL_TH TL__H TTOOH TTOTH TTO_H TT_OH TT_TH TT__H T_OOH T_OTH T_O_H T__OH T__TH T___H _LOOH _LOTH _LO_H _L_OH _L_TH _L__H _TOOH _TOTH _TO_H _T_OH _T_TH _T__H __OOH __OTH __O_H ___OH ___TH ____H
あとはこの36パターンの中からそれらしいものを目視で探します。
そうですね。自分で考えた方が楽。
完成形(改)
ここまでやって気づいたのですが、未確認の文字 ('_') があると何が何やらわかりませんので、26進法で全てのパターンを作って正規表現でフィルターをかけた方がいい気がしてきました。
それに伴い、基数変換とゼロ埋めの関数をそれぞれアルファベット特化型に改良します。
// 1つの整数を10進法から26進法(A-Z)に変換する関数 // int -> string let radixConversionOneCharAZ number = match number with | var when var <= 25 -> number + (int 'A') |> char |> string // A-Z | _ -> "";; // 指定した桁数でゼロ埋めする関数。ゼロ以外の文字を指定可能 // string -> int -> string -> string let padWithZero2 stringForZero digit text = if digit <= (String.length text) then text else String.replicate (digit - (String.length text)) stringForZero // ゼロ埋めのゼロの個数を求める |> (fun x -> x + text);; // 先頭にゼロをつける // これを呼び出す // int -> int -> string let radixConversionAZ digit number = // 基数変換の本体となる再帰関数 // int -> int -> string -> string let rec radixConversionRec number radix acc = // 「整数 / 基数」の商 let quotient = number / radix // 商を基数変換したもの let quotientOneChar = radixConversionOneCharAZ quotient // 余りを基数変換したもの let remainderOneChar = number % radix |> radixConversionOneCharAZ match quotient with | var when var < radix -> quotientOneChar + remainderOneChar + acc | _ -> radixConversionRec quotient radix (remainderOneChar + acc) // 基数変換したあと"A"で埋める radixConversionRec number 26 "" |> padWithZero2 "A" digit;;
先ほど同様、全パターン作ってフィルターをかけます。
open System.Text.RegularExpressions // 指定した単語が、指定した文字を全て含んでいるか判定する関数 // string -> string -> bool let allExists charsToBeFound str = String.forall (fun aCharToBeFound -> String.exists (fun c -> c = aCharToBeFound) str ) charsToBeFound;; let radix = 26 let digit = 5 // 指定した基数・桁数での最大値(0始まりなので - 1 している) let maximum = (double radix) ** (double digit) - 1.0 |> int // 26 ** 5 - 1 = 11881375 // 正解に含まれる文字 let usedChars = "HLOT" // 正解に含まれない文字 let notUsedChars= "ERUIADFG" // 正規表現のパターン // 否定文字クラスを使って、正解に含まれない文字と、そのマスには入らない文字を除外 // 文字が確定したマスはその文字を指定 let pattern = System.String.Format("^[^{0}HLO][^{0}HO][^{0}HLT][^{0}HL][H]$", notUsedChars) // "^[^ERUIADFGHLO][^ERUIADFGHO][^ERUIADFGHLT][^ERUIADFGHL][H]$" // 全ての組み合わせの Array を作成 let allConbinations = [|0..maximum|] |> Array.map (radixConversionAZ digit) |> Array.map (padWithZero2 "A" digit);; // 正規表現を使って、使わない文字を含まない組み合わせと、使う文字を全て含む組み合わせだけを抽出 let filteredConbinations = allConbinations |> Array.filter (fun x -> Regex.Match(x, pattern).Success) |> Array.filter (allExists usedChars);; filteredConbinations |> Array.map (printfn "%s");;
実行結果(改)
この場合は44通りでした。
BLOTH CLOTH JLOTH KLOTH MLOTH NLOTH PLOTH QLOTH SLOTH TLBOH TLCOH TLJOH TLKOH TLMOH TLNOH TLOBH TLOCH TLOJH TLOKH TLOMH TLONH TLOOH TLOPH TLOQH TLOSH TLOTH TLOVH TLOWH TLOXH TLOYH TLOZH TLPOH TLQOH TLSOH TLVOH TLWOH TLXOH TLYOH TLZOH VLOTH WLOTH XLOTH YLOTH ZLOTH
あとは目視!
辞書と連携して実在する単語のみを取り出すとかしないとしんどいですね。
ちなみに、実行時間は以下の通りでした。アルファベット5文字の組み合わせ全11,881,375通りを7秒足らずで列挙するなんて、早いなぁ。
> let allConbinations = - [|0..maximum|] - |> Array.map (radixConversionAZ digit) - |> Array.map (padWithZero2 "A" digit);; リアル: 00:00:06.553、CPU: 00:00:06.703、GC 全般0: 410, 全般1: 114, 全般2: 1
> let filteredConbinations = - allConbinations - |> Array.filter (fun x -> Regex.Match(x, pattern).Success) - |> Array.filter (allExists usedChars);; リアル: 00:00:02.135、CPU: 00:00:02.109、GC 全般0: 8, 全般1: 1, 全般2: 0
新たに学んだこと
一括置換のために初めて fold 関数を使いました。初めは自前で再帰関数を定義していたのですが、「こんな関数なかったっけ?」と思って調べたら見つかりました。広く浅く調べて、頭の片隅に置いておくのって大事ですね。存在を知らないことには思いつきようもないですから。
この記事にも書きましたが、||>
演算子との出会いが衝撃的でした。2つの要素を渡すパイプ演算子……PowerShell にもほしい!
関数を定義する時、パラメータの型の注釈(型アノテーション)を書かないとエラーになる場合があったのですが、以下のページによると、パラメータをオブジェクトとして利用する場合は型アノテーションが必要とのことです。実際に str.Length
から (String.length str)
に書き換えたらエラーが消えました。せっかく型を書かなくても動くようにできているので、書かずに済む方法でいこうと思います。
今回の一番の発見は、ゲームをプログラムで解くのは楽しいけれども、楽とは限らないということでした。
結び
「ゲームの遊び方間違ってない?」と言われるのですが、そもそも楽しみ方なんて人それぞれだと思うんですよ。タイムアタックや図鑑コンプ、縛りプレイ etc....それならば「攻略方法の考案」も認められて然るべきではなかろうか。うん。然るべきだな。
それから、私の好きな言葉に
自らが最強である必要はない。我々は最強であるものを創り出すのだ
というのがありまして1、その観点から言っても私はクイズを解くプログラムを作らざるを得ないんですよ。うん。作らないとな。