Regex Golf をやってみた 15 〜Glob〜

Regex Golf 15回目（14回目はこちら）

正規表現によるパズルゲーム？ Regex Golf 11問目 "Glob" です。ワイルドカード * をつかった検索が正しいか調べる？感じの問題です。

左側はマッチングする場合、右側はマッチングしない場合と分かれています。
ワイルドカード文字 * は任意の文字、1文字以上に該当するようです。

以下、ネタバレ

さて、方針ですが単純に左側にマッチする正規表現を探すこととします。
まずは文字列の真ん中、"matches" にマッチする文字列を試してみます。

" matches "

前後にスペースが入っているので、それを含めてみました。
各行の中でスペースが入るのは "matches" の部分だけなので

" .+ "

でも代用できそうです。

次に左側、検索文字列の部分を作ってみます。
行頭から "*" および " " 以外の文字が0文字以上としてみます。

"^([^* ]*)"

行頭から1つめの "*" または " " までがマッチしました。
次に続く "*" があってもよい。としました。

"^([^* ]*)(\*|)"

先ほどマッチした文字列に1つめの "*" を追加した範囲がマッチしました。
"*" がある場合は続いて検索文字列があってもよいため、やはり "*" および " " 以外の0文字以上の文字列を付け足します。

"^([^* ]*)(\*([^* ]*)|)"

1つめの "*" 以降の検索文字列で2つめの "*" または " " までもマッチするようになりました。
後はこれを3つめの "*" まで繰り返すと…

"^([^* ]*)(\*([^* ]*)(\*([^* ]*)(\*|)|)|)"

検索文字列の部分は全てマッチするようになりました。

これに "matches" の部分を付け足し、さらに行末記号をつけます。

"^([^* ]*)(\*([^* ]*)(\*([^* ]*)(\*|)|)|) .+ $"

当然ですが、"matches" に続く文字列が行末までの間にあるため1つもマッチしません。
この状態で、( ) で囲った部分、前方参照は次のようになっています。

1. 行頭から1つめの "*" または " " まで。
   行頭が "*" の場合は空。
2. 1つめの "*" から " " まで。
   "*" が無い場合は空。
3. 1つめの "*" の次の文字から2つめの "*" または " " まで。
   1つめの "*" が無い場合は空。
4. 2つめの "*" から " " まで。
   2つめの "*" が無い場合は空。
5. 2つめの "*" の次の文字から3つめの "*" または " " まで。
   2つめの "*" が無い場合は空。
6. 3つめの "*" から " " まで。
   3つめの "*" が無い場合は空。

これを使って検索対象の文字列にマッチさせていきます。

"^([^* ]*)(\*([^* ]*)(\*([^* ]*)(\*|)|)|) .+ \1\2$"

"*" が無い場合。\2 は空なのでこれでマッチする。

\2 が空でない場合は、否定先読みを使って、\2 が空でない場合だけ、任意の1文字以上の文字列を許可する。

"^([^* ]*)(\*([^* ]*)(\*([^* ]*)(\*|)|)|) .+ \1(\2|(?!\2).+)$"

余分なものが沢山引っかかってしまったが、これで "bowdl*" のようなパターンはマッチするようになった。後は同じ考え方で \3 〜 \6 を追加する。

"^([^* ]*)(\*([^* ]*)(\*([^* ]*)(\*|)|)|) .+ \1(\2|(?!\2).+)\3(\4|(?!\4).+)\5(\6|(?!\6).+)$"

という事で、左側全てにマッチし、右側にはマッチしない正規表現となりました。

後はどこまで省略できるか？ですが、検索文字列の "[^* ]" は " .+ " でスペースを含めるようにしているため、"[^*]" でよいはず。
後は、偶然この例の中では端折ってもいい部分を消すくらいしかありません。

"^([^*]*)(\*([^*]*)(\*([^*]*)(\*|)|)|) .+ \1(\2|(?!\2).+)\3(\4|(?!\4).+)$"

試してみたらここまで減らせました。
この点が高いのか低いのかわかりませんが、Glob も無事解く事ができました。

次回は "Balance" に挑戦予定です。

それでは、また。