平々毎々（アーカイブ）

はてなダイアリーのアーカイブです。

逆FizzBuzz問題 (Inverse FizzBuzz)

General

just another scala quantを日本語にしました。

ちなみに、私の解はこちらに。

最初の解答
はてブに書いた解答方針、Inverse Fizzbuzz (FizzBuzzの逆関数) - Qiita - 与えられた範囲内のすべての解を数え上げてます。
もっと簡潔な解答
逆FizzBuzz問題 解きなおし - Qiita

それでは、問題の日本語訳をどうぞ。

逆Fizzbuzz問題

2012年ではなく、2016年のお話。

世の中は大して変わっていない。

OOPと書き換え可能なオブジェクトによって何度もひどい目にあった後、世界はやっとのことでJohn Hughesの考察が正しかったことに気づき、関数型プログラミングに移行した。GoogleはTypesafe社を買収し、ScalaがAndroid上でネイティブに動作するようになっている。Googleに負けず劣らず、AppleはHaskellで書かれていないiOSアプリを禁止している。Windowsの世界はすべてF#で書かれるようになっている。

それらを除けば、世の中は大して変わっていない。

The canonicalのShipperさんはペンシルバニア大学を卒業し、某G社のホワイトボード面接を初めて受けるところだ。


Google: ところでShipperさん、FizzBuzzはご存知ですか？
Shipper: 何の冗談ですか？もう2016年ですよ、2012年じゃないんですから。FizzBuzzなんて誰だって知ってます。僕らのおばあちゃんでさえ知っててもおかしくない。
Google: わかりました、ではFizzBuzzを少し改変した問題をやってみましょう。

問題: 左のリストを右のリストに写像するにはどうしますか？
http://www.jasq.org/uploads/1/0/5/6/10564637/1086192_orig.png

Shipper: ええと、左のリストの中身を右のリストの中身に対応付けるってことですね。
Google: ええ。
Shipper: しかし、すべての要素ではなく、3か5の倍数だけなんですね。
Google: そうです。
Shipper: Partial Function(部分関数)でいけそうだな。
Google: Partial Functionとは何ですか？
Shipper: まずはじめに、条件を満たす述語関数はこうなります。

scala> val isFizzBuzz = ((x:Int) => x%3 ==0 || x%5 ==0)

Google: いいですね。それではこれをどう利用するのですか？
Shipper: 次に、写像を定義する別のラムダを作ります。

scala> val toFizzBuzz = ((x:Int) => (x%3,x%5) match {     
               case (0,0) =>   "fizzbuzz"
               case (0,_) => "fizz" 
               case _ => "buzz"     
          })

Google: 結構。あなたはパターンマッチの使い方をご存知ということで……
Shipper: あのう、今年は2016年で2012年じゃないと言いましたよね！誰だって婆だって……
Google: はい、はい、わかりました。それではPartial Functionを説明していただけますか？
Shipper: Partial Functionは述語関数と写像をまとめただけのものです。そして、

scala> val fizzbuzz = new PartialFunction[Int,String] {     
                  def isDefinedAt(x:Int) = isFizzBuzz(x)
                 def apply(x:Int) = toFizzBuzz(x)   
            }

こうするだけで、このPartial Functionが定義されている範囲のみの結果を集めることができます。

scala> (1 to 100).collect( fizzbuzz )
res1: scala.collection.immutable.IndexedSeq[String] = Vector(fizz, buzz, fizz,fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz,
buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizz,buzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz)

Google: ブラボー！きれいに書けましたね。
Shipper: でしょう？！
Google: ただちょっと気になるんですが、Shipperさん、なぜPartial Functionが必要なんですか？もっと単純にできないものでしょうか？
Shipper: つまり、mapとfilterとか？
Google: そうですね、やってみてもらえますか？
Shipper: そうであれば、まず述語関数でfilterをかけて、写像を適用することになります。

scala> (1 to 100).filter( isFizzBuzz ).map( toFizzBuzz )
res2: scala.collection.immutable.IndexedSeq[String] = Vector(fizz, buzz, fizz,fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz,
buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizz,buzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz)

Google: いいですね！でもまだ他にもやり方がありますね。
Shipper: うーん……
Google: 集合を思い出してください。数学ではどうやって集合を定義しますか？
Shipper: ああ、リスト内包ってことですか？
Google: そのとおり！
Shipper:

scala> for( x<- (1 to 100); if( isFizzBuzz(x))) yield toFizzBuzz(x)
res3: scala.collection.immutable.IndexedSeq[String] = Vector(fizz, buzz, fizz,fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz,
buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizz,buzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz)

Google: 素晴らしい！あなたはFizzBuzzのやり方を少なくとも3種類わかっていることになります。
Shipper: これで採用決定ですか？
Google: あわてないで、Shipperさん。まだ気が早いです！ここはGoogleなんですから。面接に来てFizzBuzzを解いた人全員を雇うわけにはいきませんよ。もう2016年なんですから、誰でも雇うことになってしまいます。
Shipper: では……
Google: そこで、ここGoogleでは新しいテストを考えました。逆FizzBuzzという名前です。
Shipper: 逆FizzBuzz！
Google: いいですね！聞いたことがないという様子です！
Shipper: はい、まったく！
Google: これはですね、私たちが先週考えたばかりなんです。でもそこまで難しくはないですよ。数学における逆とは何か分かりますか？
Shipper: 数学における逆……
Google: そうです。たとえば、5に何を足すと0になりますか？
Shipper: -5です。
Google: つまり-5とは？
Shipper: ああ！おっしゃりたいことが分かりました。マイナス5 は加法に関する5の逆元です。
Google: では乗法に関する5の逆元は？
Shipper: えーと、0.2です。0.2を5倍すれば1になります。
Google: 正解です！1/2の逆正弦は？
Shipper: 30度です。sin(30°) = 0.5 なので。
Google: 結構。1/2の逆対数は？
Shipper: eの平方根です。
Google: よくできました！では逆FizzBuzzに戻りましょう。
Shipper: はい。逆FizzBuzzはどのように定義するのですか？
Google: 単純ですよ。あるリストが与えられたときに、FizzBuzzを実行するとそのリストを出力するような最短の連続数列を返すのです。
Shipper : え？！
Google: 逆FizzBuzz問題。あるリストが与えられたときに、FizzBuzzを実行するとそのリストを出力するような最短の連続数列を求めよ。
Shipper: 理解が追いつきません。
Google: では単純な例から始めましょう。{ fizz }を出力する最短の連続数列は？
Shipper: えーと、{ 1,2,3 }です。
Google: Shipperさんしっかりしてください。もっといい答えがあるでしょう。
Shipper: あ、{ 3 }でいいのか。
Google: { buzz }を出力する最短の連続数列は？
Shipper: { 5 }です。
Google: { fizz, buzz }を出力する最短の連続数列は？
Shipper: { 3, 4, 5 }。
Google: 不正解！
Shipper: いや、ちょっと待ってください……{ 9,10 }でした。
Google: 素晴らしい！ { buzz, fizz }を出力する最短の連続数列は？
Shipper: { 5,6 }。
Google: { fizz, buzz, fizz }を出力する最短の連続数列は？
Shipper: { 3, 4, 5, 6 }。
Google: { buzz, fizz, buzz }を出力する最短の連続数列は？
Shipper: えーと……これはリストが正しくないような……
Google: 正解です。プログラムを書くときはこれを検出できるようにしてください。もう少し続けましょう。{ fizz, fizz }を出力するのは？
Shipper: { 6,7,8,9 }。
Google: { fizz, fizz, buzz }なら？
Shipper: { 6,7,8,9,10}。
Google: はい。ここまでの例をまとめたのがこれです。あなたのラムダがするべきことはこれになります。

http://www.jasq.org/uploads/1/0/5/6/10564637/5043068.png

Google: さあ、これで逆FizzBuzzのラムダを書けますよね！？
Shipper: でも、この問題の解は一意ではないですよね。{fizz}は{ 3 }に対応付けられるだけじゃなくて、{6}や{9}にも対応しますし……
Google: そうですね。ならば、解の一意性は問題にしません。最も短い連続数であればいいことにします。
Shipper: すみませんが問題をもう一度教えてもらえますか？
Google: あるリストが与えられたときに、FizzBuzzを実行するとそのリストを出力するような最短の連続数列を求めよ。
Shipper: 正直に言ってぜんぜんわかりません。
Google: そうですか。問題の解法が分からないときには何をしますか？
Shipper: 全部試してみます。力ずくってやつです。
Google: それでいいじゃないですか！
Shipper: いや、力ずくって言っても！入力の文字列に対して数列のパターンは無限に考えられるとすればどうしたらいいんですか。
Google: では最初の100個の数だけを対象にしましょう。1から100までです。さっきのように少しずつ行きましょうか。1から100までで考えられる数列の組み合わせはどうなりますか？
Shipper: ええと、FizzBuzzに1を与えて、次は{1,2}で、その次は{1,2,3}で、その次は{1,2,3,4}で……というようにして{1,2,....100}までが考えられます。
Google: そうすると100通りですね、Shipperさん。でもFizzBuzzを2から始めてもいいですよね。次は{2,3}、その次は{2,3,4}、その次は{2,3,4,5}、そして{2,....100}まで。
Google: さて、これは何通りありますか？
Shipper: 99通りです。わかりました。そうすると、100 + 99 + 98 + ...1 = (101)*100/2 = 5050通りです。
Google: 5000個強。たいした数ではないですよね。
Shipper: そうですね。しかし、重複は捨てますし、最短の数列への写像だけを持っておけばよいわけです。
Google: そうです。そうすれば、最終的なリストは5050より少なくなりますよね。
Shipper: わかりました。なんだかあっさり解けそうな気がしてきました。

scala> val all = (1 to 100).map(x=> (x to 100).map( y=> (x,y) )).flatten
all: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,1), (1,2),(1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (1,10), (1,11), (1,12), (1,13),
 (1,14), (1,15), (1,16), (1,17), (1,18), (1,19), (1,20), (1,21), (1,22), (1,23), (1,24), (1,25), (1,26), (1,27), (1,28), (1,29), (1,30), (1,31), (1,32), (1,33), (1,34), (1,35), (1,36), (1,37), (1,38), (1,39), (1,40), (1,41), (1,42), (1,43),......(2,2),(2,3),......
scala> all.size
res22: Int = 5050

Google: これで、ひとまず5050通りの範囲が得られたことになりますね。
Shipper: はい。ではこの5050通りの範囲に対してFizzBuzzを適用してみます。

scala> val results = all.map( x=> (x._1 to x._2).collect( fizzbuzz ))

Shipper: そして、入力と出力を並べてみます。

scala> val io = all.zip( results )

Shipper: 次に出力でグルーピングします。こうすれば、文字列のリストから数列のリストへの写像が得られるはずです。

scala> val inverses = io.groupBy( x=> x._2)

Google: このあたりで、正しい道筋を進んでいるかどうか確認しませんか。写像のキーの数を数えてみてください。5050より小さくなっているはずですが。

scala> inverses.keys.size
res36: Int = 302

Google: いいですね！ユニークなキーは302個だけ、5050ではありません。それでは、キーに対応する最も短い値はどうやって探しましょうか？
Shipper: まず"fizz"でテストしてみます。

scala> inverses(Vector("fizz"))
res28: scala.collection.immutable.IndexedSeq[((Int, Int), scala.collection.immutable.IndexedSeq[String])] = Vector(((1,3),Vector(fizz)), ((1,4),Vector(fizz)), ((2,3),Vector(fizz)), ((2,4),Vector(fizz)), ((3,3),Vector(fizz)), ((3,4),Vector(fizz)), ((6,6),Vector(fizz)), ((6,7),Vector(fizz)), ((6,8),Vector(fizz)), ((7,9),Vector(fizz)), ((8,9),Vector(fizz)), ((9,9),Vector(fizz)), ((11,12),Vector(fizz)), ((11,13),Vector(fizz)), ((11,14),Vector(fizz)), ((12,12),Vector(fizz)), ((12,13),Vector(fizz)), ((12,14),Vector(fizz)), ((16,18),Vector(fizz)), ((16,19),Vector(fizz)), ((17,18),Vector(fizz)), ((17,19),Vector(fizz)), ((18,18),Vector(fizz)), ((18,19),Vector(fizz)), ((21,21),Vector(fizz)), ((21,22),Vector(fizz)), ((21,23),Vector(fizz)), ((22,24),Vector(fizz)), ((23,24),Vector(fizz)), ((24,24),V...

Shipper: 確かに、キーに対応するすべての範囲が求められています。必要なのは最短の範囲だけです。minByを試してみます。

scala> inverses(Vector("fizz")).minBy(x=>x._1._2 - x._1._1)
res33: ((Int, Int), scala.collection.immutable.IndexedSeq[String]) = ((3,3),Vector(fizz))

Shipper: よし、できたみたいだ！

scala> val answer = inverses.keys.map( k=> (k,inverses(k).minBy(x => x._1._2 - x._1._1)._1)).toMap
answer: scala.collection.immutable.Map[scala.collection.immutable.IndexedSeq[String],(Int, Int)] = Map(Vector(fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz) -> (3,33), Vector(buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz) -> (10,93), Vector(fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz, fizz, buzz, fizz, fizz, buzz, fizz, fizzbuzz) -> (15,75), Vector(fizz, buzz, fizz, fizzbuzz) -> (9,15), Vector(fizzbuzz, fizz, buzz, fizz, fizz, b...

Google: 7つの例の答えを試してみますね。

scala> answer(Vector("fizz"))
(3,3)
scala> answer(Vector("buzz"))
(5,5)
scala> answer(Vector("fizz","fizz","buzz"))
(6,10)
scala> answer(Vector("fizz","buzz"))
(9,10)
scala> answer(Vector("buzz","fizz"))
(5,6)
scala> answer(Vector("fizz","buzz","fizz"))
(3,6)
scala> answer(Vector("fizz","fizz"))
(6,9)

Shipper: できた！
Google: 確かに。できましたね！
Shipper: これで採用決定ですか？
Google: うーん、今回は力ずくで解きましたよね。そうですね、力ずくでない方法を思いついたら採用としましょう。

Shipper: あーでもない……こーでもない……


追伸：実際はそんなに難しくないですよ。:)


では、まとめます。

問題
逆FizzBuzz問題。あるリストが与えられたときに、FizzBuzzを実行するとそのリストを出力するような最短の連続数列を求めよ。
力ずくの解
val all = (1 to 100).map(x=> (x to 100).map( y=> (x,y) )).flatten
val results = all.map( x=> (x._1 to x._2).collect( fizzbuzz ))
val io = all.zip( results )
val inverses = io.groupBy( x=> x._2) 
val answer = inverses.keys.map( k=> (k,inverses(k).minBy(x => x._1._2 - x._1._1)._1)).toMap