Saturday, August 6, 2011

FizzBuzz

The "new classic" programming test seems to be the FizzBuzz problem. I think it was first proposed in a blog post from 2007.

Now that it has garnered so much awareness (even videos on YouTube!), it's probably not a good interview question anymore. However, now that implementations have been written in many languages, it can be used to learn and compare the syntax of new languages.

Implementation

We can see how it works in Python:
>>> for i in range(1,101):
        if not i % 15:
            print "FizzBuzz"
        elif not i % 3:
            print "Fizz"
        elif not i % 5:
            print "Buzz"
        else:
            print i
A similar version in Clojure:
=>(defn multiple? [n div]
    (= 0 (mod n div)))

=>(doseq [i (range 1 101)]
     (cond (and (multiple? i 3)(multiple? i 5))
             (println "FizzBuzz")
           (multiple? i 3)
             (println "Fizz")
           (multiple? i 5)
             (println "Buzz")
       :else (println i)))
And, finally, a version in Factor:
( scratchpad ) 100 [1,b] [
                   {
                       { [ dup 15 divisor? ] [ drop "FizzBuzz" ] }
                       { [ dup 3  divisor? ] [ drop "Fizz"     ] }
                       { [ dup 5  divisor? ] [ drop "Buzz"     ] }
                       [ present ]
                   } cond print
               ] each

Improvements

Let's see if we can improve the Factor version a bit. First, we can "factor out" the FizzBuzz logic into its own function (showing how it would look if you were to code this directly into the listener):
( scratchpad ) : fizzbuzz ( n -- )
                   {
                       { [ dup 15 divisor? ] [ drop "FizzBuzz" ] }
                       { [ dup 3  divisor? ] [ drop "Fizz"     ] }
                       { [ dup 5  divisor? ] [ drop "Buzz"     ] }
                       [ present ]
                   } cond print ;

( scratchpad ) 100 [1,b] [ fizzbuzz ] each
To avoid all the dup and drop words, we could build a variation of cond that acts a bit like a case. The "cond-case" word was suggested on the Factor mailing list, and this is one variant of it:
MACRO: cond-case ( assoc -- )
    [
        dup callable? not [
            [ first [ dup ] prepose ]
            [ second [ drop ] prepose ] bi 2array
        ] when
    ] map [ cond ] curry ;
Using cond-case, we can improve the original version:
: fizzbuzz ( n -- )
    {
        { [ 15 divisor? ] [ "FizzBuzz" ] }
        { [ 3  divisor? ] [ "Fizz"     ] }
        { [ 5  divisor? ] [ "Buzz"     ] }
        [ present ]
    } cond-case print ;
If we realize that the check for divisible by 15 is the same as checking for divisible by 3 and divisible by 5, we can implement it slightly differently, without a cond or case:
: fizz ( n -- str/f )
    3 divisor? "Fizz" and ;

: buzz ( n -- str/f )
    5 divisor? "Buzz" and ;

: fizzbuzz ( n -- )
    dup [ fizz ] [ buzz ] bi "" append-as
    [ present ] [ nip ] if-empty print ;
Is it better? Can you think of any way to make it simpler? Perhaps by using or inventing some higher-level concepts like we did with cond-case?

1 comment:

yac said...

I think that `cond-case` should definitely be in the combinators vocabulary. Seriously, `cond` is ugly and redundant in this common case.