Monday, June 4, 2012

Functional FizzBuzz in C#

Back when Jeff Atwood first wrote about FizzBuzz, I implemented it a number of different ways in Delphi. It was an interesting exercise; I think I came up with around five different ways to implement it. I also did some performance testing and was surprised by the results. Perhaps someday I'll try to find that code and publish it. Over the years since, I've used it, or variations, in interviews and have been surprised at how many applicants it weeded out.

Recently I ran across an article listing several ways to do it in various functional languages and wondered how functional I could code it in C#. So, I fired up Visual Studio and created a new console project. I didn't think my first attempt was too bad.
namespace FunctionalFizzBuzz
{
  class Program
  {
    static string FizzBuzzResult(bool showFizz, bool showBuzz, int val)
    {
      return showFizz && showBuzz
        ? "FizzBuzz"
        : showFizz
          ? "Fizz"
          : showBuzz
            ? "Buzz"
            : val.ToString(CultureInfo.InvariantCulture);
    }

    static string GenerateFizzBuzz(int start, int end)
    {
      return Enumerable
        .Range(start, end)
        .Aggregate(new StringBuilder(), (seed, val) =>
          {
            seed.AppendLine(FizzBuzzResult(val % 3 == 0, val % 5 == 0, val));
            return seed;
          })
        .ToString();
    }

    static void Main(string[] args)
    {
      Console.WriteLine(GenerateFizzBuzz(1, 100));
    }
  }
}

However, there were a couple things I didn't like about it. First, returning the whole result as a string seemed a bit overkill and intuitively not too memory friendly. For purposes of displaying 100 lines, it's not too bad, but for a more general use case, it's not good for composition. Second, the use of Aggregate bothered me a bit. How it works is not obvious to most people when first seeing it; it's use is a bit obtuse. And concatenating a bunch of strings just felt wrong.

So, I replaced the string result with an IEnumerable. This allowed changes which I think expresses the intent better. First, the Aggregate could be be changed to a Select, clarifying the GenerateFizzBuzz method. Second, the call to Console.WriteLine to generate each output line could be passed as a parameter to an iterator function. This is an example of how the new method makes it easier to use the output for different things. Another example is to count how many "Fizz" lines there are.

static IEnumerable GenerateFizzBuzz(int start, int end)
{
  return Enumerable
    .Range(start, end-start+1)
    .Select(val => FizzBuzzResult(val % 3 == 0, val % 5 == 0, val));
}

static void Main(string[] args)
{
  var result = GenerateFizzBuzz(1, 100).ToList();
  result.ForEach(Console.WriteLine);
  Console.WriteLine("Number of Fizzes: {0}", results.Count(l => l == "Fizz"));
}

With the GenerateFizzBuzz method cleaned up some, my attention turned to the FizzBuzzResult method. I wasn't terribly happy with the multiple nested conditional statement. While functional, it seemed more computational than declarative to me. What it did was a bit opaque. I like the parameter pattern matching available in the more functional languages and wondered how I could do something similar. I couldn't think of a way to let the compiler do it and regular expressions (the only pattern matching I can think of in the .Net libraries) only works on strings. However, it seemed pretty straight forward using a data structure.

I created a dictionary with a boolean key and dictionary value. The nested dictionary also had a boolean key but with a string value. I initialized these with the four possible values. The case which should return the numeric value was set to null. Then then the result was simply the lookup value of the dictionaries unless it returned null, in which case it was the passed in value, converted to a string.

private static readonly Dictionary<bool, Dictionary<bool, string>>
  FizzBuzzMap =
    new Dictionary<bool, Dictionary<bool, string>>
      {
        {true, new Dictionary<bool, string> {{true, "FizzBuzz"}, {false, "Fizz"}}},
        {false, new Dictionary<bool, string> {{true, "Buzz"}, {false, null}}}
      };

static string FizzBuzzResult(bool showFizz, bool showBuzz, int val)
{
  return FizzBuzzMap[showFizz][showBuzz] ?? val.ToString(CultureInfo.InvariantCulture);
}

I liked the way FizzBuzzResult looked, but the initialization code for the dictionaries was a bit ugly to my eye. I tried changing it to a single dictionary containing an array of booleans as the key.

private static readonly Dictionary<bool[], string>
  FizzBuzzMap =
    new Dictionary<bool[], string>
      {
        {new[] {true, true}, "FizzBuzz"},
        {new[] {true, false}, "Fizz"},
        {new[] {false, true}, "Buzz"},
        {new[] {false, false}, null},
      };

static string FizzBuzzResult(bool showFizz, bool showBuzz, int val)
{
  return FizzBuzzMap[new [] {showFizz, showBuzz}] ?? val.ToString(CultureInfo.InvariantCulture);
}

Ah, this looked much nicer. But... it raised a key not found exception. Oops. Fail. I hypothesized the key comparison during lookup looked at the arrays as objects, rather than the values they contained, and so raised the exception. I quickly wrote a comparison class for the dictionary and passed in an instance of it.

internal class BoolArrayComparer : IEqualityComparer
{
  public bool Equals(bool[] x, bool[] y)
  {
    if (x.Length != y.Length)
      return false;
    return !x.Where((t, i) => t != y[i]).Any();
  }

  public int GetHashCode(bool[] obj)
  {
    return obj.Aggregate(0, (seed, val) => seed + val.GetHashCode());
  }
}

Sure enough, it now worked properly. So the initialization looked pretty, but at the expense of having to have this extra, ugly class floating around spoiling things. Reflecting on the prior solution with the arrays, I realized structures have slightly different semantics and might work better with comparison. I changed the boolean array to a two member structure.

internal struct FizzBuzzKey
{
  internal bool showFizz;
  internal bool showBuzz;
};

private static readonly Dictionary
  FizzBuzzMap =
    new Dictionary
      {
        {new FizzBuzzKey {showFizz = true, showBuzz = true}, "FizzBuzz"},
        {new FizzBuzzKey {showFizz = true, showBuzz = false}, "Fizz"},
        {new FizzBuzzKey {showFizz = false, showBuzz = true}, "Buzz"},
        {new FizzBuzzKey {showFizz = false, showBuzz = false}, null},
      };

static string FizzBuzzResult(bool showFizz, bool showBuzz, int val)
{
  return FizzBuzzMap[new FizzBuzzKey {showFizz = showFizz, showBuzz = showBuzz}] ?? val.ToString(CultureInfo.InvariantCulture);
}

And this worked without requiring a Comparer class. But it's quite a bit more verbose than the array notation; I really liked the succinctness of the array notation. Then I remembered structs can have constructors. I added one and this helped cut down the verbosity quite a bit.

So, in the end I finished this little exercise with the following.

namespace FunctionalFizzBuzz
{
  internal class Program
  {
    internal struct FizzBuzzKey
    {
      internal FizzBuzzKey(bool showF, bool showB)
      {
        showFizz = showF;
        showBuzz = showB;
      }

      internal bool showFizz;
      internal bool showBuzz;
    };

    private static readonly Dictionary
      FizzBuzzMap =
        new Dictionary
          {
            {new FizzBuzzKey (true, true), "FizzBuzz"},
            {new FizzBuzzKey (true, false), "Fizz"},
            {new FizzBuzzKey (false, true), "Buzz"},
            {new FizzBuzzKey (false, false), null},
          };

    static void Main(string[] args)
    {
      var results = Enumerable
        .Range(90, 11)
        .Select(val => FizzBuzzResult(val%3 == 0, val%5 == 0, val))
        .ToList();
      results.ForEach(Console.WriteLine);
      Console.WriteLine("Number of Fizzes: {0}", results.Count(l => l == "Fizz"));
    }

    private static string FizzBuzzResult(bool showFizz, bool showBuzz, int val)
    {
      return FizzBuzzMap[new FizzBuzzKey(showFizz, showBuzz)] ?? val.ToString(CultureInfo.InvariantCulture);
    }
  }
}

Final thoughts

One solution I considered during this process was to map the four values of booleans to integers and do a lookup after a conversion. Intuitively, I didn't like the approach because it added an extra level of abstraction. Levels of abstraction can be good if they clarify. However, in this case, I thought it would simply obfuscate. In spite of this, out of desire to be complete, I threw this implementation together too.

private static readonly Dictionary
  FizzBuzzMap =
    new Dictionary()
      {
        {3 /* true, true */, "FizzBuzz"},
        {2 /* true, false */, "Fizz"},
        {1 /* false, true */, "Buzz"},
        {0 /* false, false */, null},
      };

static string FizzBuzzResult(bool showFizz, bool showBuzz, int val)
{
  return FizzBuzzMap[(val%3 == 0 ? 1 : 0) + (val%5 == 0 ? 1 : 0)] ?? val.ToString(CultureInfo.InvariantCulture);
}

But it didn't work. It emitted "Buzz" in places it should have output "Fizz." But not all the time. It took me a minute or two to find it.

Can you spot the error?


The fact that 1) this was the first bug I'd produced during this exercise, 2) it wasn't immediately obvious what the problem was and 3) the need for the comments in the setup, all confirmed my suspicion this is not a good solution.

Two other things I vacillated over was whether FizzBuzzResult needed to be a separate routine and, if so, what its parameters should be. At times I'd roll it into the main routine and other times I'd pass in just the numeric value and yet other times I'd pass in the three parameters as shown. I concluded that a toy exercise like this is too small to really have a clear winner in this debate. Additional use cases provided by a larger application would probably make one of these various options a clear winner.

After going through this process, I did a web search on "C# functional FizzBuzz" and found a number of solutions including this interesting take.
Post a Comment