Sunday, 3 June 2012

FizzBuzz coding challenge, the functional way

[Level T2]

I think most of you guys have either heard about the popular FizzBuzz coding challenge or actually been asked to solve during an interview. However, for those of you that have not heard it, here it is (or at least a version of it):
Ask the user to enter two integers: start of the range and end of the range. Then for every integer in the range, output "Fizz" if the integer is dividable by 3, output "Buzz" if it is dividable by 5, output "FizzBuzz" if dividable by 15 otherwise output the number itself.
Unless one is a novice programmer, implementing this is not really hard. Adding stress of the interview, unfamiliarity of the location and the machine you are given for the challenge, it probably can represent a moderate-difficulty task for the interview if you have heard about it for the first time. But like said by many before, always ask developers to write some code during interview. Be it as simple as this challenge.

C#, a functional language?

No, I know it is not. Yet, it has a lot of the elements of functional programming since v 3.0 with Func and Action. PTL has made it even more functional since not only a function can be abstracted as Action or Func, its result and state can be abstracted and encapsulated as Task<T>.

Until recently, I have been unaware of the power of the functional programming that is possible in C#. And the reason is you have to think functional first to be able to do functional. It might surprise you that in fact Javascript (not particularly known as a functional language) inspired me to start thinking functionally - but that's another story for another day.

So I have picked up a simple scenario to gradually build up using functional C#. If you are a fluent Haskell, F# or Erlang developer perhaps this post is not for you - unless you would like to see the functional features of C#. So let's start with the conventional approach.

FizzBuzz, the conventional procedural way

As I said before, solving FizzBuzz challenge the conventional way is almost trivial (assuming we have captured user input):

private static void ConventionalApproach(int start, int end)
{
 for (int i = start; i <= end; i++)
 {
  if(i % 15 == 0)
  {
   Console.WriteLine("FizzBuzz");
  }
  else if (i % 3 == 0)
  {
   Console.WriteLine("Fizz");
  }
  else if (i % 5 == 0)
  {
   Console.WriteLine("Buzz");
  }

 }
}

The only point to note is that the condition to divide by 15 must be written first, obviously, since every number dividable to 15 is also dividable by 3 and 5.

We might actually improve the "performance" by sparing the division to 15 so that division by 15 is defined by division by 3 and division by 5 which the output will be "Fizz" + "Buzz" => "FizzBuzz".

private static void ConventionalApproachImprovedPerf(int start, int end)
{
 for (int i = start; i <= end; i++)
 {
  bool wroteAny = false;
  if (i % 3 == 0)
  {
   Console.Write("Fizz");
   wroteAny = true;
  }
  if (i % 5 == 0)
  {
   Console.Write("Buzz");
   wroteAny = true;
  }
  if (!wroteAny)
  {
   Console.Write(i); 
  }
  Console.WriteLine();

 }
}

This sort of detail is the kind of stuff your interviewers are expected to see in your solution.

What a functional solution could look like?

Functional approach lays out all new possibilities and as such, I think everyone might come up with a different solution. But I would like to present my solution which looks like this:

var chain = ChainOfResponsibility<int>
 .Start(i => i.IsDividableBy(15), i => "FizzBuzz".OutputLine())
 .Then(i => i.IsDividableBy(3), i => "Fizz".OutputLine())
 .Then(i => i.IsDividableBy(5), i => "Buzz".OutputLine())
 .Else(i => i.OutputLine());

Enumerable.Range(rangeStart, rangeEnd+1).ToList()
 .ForEach(x => chain.Run(x));

Well. This looks a lot more readable. Let's see how to build it.

Abstracting out

OK, now let's first of all think about what we have just done. We used if statements a lot. So what is an if statement:
"if" is an expression that produces a boolean value. That boolean value is fed to an action - if it has a value of true.
So in pseudo-code terms:

if ( a_condition )
  do_something()

More specifically for our case since we have an integer input to we can re-write this as:

if ( a_condition(input) )
  do_something(input)

So we can say that the condition is Predicate<int> and the action is an Action<int>. Predicate<T> is actually nothing but Func<T, bool> which means that it takes an input of type T and returns a boolean.

Chain of responsibility

Chain of responsibility is a design pattern that can be thought of as a series of if-else whereby the first one to fulfil the condition will short-circuit the path and the rest of conditions will not be checked. 

The first implementation above (which contains a series of if and if-else) can be thought of as a chain of responsibility.

In our functional approach we implement a chain of responsibility as below (note the return this statement leading to fluent API making our code more readable):

public class ChainOfResponsibility<T>
{
 private List<ConditionalAction<T>> _chain = new List<ConditionalAction<T>>();

 private ChainOfResponsibility(ConditionalAction<T> conditionalAction)
 {
  _chain.Add(conditionalAction);
 }

 private class ConditionalAction<TInput>
 {
  public Predicate<TInput> If { get; set; }
  public Action<TInput> Do { get; set; }
 }

 public static ChainOfResponsibility<T> Start(Predicate<T> condition, Action<T> action)
 {
  return new ChainOfResponsibility<T>(new ConditionalAction<T>()
  {
   If = condition, 
   Do = action
  });
 }

 public ChainOfResponsibility<T> Then(Predicate<T> condition, Action<T> action)
 {
  _chain.Add(new ConditionalAction<T>()
  {
   If = condition,
   Do = action
  });
  return this;
 }

 public void Run(T input)
 {
  foreach (var conditionalAction in _chain)
  {
   if(conditionalAction.If(input))
   {
    conditionalAction.Do(input);
    break;
   }
  }
 }

 public ChainOfResponsibility<T> Else(Action<T> action)
 {
  return Then((i) => true, action);
 }
}

This is a simple implementation which defines a generic type of T for inputs of conditions and actions. Now in order to make our code even more readable, let's define some static extension for IsDividable and Ouput for console:

public static class Int32Extensions
{
 public static bool IsDividableBy(this int a, int b)
 {
  return a%b == 0;
 }
}

public static class ObjectExtensions
{
 public static void Output(this object o)
 {
  Console.Write(o);
 }
 public static void OutputLine(this object o)
 {
  Console.WriteLine(o);
 }
}

Now to use the code, all we have to write is:

var chain = ChainOfResponsibility<int>
 .Start(i => i.IsDividableBy(15), i => "FizzBuzz".OutputLine())
 .Then(i => i.IsDividableBy(3), i => "Fizz".OutputLine())
 .Then(i => i.IsDividableBy(5), i => "Buzz".OutputLine())
 .Else(i => i.OutputLine());

Enumerable.Range(rangeStart, rangeEnd+1).ToList()
 .ForEach(x => chain.Run(x));

This code is not necessarily shorter or more performant. But it is much more readable/maintainable and the intention of the developer and underlying logic is apparent just be reading the code as a sentence.

Getting the user input

if you have ever worked with a console app and tried to get the user input from the standard input, you definitely have experienced how clumsy the implementation can be.

Now we want to do this in a simple yet generic fashion using functional programming.

Our logic can be simplified and represented as below:
  • A type: type of the value to be cast from string input
  • A validation function to verify the value
  • A conversion function
  • and A message to be shown in case the value is not in the correct format.
So all of this can be simplified as the function below:

private static T GetUserInput<T>(string message, 
 Predicate<string> validation, Func<string, T> conversion)
{
 while(true) // ideally we must allow an escape route for the user but they can just close the application if they are tired so we just create an endless loop
 {
  Console.WriteLine(message);
  string value = Console.ReadLine();
  if (validation(value))
   return conversion(value);
 }
}

So we can define the logic as below. Note that the validation of the end range makes sure this value is larger than the range start:

int tempInt = 0;
int rangeStart = GetUserInput<int>("Please enter start of the range (positive numbers):",
 s => int.TryParse(s, out tempInt) && tempInt >= 0,
 s => int.Parse(s));

int rangeEnd = GetUserInput<int>("Please enter end of the range (positive and larger than start):",
 s => int.TryParse(s, out tempInt) && tempInt > rangeStart, // note the "Closure" of rangeStart
 s => int.Parse(s));

Conclusion

C# is not a functional language but contains many of the functional languages constructs. Lambda expressions, Func and Action, etc help us to be able to write a more readable code by composing functions.

Functional C# is definitely fun!

No comments:

Post a Comment