Regex Golf をやってみた 16 〜Balance〜

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

正規表現によるパズルゲーム？ Regex Golf 12問目 "Balance" です。

パッと見 < と > だけで構成された文字列内の < と > が対になっている事を検出すればOKなようです。

タイトルの横に

This one is also impossible, but there's a finite number of test cases

とあります。
つまり、< と > が対であることを正規表現で検出するのは不可能だけど、ここに挙がっている例は括弧が有限だよ、との事。

< と > が対であり、他の文字が入らないということは、

<>

が必ず出現するという事。試しに条件として入れてみると

右側から2件弾くことが出来ました。
しかし左から1件弾かれてしまいました。
文字列無しも OK にしなければならないようです。

先ほどは <> を検索しましたが、 <> が全く無くても続けて並んでいても良いはずです。
という事で

(<>)*

としてみました。

左側は全てマッチするようになったので良いですが、右側までマッチするようになってしまいました。
こちらが想定した文字列以外はマッチしてほしくないため行頭から行末までの指定を追加します。

右側はマッチなし、左側は3件マッチになりました。
ここから左側のマッチを増やしていきます。

今の検索文字列では括弧の深さが1の場合のみを対象としていましたがもう1段深くても検出可能になるように

^(<(<>)*>)*$

とします。

意図した通り、括弧の深さが2の物もマッチするようになりました。

後は同じ要領で深さを増やし、最終的に7まで対応すれば全てマッチしました。

^(<(<(<(<(<(<(<>)*>)*>)*>)*>)*>)*>)*$

後はどこまで削れるか、ですが適当に試してみたところ

^(<(<(<(<(<(<<>>)*>)*>)*>)*>)*>)*$

でいけました。

意外と簡単でしたね。

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

それでは、また。