タイダログ

もっと怠けますか? (y/n)

F# で Wordle を楽して解きたい

Wordle で遊んでいると、「使う文字が4文字までわかって、あとは4+1文字を組み合わせるだけ」のような状況があるかと思います。そこまで行ったら全てのパターンを作ったらよいのではないかと思い、基数変換の関数を作って全パターンを列挙しました。

実行環境

Wordle とは

www.nytimes.com

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進法を使う理由は前回の記事をお読みください。

完成形

前回の記事で作った基数変換の関数 radixConversionpadWithZero を流用します。

// 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 にもほしい!

taidalog.hatenablog.com

関数を定義する時、パラメータの型の注釈(型アノテーション)を書かないとエラーになる場合があったのですが、以下のページによると、パラメータをオブジェクトとして利用する場合は型アノテーションが必要とのことです。実際に str.Length から (String.length str) に書き換えたらエラーが消えました。せっかく型を書かなくても動くようにできているので、書かずに済む方法でいこうと思います。

docs.microsoft.com

今回の一番の発見は、ゲームをプログラムで解くのは楽しいけれども、楽とは限らないということでした。

結び

「ゲームの遊び方間違ってない?」と言われるのですが、そもそも楽しみ方なんて人それぞれだと思うんですよ。タイムアタックや図鑑コンプ、縛りプレイ etc....それならば「攻略方法の考案」も認められて然るべきではなかろうか。うん。然るべきだな。

それから、私の好きな言葉に

自らが最強である必要はない。我々は最強であるものを創り出すのだ

というのがありまして1、その観点から言っても私はクイズを解くプログラムを作らざるを得ないんですよ。うん。作らないとな。

参考