Inverse Fizzbuzz

05/03/2012

It is 2016, not 2012.

Nothing much has changed.

After a series of embarassing public disasters involving OOP & mutable state, the world has finally realized the wisdom of John Hughes and switched to functional programming. Google has purchased Typesafe & Scala runs natively on Android. Not to be outdone, Apple has banned all iOS apps not coded in Haskell. The Windows ecosystem is now powered entirely by F#.

Other than that, nothing much has changed.

The canonical Mr. Shipper graduates from UPenn and lands his first whiteboard interview at the big G.

Google: So Mr. Shipper, do you know FizzBuzz ?
Shipper: Are you kidding me ? This is 2016, not 2012. Everyone and their grandmother knows Fizzbuzz.
Google: OK, lets try a slightly modified fizzbuzz.

Problem: How do you map the list on the left to the list on the right ?

Shipper: So lets see. You are mapping some stuff on the left list to other stuff on the right list.
Google: Yeah
Shipper: But you aren't mapping every element, just the multiples of 3 or 5.
Google: Yeah
Shipper: Looks like a partial function to me.
Google: Partial Function ? What's that ?
Shipper: Lets start with a predicate that defines who qualifies,

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

Google: Fine. So how do you use that ?
Shipper: I'll make another lambda that defines the mapping.

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

Google: OK. I see you know how to pattern match...
Shipper: Dude, this is 2016, not 2012 ! Everyone & their grandmother...
Google: Yeah, yeah. Got it. Now tell me what this partial function is ?
Shipper: The partial function just bundles together the predicate and the mapping. So

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

Now I just collect the results over which this partial function is defined.

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: Bravo! That is neat.
Shipper: Yeah!
Google: But tell me, Mr. Shipper, why do you need this partial function ? Can't you do something simpler ?
Shipper: You mean like map filter ?
Google: OK, lets try that...
Shipper: So I'd first filter with my predicate and then apply my mapping.

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: Good! But there's yet another way to do this.
Shipper: Hmmm...
Google: Think Sets. How do you define a set in math ?
Shipper: You mean, like a list comprehension?
Google: You got it!
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: Excellent! So you know how to do fizzbuzz atleast 3 different ways.
Shipper: Do I get the job ?
Google: Patience, Mr. Shipper. Patience! This is Google. We can't hire everybody who walks through the door and solves a fizzbuzz. This is 2016, after all. Everybody would get hired.
Shipper: So..
Google: So we here at Google have come up with a new test. Its called the Inverse FizzBuzz.
Shipper: Inverse FizzBuzz !
Google: Good! Looks like you never heard of it.
Shipper: Never!
Google: Well, we just came up with it last week. But its not so hard. You know what an inverse is.
Shipper: Inverse...
Google: Yeah, like 5 plus what is 0 ?
Shipper: -5
Google: So minus 5 is ?
Shipper: Oh! Yeah. OK. Minus 5 is the additive inverse of 5.
Google: So what's the multiplicative inverse of 5 ?
Shipper: Hmmm. 0.2. Because 0.2 times 5 is 1.
Google: You got it! What's the inverse sine of a half ?
Shipper: 30 degrees, because sine(30) = 0.5
Google: Good. What's the inverse logarithm of a half ?
Shipper: The square root of e.
Google: Very Good! So lets talk about the inverse of a fizzbuzz.
Shipper: OK. How do you define Inverse FizzBuzz ?
Google: Very simple. Given a list, give me the shortest contiguous sequence of numbers that produces that list when you run fizbuzz
Shipper : Huh ?!
Google: Inverse FizzBuzz - Given a list, what's the shortest contiguous sequence of numbers that produces that list when you run fizbuzz ?
Shipper: I don't follow.
Google: Lets do a few simple examples. What's the shortest sequence that produces { fizz }
Shipper: Hmm. { 1,2,3 }
Google: Come on Mr. Shipper. You can do better than that.
Shipper: OK. Its just {3}.
Google: What's the shortest sequence that produces { buzz }
Shipper: { 5 }
Google: What's the shortest sequence that produces { fizz, buzz }
Shipper: { 3, 4, 5 }
Google: Nope!
Shipper: OK. Wait....its {9,10}
Google: Excellent! What's the shortest sequence that produces { buzz, fizz }
Shipper: { 5,6 }
Google: What's the shortest sequence that produces { fizz, buzz, fizz }
Shipper: { 3, 4, 5, 6 }
Google: What's the shortest sequence that produces { buzz, fizz, buzz }
Shipper: Hmmm. I don't think that list is valid...
Google: Good. So your program will have to detect that. Lets do a few more. What produces { fizz, fizz } ?
Shipper: { 6,7,8,9 }
Google: What produces {fizz, fizz, buzz }
Shipper: { 6,7,8,9,10}
Google: OK. So here's the examples we've seen so far. This is what your lambda must do.

Google: Now write a lambda for Inverse FizzBuzz !
Shipper: Well, the solution is not unique. The sequence {fizz} maps to { 3 }, but it could also map to {6}. Or {9} ...
Google: Yeah, well, I don't care about uniqueness. Just the shortest sequence.
Shipper: So what's the problem again ?
Google: Given a list, what's the shortest contiguous sequence of numbers that produces that list when you run fizbuzz ?
Shipper: I honestly don't know.
Google: Well, what do you do when you don't know how to solve a problem ?
Shipper: Try everything. Brute force.
Google: Exactly!
Shipper: But brute force! That would be like an infinite number of input strings.
Google: Lets say we only care about the first 100 numbers. 1 to 100. Just like before. How many possible combinations on those ?
Shipper: Well, I could run fizzbuzz on 1. Then {1,2} Then {1,2,3}, Then {1,2,3,4} etc. upto {1,2,....100}
Google: So that's a 100 combinations.Shipper: But then I could run fizzbuzz on 2. Then {2,3} Then {2,3,4}, Then {2,3,4,5} etc. upto {2,....100}
Google: So that's how many ?
Shipper: 99. Ok I got it. So its like 100 + 99 + 98 + ...1 = (101)*100/2 = 5050 combinations.
Google: So five thousand plus. That's a small number.
Shipper: Right. But we kill duplicates. And we only keep the mapping that produces the shortest sequence.
Google: Yeah, so your final list will be much smaller than 5050.
Shipper: OK. I think I can do that quite easily.

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: So we have the 5050 possible ranges.
Shipper: Yes. Now I just run fizzbuzz on every one of those 5050 ranges.

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

Shipper: Now I'll line up the inputs with the outputs.
scala> val io = all.zip( results )

Shipper: Now I'll group by the output. That should give me a mapping from the list of strings to a list of sequence of numbers.

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

Google: Lets first see if you are on the right track so far. Count the keys in your mapping. It should be much smaller than 5050.

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

Google: Good! Only 302 unique keys, not 5050. Now how would you find the smallest value the key maps to ?
Shipper: Lemme first test with "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: OK. That gives me all the ranges my key maps to. I just need to find the smallest range. Lets try 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: Hey, I think I got it!

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: Lets check the answers to the 7 examples.
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: Voila!
Google: Absolutely. Voila!
Shipper: So do I get the job now ?
Google: Well, you've used a brute force approach. Tell you what. Come up with a non-brute force answer & the job's yours.

Shipper: Thinking.....Thinking.....Thinking.....

PS: Its actually not that hard :)

So, to recap:
Question: Inverse FizzBuzz - Given a list, what's the shortest contiguous sequence of numbers that produces that list when you run fizbuzz ?

Brute force solution:
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

Comments

David Bell

05/04/2012 9:38am

The fizzbuzz pattern is a periodic sequence of the form fbffbfx, where x is a fizzbuzz. We know that x is a multiple of 15, and the values of f are determined by one lookahead and b by two. We can also use the same idea in reverse to extend a pattern indefinitely.

Thus, the general algorithm is given our pattern to extend it to the nearest x, which we seed with an initial value equal to (number of x's)*15. Then, we iterate backwards over the pattern and fill in the values based on the lookahead. If there is no valid lookahead (say for a b followed by another b) then we throw an error.

Finally, we iterate over the original pattern to get the values of the sequence.

This approach will take linear time proportional to the length of the initial sequence and constant extra space to solve, since both the look-up table and pattern extension are bounded by the alphabet and periodicity of the pattern.

foobar

05/05/2012 6:27am

I can't believe everyone is ignoring your superior solution.

Ming

05/04/2012 10:37am

The John Hughes' paper is dated in 1984. That was before Java, C#, and the explosion of OOP popularity. Is the paper still relavent?

dxbydt

05/04/2012 10:49am

In academia, its generally accepted that Professor Hughes has more wisdom in that single paper than all the OO getter setter mutable state ftw garbage that pervades industry these days. But if you want corporate endorsement, read this paper by Don Syme at Microsoft Research : http://cufp.org/archive/2008/slides/SymeDon.pdf

shawn

05/06/2012 7:43am

YES! very much so. It's a pretty safe to say that the most relevant papers in CS are still most papers from the 60's (and a select few from the 50's ans 70's). There have been a few scatterings of good papers since (e.g. Hughes, Milne, Sussman and a few other great names). I'm obviously simplifying a little.

Java and C# are actually much more similar to the "structured programing" style that the inventors of OO were trying to move away from than they are similar to languages like Simula and especially Smalltalk.

But yes, we tend to think anything more than 5 years old in CS is antiquated but do a terrible job at teaching CS history. "Those who don't know their history are bound to repeat it." Psychology, in contrast very much teaches it's history even though some of the earlier theories have been dispelled.

anand jeyahar link

05/04/2012 12:56pm

Hmm.. which version of scala was this? and which java does it run on? am a python programmer jumping into scala. looks like the <Range>.collect and .<RandomAccessSeq>.flatten methods have been moved. Am on scala 2.7.7 and java-6-openjdk.

As for a non-brute force one pattern to eliminate would be any fizz sandwiched between two buzz's (see you can't get two multiples of five with only one multiple of 3 in natural numbers).

dxbydt

05/04/2012 1:04pm

Scala 2.9.2 and jdk 1.7
There are many patterns like the one you found. Some code would be nice:)

dave

05/04/2012 1:28pm

Something more elegant will come to me. I hope...
https://gist.github.com/2597800

Tinco link

05/04/2012 1:40pm

I'm not sure if this is better than the brute force one. My naieve attempt in Haskell: https://gist.github.com/2597922

Kikito

05/04/2012 3:54pm

"Given a list, what's the shortest contiguous sequence of numbers that produces that list when you run fizbuzz ?"

Well, the answer is, obviously

"the shortest contiguous sequence of numbers that produces that list when you run fizbuzz"

:P

Zack Maril

05/04/2012 7:16pm

A possible solution with clojure:
https://gist.github.com/2599321

Not sure how close to O(n) it is. There is a better way to do it somewhere.

Takahiro Noda link

05/17/2012 7:05pm

Yet another Inverse Fizzbuzz solver in Clojure:

https://gist.github.com/2717342

Juan Lopes

05/04/2012 8:45pm

Solution in functional python:

https://gist.github.com/2599776

Chris Kuklewicz

05/09/2012 4:26am

Efficient solution in haskell, not bound to first 100 characters:

https://gist.github.com/2644157

Tomohito Ozaki

05/14/2012 9:16pm

Solution in Scala Using Strream.

https://gist.github.com/2699068

Chris Kuklewicz

05/17/2012 2:59am

Solves different problem that keeps track of blanks. Does not seem to look for shortest sequence.

xuwei-k link

05/14/2012 10:41pm

https://gist.github.com/2699263

Brian Balke

06/27/2012 8:26am

So this guy gets shown the door because he didn't think to ask:

"Why do you care?"

Which leads to questions like "How does this scale to larger symbol sets?"

For example, "fizz, buzz, Doh!"

how to cure gonorrhea link

12/02/2012 8:05pm

I was unable to understand inverse fizz buzz, but after reading your blog i got the answer . You have updated a great detail about this inverse buzz.

trailer brake controllers link

12/18/2012 10:27pm

The concept of Inverse Fizzbuzz is indeed quite new to me. After reading this post, I got a clear idea about it.

drug rehab link

12/21/2012 1:14am

Great news that scala seeks to integrate features of object-oriented and functional languages that's why code sizes are typically reduced which is a good news for programmers.

Arlene link

12/27/2012 11:58pm

Thank you for sharing such great information with us. I really appreciate everything that you’ve done here and am glad to know that you really care about the world that we live in

abwe link

01/15/2013 1:37am

You have indeed shared very vital post regarding Fizzbuzz. I was aware of this concept but thanks to you.

underwater treadmills link

01/22/2013 11:26pm

I was not aware of the concept Fizzbuzz. The above post has indeed given me the entire information about Fizzbuzz.

nevada dui lawyer link

03/26/2013 12:55am

Your article tells me you must have a lot of background in this topic. Can you direct me to other articles about this? I will recommend this article to my friends as well. Thanks

How To Grow Your Eyelashes link

04/16/2013 3:02am

I was not aware of the fact that Apple has banned all the iOS applications which is not coded in Haskell. Thanks for sharing such interesting information.

Bjj Kimono link

04/16/2013 10:44pm

I am really amazed by the interview questions posted by Google to the Shipper. Thanks for sharing such interesting information.

cheap Oakley sunglasses link

05/07/2013 1:17am

Brand sunglasses are not worth that much, most of the brand sunglasses (such as Bulgari, Prada glasses) are actually manufactured with an Italian manufacturer Luxottica.

Cartier sunglasses link

05/08/2013 11:51pm

Quack,Quack the frogs were singing in the fields. The crickets were blowing

Inverse Fizzbuzz

Comments

Leave a Reply