読者です 読者をやめる 読者になる 読者になる

北海道苫小牧市出身の壮年PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

逆FizzBuzz(Inverse FizzBuzz)の正規表現書いた(解けてないけど)

perl

ええ、そうなの!? と思ったので深追いしてみた。

FizzBuzzって、オートマトンなので正規表現を使うと楽に出来るはず。

Perl で 逆FizzBuzz

状態遷移図を書いてみるとこう。

ほんとは1〜15まで全て状態を書いて、ε遷移を加えてεの長さも1とした最少の単語を見付けなければならない。

で、これをこのPDFの方法正規表現に書き直してみる。だるかったのでfizzはF、buzzはB、fizzbuzzはZにしておいた。

my $reg_inv_fizzbuz = qr/^(
    (((((F?B)?F)?F)?B)?F)?Z
    (FBFFBFZ)*
    (F|FB|FBF|FBFF|FBFFB|FBFFBF)
    |(((((F?B)?F)?F)?B)?F)?Z
    |((((F?B)?F)?F)?B)?F
    |(((F?B)?F)?F)?B
    |((F?B)?F)?F
    |(F?B)?F
    |F?B
    |F
)$/x;

これでfizz buzz の列について回答が存在するか否かは判定できる。ただ、正規表現に変換してしまった時点で各遷移の重み付けの情報は飛んでしまったので、逆fizzbuzzの解答にはならなかった。

おしまい。


【追記】
正規表現は使ってないけど、一応automata的な解答は作っておいた。もっと簡単にかけると思ったら思ったより面倒。