2015-07-24

Regex Golf をやってみた 14 〜Triples〜

Regex Golf 14回目(13回目はこちら

だんだん続けるのが辛くなってきましたが始めてしまった以上、最後までやりたいと思います。
正規表現によるパズルゲーム? Regex Golf 10問目 "Triples" です。
3の倍数を検索です。


前回は状態遷移を考えて正規表現を組み立てて、正解にはたどり着きましたが、3で割り切れない数字の出現回数をつかった方法はできないまま終わっていました。

以下、ネタバレ

さて、3で割り切れない数字の出現回数を数える方法についてですが、肯定先読みを使って数えます。

まず、3で割ると1余る数字の出現回数ですが
(?=((.*?[147]){3})*((.*?[147]|){2}))
で数えることが出来ます。
.*?
はマッチする最小の文字列で検索します。Lazy指定をしないと正しく回数を数えられません。

この正規表現はどのような文字列でも必ずマッチします。
出現回数は \3 と \4 から次のように判断できます。
  • \3 (および \4) が空なら出現回数は3の倍数回
  • \3 に文字列が入っていて \4 が空なら出現回数は3の倍数+1回
  • (\3 および) \4 に文字列が入っているなら出現回数は3の倍数+2回
続いて、 3で割ると2余る数字の出現回数ですが147と同様に
(?=((.*?[258]){3})*((.*?[258]|){2}))
で数えます。
147 の肯定先読みの後にこれを書くため出現回数は \3 と \4 ではなく \7 と \8 から次のように判断できます。
  • \7 (および \8) が空なら出現回数は3の倍数回
  • \7 に文字列が入っていて \8 が空なら出現回数は3の倍数+1回
  • (\7 および) \8 に文字列が入っているなら出現回数は3の倍数+2回
さらに、検索対象の文字列全体にマッチする検索文字列 ^.*$ をつなげて
(?=((.*?[147]){3})*((.*?[147]|){2}))(?=((.*?[258]){3})*((.*?[258]|){2}))^.*$
 とします。これでどのような文字列でもマッチし、147 と 258 の出現回数を判断できる状態になりました。

この検索文字列の末尾に、3の倍数でない場合には文字列が追加されるようにすれば3の倍数にだけマッチするようになるはずです。

さて、3の倍数になるための条件は 147 と 258 の出現回数を3で割った余りが同じであることなので、
  • \3 および \7 が空
  • \3 および \7 は文字列が入っているけど \4 \8 は空
  • \4 および \8 に文字列が入っている

の 3 パターンであればOKです。
それぞれ、条件をみたす場合に空になる文字列は

  • \3\7
  • (?!\3|\7)\4\8
  • (?!\4|\8)

となります。

(?!\3|\7)

は \3 および \7 の両方に文字列が設定されていればマッチする文字列が存在しないため、後続の条件が活きてきます。
どちらかが空白の場合は空白の側がマッチしてしまうので否定先読みに引っかかります。

という事で、全体としては

(?=((.*?[147]){3})*((.*?[147]|){2}))(?=((.*?[258]){3})*((.*?[258]|){2}))^.*$(\3\7|(?!\3|\7)\4\8|(?!\4|\8))
になります。


前回の503ポイントから21ポイント増です!!
なんかこれ以上は無理っぽいので "Triples" はこれでおしまい。

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

それでは、また。

2 件のコメント:

まさいとう さんのコメント...

正規表現で面白い事やるもんですね。正規表現系エンジンってパフォーマンスも良くなって、今結構色々なプログラムで使われてますが、自分は複雑な正規表現とかを書くと「テストケースが全部把握できない」「思わぬ結果が出る事が想定できない」という理由で文字列操作系処理は未だに文字列検索などを使って自作する事が多いです(オールドタイプなんでしょうね( ´ー`))

さぼのば さんのコメント...

まさいとう さん、コメントありがとうございます。
Regex Golf は遊びだからこれでいいけど、まさいとう さんと同じ理由、仕事で作るプログラムは検証が容易であることの優先度がかなり高いのでほぼ使わないですね。^^;