この記事は FizzBuzz Advent Calendar 2017 の16日目の記事です。

KotlinでFizzBuzz / 逆FizzBuzz問題を解いてみたいと思います。

#KotlinでFizzBuzz

まずはルールのおさらいです

自然数$i$は $1 \leqq i \leqq 100$を満たすものとする。
このとき、自然数列 $a_n=\{1, 2, 3, 4, ..., 100\}$ に対し、
・$a_i$が3の倍数であるときは"Fizz"を、
・$a_i$が5の倍数であるときは"Buzz"を、
・$a_i$が3の倍数で、かつ5の倍数でもあるときは"FizzBuzz"を、
・それ以外の場合は$a_i$の値を出力する
を満たすようなプログラムを作成せよ。

それではまずは普通に書いてみます。

FizzBuzz.kt

fun main(args: Array<String>){
  for(i in 1..100){
    if(i % 15 == 0){
      println("FizzBuzz")
    }else if(i % 3 == 0){
      println("Fizz")
    }else if(i % 5 == 0){
      println("Buzz")
    }else{
      println(i)
    }
  }
}

典型的なforループとif文によるコードですね。

よく「FizzBuzzを3分以内に書けないエンジニアは失格」、とか言われますが
個人的にはこのレベルのコードを3分以内で書かれても「だから？」という感じがします。
（納期に間に合わせることだけを目的としたクソコード量産機を望むのであれば話は別ですが）

それよりも、ある程度十分な時間を与えた上でいかに美しいコードを書けるかが重要ではないかと思います。
3分とは言わずとも、10分くらいあっても書けないエンジニアであれば、多分3時間あっても書けないだろうと思います。
~~（「美しい」の定義でまた論争が起きそうな気もしますが、フィーリングでうまいこと解釈して下さい。）~~

次にCodeGolfで出ている現状の最短（と思われる）コードがこちらです。

Shortest.kt

fun main(a:Array<String>){(1..100).map{i->println(mapOf(0 to i,i%3 to "Fizz",i%5 to "Buzz",i%15 to "FizzBuzz")[0])}}

極力変数の文字数を少なくしたり、不要な空白・改行を取り除いているのはもちろんなのですが、
1から100の繰り返しを(1..100).map{...}というようにStreamを用いて記載することでかなり文字数が抑えられています。

もっと短く書けるのかもしれませんが、現状私もこれより短く書けるコードは知りません。
もし何かご存知でしたらぜひ教えてください。

#Kotlinで逆FizzBuzz

さて、今回の本題はこちらです。Kotlinで逆FizzBuzzを書いてみたいと思います。

ここで逆FizzBuzzの定義のおさらいをしようと思います。

"Fizz","Buzz","FizzBuzz"の3つの文字列のいずれかのみからなるリストLが与えられた時
FizzBuzz操作を行うとそのリストLと同じような出力を行う自然数列$a_n$のうち、最も要素数が少ないものを$A_n$とする。
（ただしここでは$a_i$が3の倍数でも5の倍数でもない場合は何も出力しないこととする。）

このような$A_n$を出力するプログラムを作成せよ。
（ただし、$A_n$の候補が複数存在する場合は、その総和が最も小さいものを$A_n$とする。）

少し具体例を交えてみると、例として以下のようなリストが与えられたとします。

val list = listOf("Fizz", "Buzz")

このとき、ある数列$a_n$に対してFizzBuzz操作を行うと"Fizz", "Buzz"の順で出力されるような数列$a_n$は複数あって、
例えば$a_n = \{3,4,5\}$や、$a_n = \{9, 10\}$が考えられます。

このうち最も要素数が少ないものは$a_n = \{9, 10\}$ですので、今回はそれを出力することができればOKです。

##まずは書いてみる

実はKotlinで逆FizzBuzzを書いたことはありません。
最適化はのちほど行うとして、まずは書いてみます。

InvFizzBuzz.kt

fun main(a: Array<String>) {
    inverseFizzBuzz(arrayOf("Fizz"))
    inverseFizzBuzz(arrayOf("Buzz"))
    inverseFizzBuzz(arrayOf("Fizz", "Fizz"))
    inverseFizzBuzz(arrayOf("Buzz", "Fizz"))
    inverseFizzBuzz(arrayOf("Fizz", "Buzz", "Fizz"))
    inverseFizzBuzz(arrayOf("FizzBuzz"))
    inverseFizzBuzz(arrayOf("FizzBuzz", "Fizz", "Buzz"))
    inverseFizzBuzz(arrayOf("FizzBuzz", "Buzz"))
}

fun inverseFizzBuzz(input: Array<String>) {
    val list = (1..15).map { i -> inverse(input, i) }.filter { i -> i != null }
    if (list.count() == 0) {
        println(input, emptyArray())
        return
    }
    val range = list.sortedBy { i -> i!!.second - i.first }.first()
    println(input, (range!!.first until range.second).toList().toTypedArray())
}

fun inverse(input: Array<String>, start: Int): Pair<Int, Int>? {
    var i = start
    for (element in input) {
        while (i % 3 != 0 && i % 5 != 0) i++
        if (element != if (i % 15 == 0) "FizzBuzz" else if (i % 3 == 0) "Fizz" else if (i % 5 == 0) "Buzz" else "") return null
        i++
    }
    return Pair(start, i)
}

fun println(input: Array<String>, output: Array<Int>){
    println(input.toList().toString() + " -> " + output.toList().toString())
}

操作の実体はinverseFizzbuzz()です。main関数内で色々と入力を作ってみました。

ちなみに結果はこんな感じです。

[Fizz] -> [3]
[Buzz] -> [5]
[Fizz, Fizz] -> [6, 7, 8, 9]
[Buzz, Fizz] -> [5, 6]
[Fizz, Buzz, Fizz] -> [3, 4, 5, 6]
[FizzBuzz] -> [15]
[FizzBuzz, Fizz, Buzz] -> [15, 16, 17, 18, 19, 20]
[FizzBuzz, Buzz] -> []

うん、少なくとも今回のケースは全て正しく通ってそうです。

##説明

おそらく逆FizzBuzz問題の元ネタである逆FizzBuzz問題 (Inverse FizzBuzz)より、

Shipper: いや、力ずくって言っても！入力の文字列に対して数列のパターンは無限に考えられるとすればどうしたらいいんですか。

Google: では最初の100個の数だけを対象にしましょう。1から100までです。さっきのように少しずつ行きましょうか。1から100までで考えられる数列の組み合わせはどうなりますか？

Shipper氏の言うとおり、解自体のパターンは無限通り考えられうるのですが、
今回はその中でも最短かつ最小のものだけを出力、ということにしています。

Fizzは3の倍数、Buzzは5の倍数、FizzBuzzは15の倍数の時に出力されるので、
それぞれの最小公倍数である15を周期として出力が反復されることがわかります。

すなわち、「KotlinでFizzBuzz」の項目で作成した数列$a_n$の各要素に対しFizzBuzz変換を行ったリストをBとして、
先頭から15要素ごとに分割したBの部分リスト$B_k(k=0,1,2,...)$を考えると、

$B_1$ = [1, 2, "Fizz", 4, "Buzz", "Fizz", 7, 8, "Fizz", "Buzz", 11, "Fizz", 13, 14, "FizzBuzz"]
$B_2$ = [16, 17, "Fizz", 19, "Buzz", "Fizz", 22, 23, "Fizz", "Buzz", 26, "Fizz", 28, 29, "FizzBuzz"]
$B_3$ = [31, 32, "Fizz", 34, "Buzz", "Fizz", 37, 38, "Fizz", "Buzz", 41, "Fizz", 43, 44, "FizzBuzz"]

というように、確かに周期15で繰り返していることが目で見てわかります。

ですので、最初の繰り返し単位である1から15までの整数の中で解探索を行い、
その中で最小かつ最短であるものをStreamにより抽出して出力すればよいことがわかります。
逆に、解が見つからなかった場合は、どんなに先まで探索を続けても解は存在しないはずです。

他によく使われる手法としてはテーブルを作成しておいたり、正規表現を使ったりするものがあるようです。

##ちなみに
Fizz, Buzz, FizzBuzzの繰り返し周期をそれぞれ考えると

Buzzの周期5はFizzの周期3より大きいため、Buzzが連続するケースは存在しない
FizzBuzzの周期15はBuzzの周期5より大きいため、FizzBuzzが連続するケースは存在しない
Fizz-Fizzの周期は最短でも3+3=6で、これはBuzzの周期5より大きいため、Fizzが3つ以上連続するケースは存在しない
FizzBuzzを1つ以上含む場合は、以下のように考えれば良い
- 1つでもFizzBuzz-Buzzを含むようなものは存在しない（数学的帰納法で証明可能）
- 全てが(n個の)FizzBuzz-Fizzのみから構成されている場合は各FizzBuzzの直後でn+1個リストを分割する
  - n $ = $ 1の場合はn+1個のリストそれぞれに対して解探索すればよい
  - n $ \geqq $ 2の場合は以下の2条件を満たしていればよい
    - 両端以外のn-1個のリストが全て[Fizz, Buzz, Fizz, Fizz, Buzz, Fizz, FizzBuzz]であること
    - 両端の2個のリストのそれぞれに対して解探索を行い、それぞれ解が存在すること

ということを考えると、テストケースは以下の22通りを用意すればよいことがわかります。

[Fizz]
[Buzz]
[FizzBuzz]
[Fizz, Fizz]
[Fizz, Buzz]
[Buzz, Fizz]
[Fizz, FizzBuzz]
[FizzBuzz, Fizz]
[Fizz, Fizz, Buzz]
[Fizz, Buzz, Fizz]
[Buzz, Fizz, Fizz]
[Buzz, Fizz, FizzBuzz]
[Fizz, Fizz, Buzz, Fizz]
[Fizz, Buzz, Fizz, Fizz]
[Buzz, Fizz, Fizz, Buzz]
[Fizz, Buzz, Fizz, FizzBuzz]
[Fizz, Buzz, Fizz, Fizz, Buzz]
[Buzz, Fizz, Fizz, Buzz, Fizz]
[Fizz, Fizz, Buzz, Fizz, FizzBuzz]
[Fizz, Buzz, Fizz, Fizz, Buzz, Fizz]
[Buzz, Fizz, Fizz, Buzz, Fizz, FizzBuzz]
[Fizz, Buzz, Fizz, Fizz, Buzz, Fizz, FizzBuzz]

ちなみに実行結果は

[Fizz] -> [3]
[Buzz] -> [5]
[FizzBuzz] -> [15]
[Fizz, Fizz] -> [6, 7, 8, 9]
[Fizz, Buzz] -> [9, 10]
[Buzz, Fizz] -> [5, 6]
[Fizz, FizzBuzz] -> [12, 13, 14, 15]
[FizzBuzz, Fizz] -> [15, 16, 17, 18]
[Fizz, Fizz, Buzz] -> [6, 7, 8, 9, 10]
[Fizz, Buzz, Fizz] -> [3, 4, 5, 6]
[Buzz, Fizz, Fizz] -> [5, 6, 7, 8, 9]
[Buzz, Fizz, FizzBuzz] -> [10, 11, 12, 13, 14, 15]
[Fizz, Fizz, Buzz, Fizz] -> [6, 7, 8, 9, 10, 11, 12]
[Fizz, Buzz, Fizz, Fizz] -> [3, 4, 5, 6, 7, 8, 9]
[Buzz, Fizz, Fizz, Buzz] -> [5, 6, 7, 8, 9, 10]
[Fizz, Buzz, Fizz, FizzBuzz] -> [9, 10, 11, 12, 13, 14, 15]
[Fizz, Buzz, Fizz, Fizz, Buzz] -> [3, 4, 5, 6, 7, 8, 9, 10]
[Buzz, Fizz, Fizz, Buzz, Fizz] -> [5, 6, 7, 8, 9, 10, 11, 12]
[Fizz, Fizz, Buzz, Fizz, FizzBuzz] -> [6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[Fizz, Buzz, Fizz, Fizz, Buzz, Fizz] -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[Buzz, Fizz, Fizz, Buzz, Fizz, FizzBuzz] -> [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[Fizz, Buzz, Fizz, Fizz, Buzz, Fizz, FizzBuzz] -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

でした。

#まとめ
時間を掛ければとりあえず書けますが、Googleの採用面接でいきなり出されて、
対話しながらとはいえその場である程度の回答をつくるのはやっぱり難しいなと思いました。

みなさんもぜひ試してみて下さい。