Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

逆FizzBuzzを解いてみた

一時期はやっていた逆FizzBuzzをいまさら解いてみました。数年前初めて見たときは難しそうと思ったのですが、今回やってみたらかなりスラスラと解けて驚きました。

問題文

ある連続した自然数列のうち3の倍数をFizz、5の倍数をBuzz、15の倍数をFizzBuzzと変換し、変換されなかった数を取り除いたリストをFizzBuzz列とする。FizzBuzz列が与えられたとき、与えられた列に変換されるような整数列のうち、最短かつ先頭の要素が最小の自然数列を出力せよ。そのような自然数列が存在しない場合はnullを出力せよ。

入力と出力の例

入力出力
Fizz3
Buzz5
Fizz Buzz9 10
FizzBuzz15
FizzBuzz Buzznull

解法

(以下では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が出てこないパターンは解の可能性のある数列がいくつかあるので、そのうち最短かつ先頭が最小のものを手動で探さねばなりません。

F3
B5
F,B9,10
F,F(,B,F,FB,…)6,7,8,9(,10,11,…)
F,FB…12,13,14,15,…
B,F5,6
F,B,F3,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はすこし頭を使いました。面白かったです。