Wednesday, February 8, 2012

FizzBuzz

Apparently, the "FizzBuzz" problem is a common programming interview question. I came across it while reading You Can't Teach Height - Measuring Programmer Competence via FizzBuzz on Scott Hanselman's blog.

The "FizzBuzz" problem is:
Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.
After reading this, my first thought was to write code to solve the problem. Funny that the end of Hansleman's post states:
One other thing that's amazing to me ... is that some of the programmers who read these blogs feel the need to actually solve the FizzBuzz problem.
They've completely - no, I need a work with more oomph - utterly? missed the point.
I'm pretty sure the point of his post is just that an interviewer should ask the applicant to show what he/she can do, rather than just talk about it. I agree with this. And I always have a better feeling about a place where I interview if they at least have me provide code samples and have me talk about them.

But I've got to agree with one of the commenters:
Missed the point?? Developers are problem-solvers - OF COURSE we're going to try to code a solution! :-)
I love puzzles. So I tried coding it without looking up anything, then compiling to see if it worked. I first used a switch/case statement, so that if a number was both a multiple of 3 and 5, it would fall through both and output "FizzBuzz" without needing a separate case to handle both, something like this:

switch (i)
{
    case i % 3 == 0:
        Console.WriteLine("Fizz");
    case i % 5 == 0:
        Console.WriteLine("Buzz");
    default:
        Console.WriteLine(i);
}

Whoops. C# only allows constants in switch/case statements, and it doesn't support break fall-throughs, either (need to use "goto"!). So I tried to mimic it with regular if/then statements. But at the same time, I also had the idea to make it a method, so I ended up with this:

using System;
using System.Collections;
using System.Text;

namespace FizzBuzz
{
    class Program
    {
        static void Main(string[] args)
        {
            foreach (string i in fizzBuzz())
            {
                Console.WriteLine(i);
            }

            Console.ReadLine();
        }

        private static IEnumerable fizzBuzz()
        {
            bool isReplaced = false;

            for (int i = 1; i < 101; i++)
            {
                if (i % 3 == 0)
                {
                    yield return "Fizz";
                    isReplaced = true;
                }

                if (i % 5 == 0)
                {
                    yield return "Buzz";
                    isReplaced = true;
                }

                if (!isReplaced)
                {
                    yield return i.ToString();
                }

                isReplaced = false;
            }
        }
    }
}
This works, but for numbers like 15, it outputs Fizz and Buzz on two separate lines. It would be better off combining the 3 and 5 multiple case first, and having one if/else statement.

By the way, this doesn't loop twice - it starts the loop in main, goes into the fizzBuzz method, runs the logic until it gets to a "yield" statement, then finishes the loop in main, then runs the next iteration of the loop. It then picks up where it left off in the fizzBuzz method. This approach would let you format each string iteration differently if you wanted to (i.e. having the word "Fizz" output in green).

So my next thought was to compare my solution to others. I found this, which has a number of solutions in many different languages (none use the enumerable interface idea).

The Articulating Ideas blog has a really interesting post on efficient ways to solve the problem using C# - the bitwise operator one is very interesting (and a bit beyond my current coding skills):

string[] messages = new string[]{null, "Fizz", "Buzz", "FizzBuzz"};
int acc = 810092048; //11 00 00 01 00 10 01 00 00 01 10 00 01 00 00
int c = 0;
for (int i=1; i < = N; ++i)  {
    c = acc & 3;
    result += (c > 0 ? messages[c] : i.ToString()) + ", ";
    acc = acc >> 2 | c < < 28;
}


I'm surprised that this solution wasn't the clear winner (it tied another very slick version that doesn't use modulo, and was only a little faster than another using modulo). Division is usually the most expensive math operation, and shifting bits lets you get around that very cleverly (if you are clever enough to know how to use it...).

It really is true that 100 different programmers will come up with 100 different solutions to the same problem.

Saturday, February 4, 2012

C# "??" operator

I just ran across something I hadn't seen before - a two question mark operator. I found it in the AccountMembership service method in the default AccountModel.cs file that's used when you start a new ASP.NET MVC 3 project. Here's the line of code:
_provider = provider ?? Membership.Provider;
I did a little research and found it's just a shortcut for this, using an iif/conditional:
_provider = provider != null ? provider : Membership.Provider;
which of course is a shortcut for this regular if statement:
if(provider != null) {
     _provider = provider;
} else {
     _provider = Membership.Provider;
}

More info here: http://msdn.microsoft.com/en-us/library/ms173224.aspx
Very cool. I love the terseness of C#.