黄昏より暗きもの、血の流れより赤きもの

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

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

逆FizzBuzz問題とその解き方

今日はFizzBuzz問題(Inverse FizzBuzz Ploblerm)の逆とも言える「逆FizzBuzz問題」について何とか解いたので、その解き方を紹介したい。まずは以下の問題文を見て欲しい。尚問題文は「逆FizzBuzz問題 (Inverse FizzBuzz) - 猫とC#について書くmatarilloの雑記」の文献を基に構成した。


問題


FizzBuzz問題とは、1からNまでの自然数を数えていくときに、3の倍数ならば数字の代わりに「Fizz」、5の倍数ならば数字の代わりに「Fuzz」、15の倍数ならば数字の代わりに「FizzBuzz」と答えるものであった。FizzBuzz問題を解く上で整数1〜15までの間には、以下の表の順に文字列が登場する。(以下の表では「Fizz」はF、「Buzz」はBで表示している)





今度は逆にFizz又はBuzzと入力したとき、その文字列を表す数字列がどのようなものかを考える。つまりあるリストが与えられたときに、FizzBuzzを実行するとそのリストを出力するような最短の連続数列を求めたい。例えば「Fizz」と入力すると、{3}が返され、「Buzz」と入力すると{5}が返される。このとき、


[1]:以下の文字列を入力したときに返される最短の連続数列を答えよ。連続数列が無い場合は「なし」と答えよ。



(a):{Fizz,Buzz}

(b):{Fizz,Buzz,Fizz}

(c):{Buzz,Fizz,Buzz}


[2]:逆FizzBuzz問題のプログラムを実装せよ。


解答(1)


15以降の場合も同じ周期でFizz,Buzzの並びが続くので、最短の連続数列は自然数1〜15の間にある。問題文の表を見てみると、(a):{Fizz,Buzz}→{3,4,5},(b):{Fizz,Buzz,Fizz}→{3,4,5,6},(c):なし(答)


解答(2)の方針


解答2の方針は、「逆FizzBuzz問題を解く(me agaist the world)」さんの方法を採用する。具体的な手順は、



(a):Fizzを1,Buzzを2,FizzBuzzを3に対応付ける

(b):問題文の表のF,B,FBを左から並べ(a)のように置き換えた数列Aを作成する。例えば問題文の表を置き換えると、1211213...というように数列Aが作成される。同時に1,2,3の位置を表す数字(3,5,6など)も保存していく。

(c):入力したFizz,Buzz文字列を(a)のように置き換えた数列Bを作成する。例えば入力した文字列が{Fizz,Buzz}ならば12と作成される。

(d):数列Aと数列Bを比較し、数列AのX文字目〜Y文字目の間に数列Bが初めて登場するかを調べる。尚Y=X+(数列Bの文字の長さ)-1が成立するのでこれを利用する。

(e):(d)のX,Yに対応する数字f[X],f[Y]を出力。(全部出力したい場合はf[X]〜f[Y]までの連続する自然数*1をループで出力)


以上。上記の手順をPHPにて実装してみた。今回は簡便のため上記のf[X],f[Y]のみを出力するプログラムを作成。尚、問題1の(c)にあった{Buzz,Fizz,Buzz}と入力したような場合などの例外処理は付けていないのでご了承願いたい。XとYの求め方について。PHPのstrpos関数*2を使ってXを求め、strlen*3関数を使って数列Bの長さを求めYを計算していく。


解答(2)のソースコード



検証


試しに問題[1](b)にあった、{Fizz,Buzz,Fizz}を入力したところ無事数列{3,...,6}が表示された。尚121は数列Bを表す。




*1:別な言い方をすると初項f[X],公差1,末項f[Y]の等差数列

*2:strpos関数:文字列内の部分文字列が最初に現れる場所を見つける

*3:strlen関数:文字列の長さを調べる関数