限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。2017-02-14逆FizzBuzzを解いてみたJavaScript一時期はやっていた逆FizzBuzzをいまさら解いてみました。数年前初めて見たときは難しそうと思ったのですが、今回やってみたらかなりスラスラと解けて驚きました。問題文ある連続した自然数列のうち3の倍数をFizz、5の倍数をBuzz、15の倍数をFizzBuzzと変換し、変換されなかった数を取り除いたリストをFizzBuzz列とする。FizzBuzz列が与えられたとき、与えられた列に変換されるような整数列のうち、最短かつ先頭の要素が最小の自然数列を出力せよ。そのような自然数列が存在しない場合はnullを出力せよ。null解法(以下ではFizz、Buzz、FizzBuzzをそれぞれF、B、FBと記します)15で割ったときの余りが同じ数字は同じFizzBuzz文字に変換されます。FizzBuzz列は周期性があります。F,B,F,F,B,F,FBとなります。16以降はこれの繰り返しとなっています。いうことは、与えられたFizzBuzz列が長さ7以上の場合、周期性を利用すると先頭から7文字見るだけで出力がわかります。入力「F,B,F,FB,F,B,F,F,B,F,FB」を考えます。この入力が正しい出力を得られるものとすると、必ず「F,B,F,F,B,F,FB」(1〜15をFizzBuzz列に変換したもの)が含まれているはずです。カッコでくくってみると「F,B,F,FB,(F,B,F,F,B,F,FB)」の部分です。カッコの部分は1~15、16~30、31~45、...のいずれかです。先頭の要素が最小となる自然数列を出力したいので、16~30を選びます。ここから逆算的に考えて「F,B,F,FB」部分は「9,10,11,12,13,14,15」となります。以上から「9から30までの数列」が求める自然数列とわかります。入力の長さが7未満FBが出てきたらそれ以降は周期性からすぐに解が求まります。そのためFBを末尾以外に含まないパターンのみを考えればよいとわかります。入力の長さが7未満の場合で、解が存在するパターンは以下の11個です。FBF,BF,F(,B,F,FB,...)F,FB...B,FF,B,FB,F,F(,B,F,FB,...)B,F,FB...F,B,F,F(,B,F,FB,...)F,B,F,FB...カッコがあるパターンは、解がある場合その組み合わせしか存在できないので、周期性からすぐに解が求まります。カッコがなくFBが出てこないパターンは解の可能性のある数列がいくつかあるので、そのうち最短かつ先頭が最小のものを手動で探さねばなりません。9,10,11,12,13,14,15,...これで、解が存在する場合の全パターンを列挙できました。プログラムもはやプログラミングというより数学の問題という感じですが、一応プログラムを組んでおきます。}};感想FizzBuzzといえば簡単なプログラムの代名詞ですが、逆FizzBuzzはすこし頭を使いました。以前、Fisher-Yatesアルゴリズムについての記事を書きました。限界を究めるブログです。までSNSTwitterGitHubHomepageBlog連載リストプライバシーポリシースターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。