一時期はやっていた逆FizzBuzzをいまさら解いてみました。数年前初めて見たときは難しそうと思ったのですが、今回やってみたらかなりスラスラと解けて驚きました。
問題文
ある連続した自然数列のうち3の倍数をFizz、5の倍数をBuzz、15の倍数をFizzBuzzと変換し、変換されなかった数を取り除いたリストをFizzBuzz列とする。FizzBuzz列が与えられたとき、与えられた列に変換されるような整数列のうち、最短かつ先頭の要素が最小の自然数列を出力せよ。そのような自然数列が存在しない場合はnullを出力せよ。
入力と出力の例
入力 | 出力 |
---|---|
Fizz | 3 |
Buzz | 5 |
Fizz Buzz | 9 10 |
FizzBuzz | 15 |
FizzBuzz Buzz | null |
解法
(以下ではFizz、Buzz、FizzBuzzをそれぞれF、B、FBと記します)
15で割ったときの余りが同じ数字は同じFizzBuzz文字に変換されます。つまりFizzBuzz列は周期性があります。
1から15までをFizzBuzz列に変換すると F,B,F,F,B,F,FBとなります。16以降はこれの繰り返しとなっています。ということは、与えられたFizzBuzz列が長さ7以上の場合、周期性を利用すると先頭から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個です。
- F
- B
- F,B
- F,F(,B,F,FB,…)
- F,FB…
- B,F
- F,B,F
- B,F,F(,B,F,FB,…)
- B,F,FB…
- F,B,F,F(,B,F,FB,…)
- F,B,F,FB…
カッコがあるパターンは、解がある場合その組み合わせしか存在できないので、周期性からすぐに解が求まります。カッコがなくFBが出てこないパターンは解の可能性のある数列がいくつかあるので、そのうち最短かつ先頭が最小のものを手動で探さねばなりません。
F | 3 |
B | 5 |
F,B | 9,10 |
F,F(,B,F,FB,…) | 6,7,8,9(,10,11,…) |
F,FB… | 12,13,14,15,… |
B,F | 5,6 |
F,B,F | 3,4,5,6 |
B,F,F(,B,F,FB,…) | 5,6,7,8,9(,10,11,…) |
B,F,FB… | 10,11,12,13,14,15,… |
F,B,F,F(,B,F,FB,…) | 3,4,5,6,7,8,9(,10,11,…) |
F,B,F,FB… | 9,10,11,12,13,14,15,… |
これで、解が存在する場合の全パターンを列挙できました。
プログラム
もはやプログラミングというより数学の問題という感じですが、一応プログラムを組んでおきます。
const solve = arr => { arr = arr.map(s => s === 'FizzBuzz' ? 'FB' : s === 'Fizz' ? 'F' : 'B'); // 処理を簡単にするために変換した const index = arr.indexOf('FB'); if (index >= 7) return null; if (arr.length >= 7 && index === -1) return null; if (index !== -1) { for (let i = 0; i + index + 1 < arr.length; i++) { if (arr[i + index + 1] !== 'F B F F B F FB'.split(' ')[i % 7]) return null; } const res = { '': [], 'F': [12, 13, 14], 'B F': [10, 11, 12, 13, 14], 'F B F': [9, 10, 11, 12, 13, 14], 'F F B F': [6, 7, 8, 9, 10, 11, 12, 13, 14], 'B F F B F': [5, 6, 7, 8, 9, 10, 11, 12, 13, 14], 'F B F F B F': [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] }[arr.slice(0, index).join(' ')].concat(15); for (let i = 16, _i = ((0 | arr.slice(index + 1).length / 7) + 1) * 15; i <= _i; i++) { res.push(i); } return res.concat({ '': [], 'F': [1, 2, 3], 'F B': [1, 2, 3, 4, 5], 'F B F': [1, 2, 3, 4, 5, 6], 'F B F F': [1, 2, 3, 4, 5, 6, 7, 8, 9], 'F B F F B': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 'F B F F B F': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] }[arr.slice(arr.lastIndexOf('FB') + 1).join(' ')].map(x => x + ((0 | arr.slice(index + 1).length / 7) + 1) * 15)); } if (arr.length === 1){ return [arr[0] === 'F' ? 3 : 5]; } if (arr.length === 2) { if (arr[0] === 'F' && arr[1] === 'B') return [9, 10]; if (arr[0] === 'B' && arr[1] === 'F') return [5, 6]; if (arr[0] === 'F' && arr[1] === 'F') return [6, 7, 8, 9]; return null; } if (arr.length === 3) { if (arr.join(' ') === 'F B F') return [3, 4, 5, 6]; if (arr.join(' ') === 'B F F') return [5, 6, 7, 8, 9]; if (arr.join(' ') === 'F F B') return [6, 7, 8, 9, 10]; return null; } if (arr.length === 4) { if (arr.join(' ') === 'F B F F') return [3, 4, 5, 6, 7, 8, 9]; if (arr.join(' ') === 'B F F B') return [5, 6, 7, 8, 9, 10]; if (arr.join(' ') === 'F F B F') return [6, 7, 8, 9, 10, 11, 12]; return null; } if (arr.length === 5) { if (arr.join(' ') === 'F B F F B') return [3, 4, 5, 6, 7, 8, 9, 10]; if (arr.join(' ') === 'B F F B F') return [5, 6, 7, 8, 9, 10, 11, 12]; return null; } if (arr.length === 6) { if (arr.join(' ') === 'F B F F B F') return [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]; return null; } };
感想
FizzBuzzといえば簡単なプログラムの代名詞ですが、逆FizzBuzzはすこし頭を使いました。面白かったです。