2015-07-02

Regex Golf をやってみた 9 〜素数にリベンジ〜

Regex Golf 9回目(8回目はこちら

正規表現によるパズルゲーム? Regex Golf 7問目 "Prime" ですが、昨日すっきりしない感じで終えたので今日はリベンジです。

以下、ネタバレ

さて、昨日は "x" の素数回繰り返しを検索するのではなく、素数でないものを否定する方向でこんな風にしました。
^(?!((xx){2,}|(xxx){2,}|(x{5}){2,})$)


考え方としては
  • 「素数」の2回以上繰り返しがあればダメ
  •  問題の数が限られているから正解になるまで素数を足していけばOK
という物でした。

今日はもう少し基本に立ち返って考えます。そもそも素数とは Wikipedia によると
素数(そすう、英: prime number)とは、1 と自分自身以外に正の約数を持たない自然数で、1 でない数のことである。
という事ですから、素数でない数は
  • 1 は素数ではない
  • 割ると2以上になる数が存在する数は素数ではない
と言うことになります。
前回は「素数の2回以上繰り返し」つまり「素数で割ると2以上になる」ものを素数ではないと判断しましたが、この「素数」は必要ない事がわかります。

どうなるかと言うと
  • "x" 1 文字は素数ではない
    • ^(?!x$)
  • 割ると2以上になる数が存在する数は素数ではない
    つまり "x" 2 文字以上の 2 回以上繰り返しは "x" 素数個の文字列ではない
    • ^(?!(xx+)\1+$)
合わせると
^(?!(x|(xx+)\2+)$)
となります。


かなりスッキリ!恐らく正解でしょう!!

後は短く出来るか?ですが "x" 1 文字は問題の中にないので削ることが出来ます。
^(?!(xx+)\1+$)


いや〜
ちゃんと出来ると気分爽快ですね!!

ちなみに "x" 2 文字以上の 2 回以上繰り返しは
(xx+){2,}
一瞬と書けそうな気がしましたがそれはつまり
(xx+)(xx+)(|xx+)(|xx+)(|xx+) ...
とこんな感じになり、括弧内の "x" 文字数は括弧ごとに違ってOKになってしまうため今回意図している検索にはなりません。
そもそも文字数も増えてますし…

次回、10回目は 8 問目、 "Four" の予定です!

0 件のコメント: