I invented/discovered/came-upon "Inverse Fizzbuzz"  while mucking about with Scala & Partial Functions.

While Fizzbuzz answers the question  "Can Shipper code  ? ", Inverse Fizzbuzz tells you "How well does Shipper code ?"

After posting the Hacker News piece,  Inverse Fizzbuzz was featured on a codegolf.

There were a dozen participants - with solutions in Ruby, Perl, Python, Scheme, PHP, Javascript, Groovy, and yes , Scala. After the golf ended, the results were somewhat bizarre. The Perl solution by tybalt89 won, with a score of 10,000.
Here's the winning entry - practically a one-liner.

#!perl -lp
s/\w{5}/E/g+y/F-z /F/d>8&&s/\B/ */g;$_=" F BF FB F E"x22~~/$_/&&1+"@-"." @+"

Now guess the solution that came in dead last ? Scala ! That bothered me a little bit. But what bothered me the most was the cheating :)

Cheating! What do I mean by that ?  Take a look at the test case
Here's what the outputs look like: look at the item in red.
9 72
3 3
3 12
3 45

6 10
5 6
3 96
12 102


12 15
5 5
3 93
15 177
3 27
5 33
9 115
9 48
9 87
15 18
9 30

9 180
6 9
15 15
9 135
12 18
12 96
10 15
3 55
-----

So if somebody told you that the largest fizzbuzz string mapped to 180, then you can cheat by simply generating all possibles upto/beyond 180, use memoization & simply compare the test input to what you've precomputed. That's what most of the entries had done.

So for example, the Perl solution has " F BF FB F E"x22 ie. 15 times 22 > 180
In the Python solution : see the number 182
In the Haskell solution : the number 171
In the Scala solutionSeq.tabulate(181)
In the Javascript solution : the number 182

I decided I wouldn't cheat. Instead I will solve Inverse Fizzbuzz from first principles, using a Finite State Machine => Regex  approach.
Note: I'm not interested so much in the numbers on the RHS as much as making sure if a sequence of strings actually corresponds to a valid "Inverse Fizzbuzz" . So the goal is to test language memberships. Number gymnastics can come later.

Inverse FizzBuzz - Given a list of strings , what's the shortest contiguous sequence of numbers that produces that list when you run fizbuzz ( over those numbers ) ?
( or in pictures, how do you go from stuff on the left to stuff on the right ? )

Say fizz = f, buzz = b, fizzbuzz = g

The finite state machine that produces the language of "Inverse Fizzbuzz" must have 8 states and must look like below

Its not too hard to see why.
"Fizz" qualifies - ergo, go from start state q0 via arc "f" to terminal state q1
"Buzz" qualifies - go from start state q0 via arc "b" to terminal state q2
"Fizz Buzz" qualifies -  go from start state q0 via arc "f" to  q1, then via arc "b" to terminal state q2.
"Fizz Buzz Fizz" qualifies - go from start state q0 via arc "f" to  q1, then via arc "b" to q2, then via "f" to terminal state q3.
Clearly "Buzz Buzz" does not qualify, so there's no way to produce "bb" via the machine below.
And so on and so forth... ( If you have a simpler FSM, please do email me )

Getting rid of the multiple terminal nodes will introduce lambda-transitions ( NFA-epsilons )
and you get the machine below:

Picture

Now you reform transitions - ie. put lambda-transitions between states with no transitions.
That produces the monster below:

Picture

Finally, the Collapse mode: get rid of the non-final and non-initial states systematically, and JFLAP leaves you with :

Picture

So then, lets turn to the trusted Scala REPL to try out the regex.

scala> val p = "f|b|fb|f|(b|fb)f|f|(f|(b|fb)f)f|b|(f|(f|(b|fb)f)f)b|f|(b|(f|(f|(b|fb)f)f)b)f|(g|(f|(b|(f|(f|(b|fb)f)f)b)f)g)(fbffbfg)*(f|fb|fbf|fbff|fbffb|fbffbf){0,1}".r
p: scala.util.matching.Regex = f|b|fb|f|(b|fb)f|f|(f|(b|fb)f)f|b|(f|(f|(b|fb)f)f)b|f|(b|(f|(f|(b|fb)f)f)b)f|(g|(f|(b|(f|(f|(b|fb)f)f)b)f)g)(fbffbfg)*f|fb|fbf|fbff|fbffb|fbffbf){0,1}

So p is the regex correponding to Inverse Fizzbuzz.
Lets get the matching engine out of p so we can try various language matches upon it.

scala> val m = p.pattern.matcher _
m: java.lang.CharSequence => java.util.regex.Matcher = <function1>

scala> m ("f") matches
res25: Boolean = true

scala> m ("b") matches
res26: Boolean = true

scala> m ("fb") matches
res27: Boolean = true

scala> m ("ff") matches
res28: Boolean = true

scala> m ("bf") matches
res29: Boolean = true

scala> m ("bb") matches
res30: Boolean = false

scala> m ("bff") matches
res31: Boolean = true

scala> m ("bfg") matches
res32: Boolean = true

scala> m ("g") matches
res33: Boolean = true

scala> m ("gb") matches
res34: Boolean = false

scala> m ("gf") matches
res35: Boolean = true

So that's that!
Inverse FizzBuzz as a regex =
"f|b|fb|f|(b|fb)f|f|(f|(b|fb)f)f|b|(f|(f|(b|fb)f)f)b|f|(b|(f|(f|(b|fb)f)f)b)f|(g|(f|(b|(f|(f|(b|fb)f)f)b)f)g)(fbffbfg)*(f|fb|fbf|fbff|fbffb|fbffbf){0,1}""

JFLAP FTW!
Picture
Postscript: The "Regular Expression Exploration" Tool produced by Microsoft Research consumes a RegEx and produces an automaton. When fed the Inverse Fizzbuzz Regex, it produced the alongside automaton with 81 states !!! ( Thanks to sureshv at HN

 


Comments

06/27/2012 6:21am

Awesome! I like how you actually solved the problem.

Reply
Harsh Gupta
07/14/2012 3:49pm

That was a pretty good demonstration of the solution. But if I am not mistaken, I would guess your solution is incomplete. Your solution only points out if a given sequence is valid or not i.e. only prints boolean true or false, but doesn't actually gives out the sequence of numbers, as asked in the question.

So even if you are not cheating, your solution is also not giving the result expected.

Reply
11/28/2012 9:05pm

Was a bit confusing but finally got it. :)

Reply
06/03/2013 3:02am

Take steps to add colors, feel and texture. Look at popular home improvement magazine to stimulate your ideas. Never be afraid to ask for help and opinions.

Reply
06/03/2013 3:03am

Regardless of the method you choose it is imperative that you provide adequate and pertinent information on the horse or horses you want to sell or promote.

Reply

Take steps to add colors, feel and texture. Look at popular home improvement magazine to stimulate your ideas. Never be afraid to ask for help and opinions.

Reply
06/03/2013 3:06am

Regardless of the method you choose it is imperative that you provide adequate and pertinent information on the horse or horses you want to sell or promote.

Reply
06/03/2013 3:06am

Before current technology came to the forefront, we had about seven basic modes of communication: telephone, telegraph wire, television, radio, mail, fax machines, eventually the pager (or beeper) and the grapevine---over the fence

Reply
06/03/2013 3:07am

You also should check out any loan company thoroughly by running them through the Better Business Bureau website to see if they have many complaints filed against them.

Reply
06/03/2013 3:07am

By getting in touch with someone whose caliber is accounted for by many of his clients can surely help you in achieving your desired goals for the future.

Reply
07/15/2013 4:33am

The inverse fizz buzz logic is great. I really liked the logic behind your work. The article is very interesting and the description given is very clear and elaborate. The graphical and pictorial explanations given are helpful in understanding the logic. Thanks a lot for sharing this post

Reply
07/27/2013 6:11am

This is a smart blog. You have so much knowledge about this issue, and so much passion.

Reply
08/16/2013 7:51am

I'm not necessarily curious so much inside volumes within the RHS approximately ensuring that if the sequence involving strings in fact matches into a good "Inverse Fizzbuzz.

Reply
08/27/2013 2:09am

Thanks for all your efforts that you have put in this. Very interesting information. I like with express my support of your ideas in your article, and looking forward to your next article.

Reply
09/05/2013 4:54am

Thanks alot for sharing this nice post here with us..!

Reply
09/07/2013 5:53pm

Lovely blog, thanks for posting.

Reply
09/14/2013 5:44am

Eventually, the Crash vogue: win purge of the stop-definitive moreover stop-primary countrys systematically.

Reply
09/18/2013 4:14am

Creating a list of the first hundred Fizz buzz numbers is a trivial problem for any would-be computer programmer, so interviewers can easily sort out those with insufficient programming ability. Thanks for information.

Reply

Immediately you permutation spurs - ie. put lambda-processs among nations along no legs.

Reply

This is a great article with well-scripted, engaging content that is full of original and sensible views. Much of your informative content is in line with my way of thinking.

Reply
10/21/2013 2:49pm

I recite numerous cycles your blog,Very good and useful information.Thanks

Reply



Leave a Reply