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 solution: Seq.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.

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 solution: Seq.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 ? )( or in pictures, how do you go from stuff on the left to stuff on the right ? )

Say

"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 )

**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:

Now you reform transitions - ie. put lambda-transitions between states with no transitions.

That produces the monster below:

That produces the monster below:

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

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!

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!

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 )