正規表現で2のn乗を判定（Regex Golf をやってみた 17 〜Powers〜）

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

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

今回のお題は「正規表現で2のn乗を判定する」です。
素数の判定と同じで "x" の数を数えます。

タイトル横のアドバイスを見ると

In hard mode, you have to recognize any power of two.

とあります。

えっと…
ハードモード？

実は今まで通常モードでやってきたのですが、このゲーム、ハードモードがあるのです。
通常モードでは例に挙がっているものだけを対象とすればいいのですが、ハードモードでは同一ルールで生成された例に挙がっていないパターンにも対応しなければならないのです。
通常モードでは2の10乗まで判定できればよいのですが、ハードモードではこの制限が無い模様。
ということはシンプルな答えがあるという事でしょう。

とはいえ、全然思いつかないのでとりあえず力技で対応してみます。
先頭から末尾までが x, xx, xxxx, xxxxxxxx, 中略 xxxx...(1024回繰り返し) であればよいため、次のように書けます。繰り返し回数が増えたら繰り返し {n} を使うと効率的です。

^(x|xx|xxxx|x{8}|x{16}|x{32}|x{64}|x{128}|x{256}|x{512}|x{1024})$

とりあえずこれで左側は全てマッチ、右側は全てマッチしない正規表現になりました。
右側の x の数は 3, 5, 7, 11, 13, 28, 48, 160, 401, 600, 1025 なので 2〜16 は単純に偶数の判定でよさそうです。また、右側には 64 の倍数は含まれていないため、64〜1024 は 64 の倍数の判定でよさそうです。そこで次のようにしてみました。

^(x|(xx){1,8}|x{32}|(x{64})+)$

検索文字列を大幅に減らすことが出来ました。
でもこの方法では一般化することは難しそうです。

そこで、別の方法を試してみることにしました。
2の0乗を検索

^x$

2の0〜1乗を検索

^(x)\1?$

2の0〜2乗を検索

^((x)\2?)\1?$

2の0〜3乗を検索

^(((x)\3?)\2?)\1?$

この要領で進めていくと、2の0〜10乗を検索する正規表現は

^((((((((((x)\10?)\9?)\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?$

となります。

点数、下がっちゃいましたね。
これは一見単純な繰り返しでよさそうに思えましたが、やはり根本的な解決には向かわないようです。

正解を検索する方法ではどうもうまくいかないので、素数の判定で使った正解を検索するのではなく不正解を検索し否定先読みする方式を次回、考えてみたいと思います。

それでは、また。