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”.

Tuesday, January 31, 2012

Fizz 9 - Fire Ready Aim (Dart)

For this Fizz I choose one of the most recent languages: Google's Dart.  While trolling Google Plus I found this solution by Yosuke Sato.

// fizz buzz
main() {
  for(int i=0;i++<100;)
    print((i%3==0?"Fizz":"")+(i%5==0?"Buzz":"")||i);
}

This is a fairly dense rendering of FizzBuzz and gets right to the point without much ceremony: one loop, one single print statement, and a minimum of braces and parenthesis based on operator order of precedence.

Things get interesting when we encounter the short-circuit or operator.  On the left we have a string type, and on the right we have an integer type.  Java would reject this out of hand because short-circuit logical operations can be applied only to boolean primitive types.  Dart, however, has more in common with JavaScript, and uses an entirely different approach.  First the left hand side is evaluated, and what matters is if it is false-equivilant value:  false, null, zero, or the empty string.  The && operator will return the left side if it is negative, and the || operator will return the right hand side if the left is negative.  With boolean values you get simple solutions.  With string and integer types you get more interesting uses.  Such as using || to resolve defaults and the && operator to null-check complex objects.

As an aside, the dartlang.org sample compiler will refuse to run this FizzBuzz in checked mode.  In unchecked mode it will complain about the types.  Perhaps it does have more in common with Java than I realized at first.

Thursday, January 26, 2012

#8 - Do while I'm doing

Now that we have examined the while loop in C style languages, it's time to consider the while loops delinquent little brother: the do-while loop.  This is a fairly unique control structure that requires a keyword both at the beginning and the end of it's structure.  Kind of like the try-catch clause, except that you only try once but you do the loop at least once, and then consider whether you continue or not.  This does have one slight advantage in readability:  if you decide not to continue you are right at the code block you will evaluate next.

public class FizzBuzz08 { 
  public static void main(String[] args) { 
    int i = 1; 
    do {
      if ((i % 3 == 0) && (i % 5 == 0)) { 
        System.out.println("FizzBuzz"); 
      } else if (i % 5 == 0) { 
        System.out.println("Buzz"); 
      } else if (i % 3 == 0) { 
        System.out.println("Fizz"); 
      } else { 
        System.out.println(i); 
      } 
    } while (i++ < 100); 
  } 
}

This code isn't dramatically different from the previous entry where the while loop was considered.  The body is still on lines 5 through 13, and the first expression is on line 3.

The differences come in the second and third expression.  I combined both of them on line 14 for stylistic reasons.  First, the order of the expressions would not have been maintained since the increment would occur before the test.  I then moved the post increment into the while test expression so we can use the less than operator instead of the less than and equal.  One less keystroke.  Although since I am programming in Java I don't know why I worry about minimizing keystrokes.

This loop is not a direct decomposition of a for loop.  The loop body will always be evaluated once regardless of the truth of the expression.  So this is not a good case of the always evaluate logic.  So if a do-while smells like a simple while, typical developers can code it correctly.  However whether they can use the always evaluate aspect correctly is up for debate.

Tuesday, January 24, 2012

#7 - Decomposed Loop

It's hard to take a look at a programming solution to FizzBuzz from an absolute ground state.  There are at least three concepts that need to be working at a basic level for a solution to be sensible: repetition, decisions, and calculation.  To analyze any of those three aspects you need two of them standing fairly unchanged while one of them is decomposed.

First I shall decompose the nature of the solution by changing the basic ways a loop can be constructed.    Given the prevalence of C and Java as arguably the most popular language in programming language for over a quarter century the three expression for loop is something that any professional or accomplished amateur should understand instinctively.  But what does that three expression loop look like when decomposed in a semantically similar fashion??


public class FizzBuzz07 {
  public static void main(String[] args) {
    int i = 1;
    while (i <= 100) {
      if ((i % 3 == 0) && (i % 5 == 0)) {
        System.out.println("FizzBuzz");
      } else if (i % 5 == 0) {
        System.out.println("Buzz");
      } else if (i % 3 == 0) {
        System.out.println("Fizz");
      } else {
        System.out.println(i);
      }
      i++;
    }
  }
}

The three expression for loop actually has four parts.  The part that often gets ignored is the loop body, expressed by lines 5 through 13 and is not counted in the three expressions.  Since C and Java have zero based arrays, we could call this the zeroth expression.

The first expression sets initial values and variables and is seen in line 3.  Strictly speaking this is not a proper decomposition since the scope of the variable in this decomposition could extend beyond the loop body, if there were expressions other than the loop.  The second expression is a test, and is found inside the while expression on line 4.  The last expression is found on line 14, executed after the content of the body.

As an aside, the last entry on Ceylon didn't feature a three expression loop because Ceylon doesn't support the syntax.  That was the position Groovy once took but later relented when it added the "classic for loop" in it's 1.5 release.  However, Ceylon and Groovy both have a while loop construct.  So by applying the FizzBuzz Hypothesis we can see that programmers don't need a nice neat for loop expression.  But it sure looks prettier with one.

Thursday, January 19, 2012

Fizz 6 - This or That (Ceylon)

Ceylon is a new JVM language being created by Red Hat and Gavin King.  You may recognize that last name. Gavin also created Hibernate, a data library that underlies many e-commerce sites and is integrated (at the default option) into Grails.  Ceylon puts a lot of emphasis into how it handles types, so it seemed like a natural language feature to abuse.

interface Fizz {}
interface Buzz {}

class CFizz() satisfies Fizz {
  shared actual String string = "Fizz";
}

class CBuzz() satisfies Buzz {
  shared actual String string = "Buzz";
}

class CFizzBuzz() satisfies Fizz & Buzz {
  shared actual String string = "FizzBuzz";
}

Fizz|Buzz|Natural fizzIt(Natural i) {
  if ((i % 3 == 0) && (i % 5 == 0)) {
    return CFizzBuzz();
  } else if (i % 5 == 0) {
    return CBuzz();
  } else if (i % 3 == 0) {
    return CFizz();
  } else {
    return i;
  }
}

shared void FizzBuzz06() {
  for (i in 1..100) {
    print(fizzIt(i).string);
  }
}

The particular typing feature I am using is called "Union Types."  When you declare a type as TypeA|TypeB (note the pipe between the two types) you are telling the Ceylon compiler that you will have either TypeA or TypeB, it doesn't matter.  And you won't have TypeC (for this example TypeC is not a TypeA or TypeB).  Without this construct I would be forced to declare the return type of fizzIt to be an Object and hope no stray classes like Klang shows up.

There also exists Intersection Types (TypeA&TypeB) which means that the type is both of TypeA and TypeB without having to create some other interface that joins the two. Instead of createing a new interface RunnableFuture<V> you would just have Runnable&Future<V> without the need for a third class. Throw in stuff like RunnableScheduledFuture<V> which could have been declared as Runnable&Delayed&Future<V> and the code savings start piling up.

Tuesday, January 17, 2012

Buzz 5 - The FizzBuzz Hypothesis

For the Buzz entries I intend to write something more involved. These entries will have a FizzBuzz solution, but the text will only be about FizzBuzz. And if you check various dictionaries the act of talking 'about' FizzBuzz gives me a lot of latitude to talk about practically anything tangentially related.

Today, however, I intend to stay fairly close to FizzBuzz itself. What I want to talk about is something I will call "The FizzBuzz Hypothesis:"
Given a particular language feature or programming technique, if it cannot be shown as an integral part of a FizzBuzz solution then the typical programmers will not be able to use it correctly.
This statement is worth deconstructing from multiple angles. First there is the logical structure of the hypothesis:
¬r → ¬q
where r is the ability to express the programming language feature or technique in the form of FizzBuzz and q is typical programmers using it correctly. This also implies something by negation. If typical programmers are using a language feature correctly then there must be some way to make it integral to a FizzBuzz solution, and if it can be proven that there is no such FizzBuzz solution then clearly the typical programmer isn't using it correctly, all other evidence notwithstanding. Also note the word choice here. I did not say properly or effectively, I said correctly. There are proper and effective ways to do things that are not correct. I am reminded of this every day I watch my children do chores around the house.

There is also the question of what I mean by the typical programmer. Since there is a high amount of variability on the high end of the "mean average programmer" the mean pulls up the average such that more than half of the programmers are less than average. There is also the possibility of a "median" programmer, where half the programmers are better or worse. This too has its faults, because that means that half of the programmers may not be able to even program a FizzBuzz solution. Given a large enough sample set that may be true, but I don't think we are talking about anyone who has sat through a LOGO class in elementary school or hand coded some HTML. When I say "typical programmer" I mean someone within one or two standard deviation of the mean. I am also assuming that programming ability is a Poisson distribution. (I think I've just demonstrated everything I can remember from one semester of college statistics for technical majors.)

Now why do I express the law as a double negative implication? I blame the self-esteem driven coddling I received in public schooling. When you are failing you are "not succeeding" and when you are rebelling you are "not conforming." Everything is expressed as the desired outcome, and rather than using an antonym the desired word is used, with a negation in front of it. As a good Computer Science major I spent a few weeks in propositional logic. This math subset has a lot of theorems. And one of them is is Transposition, where we can swap the order of the implication as long as we negate both sides. Taking a desired statement, and adding two negations and still have it mean something is really cool.

This them begs the question, if a typical programmer is using a language feature or pattern correctly then it can be expressed as a fundamental part of a FizzBuzz solution then why don't I say it like that? The problem is we start with the hypothetical typical programmer. Next, we would need to see them use the language feature or pattern correctly. And only then can we conclude an integral FizzBuzz solution exists. I don't like this formulation because we start with end results looking backwards rather than a prediction looking forward. We would start with real programmers correctly using real technologies and concluding something arbitrary and contrived. But if we start with something arbitrary and contrived we can project onto real programmers and real situations without waiting for those real situations to occur. Much like concluding that a ball will hit the ground without dropping it. This is especially useful for technologies that have not seen widespread use. By starting with the technology we can then use this hypothesis as a lens to examine potential technologies a priori rather than as a post mortem.

The reason I came to formulating this hypothesis is because of the depths of thinking I went to while contemplating the various parts of this project. Part of that was reflecting on why it was a good interview question for testing programming skills. Not design, engineering, or architecture skills, but programming skills in the raw. It's a bit like the NFL combine. Before players are drafted by professional teams the teams get all of the top candidates together and test basic skills. How fast can you run, how much can you bench press. Let’s see you catch balls, see you throw balls, and see how smart are you. (No kidding, the NFL sits them down for an IQ test. And offensive tackles tend to be smarter than the quarterbacks, and way smarter than the wide receivers.)

But what makes FizzBuzz a good proxy for programming aptitude? FizzBuzz has three key aspects to most solutions: repetition, calculation, and decision. And these three aspects pretty much sums up most of what programming is about. There are some exceptions, and most of those interactions are hidden behind APIs calls. So if a programming language feature or pattern doesn't help you repeat, calculate, or decide, what good is it for programming?

For this entry I am going to use the FizzBuzz Hypothesis to answer a question that has bothered me since the Java programming language has been released: why is there both a short circuted and fully evaluated boolean operator in the Java Programming Language? And can you use both meaningfully?

public class FizzBuzz05 {

  static boolean lessThan100(int val) {
    return val < 100;
  }

  static boolean printNumber(int val) {
    System.out.print(val);
    return true;
  }

  static boolean maybeFizz(int val) {
    if (val % 3 == 0) {
      System.out.print("Fizz");
      return true;
    } else {
      return false;
    }
  }

  static boolean maybeBuzz(int val) {
    if (val % 5 == 0) {
      System.out.print("Buzz");
      return true;
    } else {
      return false;
    }
  }

  public static void main(String[] a) {
    int num = 0;
    while (lessThan100(num++) &&
      maybeFizz(num) | maybeBuzz(num) || printNumber(num)) {
      System.out.println();
    }
  }

}

Most of this solution is spent writing a method that makes the key point more readable. There are four different methods that do four separate things required by the solution. One method tests if the number is less than one hundred. One method prints out the number that is passed in. One method when passed in a number divisible by three prints out "Fizz." And there is one last helper method that does the same as the last, except testing for 5 and printing "Buzz." If the Fizz or Buzz methods print out a value, then they return true. If no value was printed, false is returned. None of these helper methods print a new line; that will be the task of the main method. You may be wondering where the helper method is that prints out "FizzBuzz". The reason we don’t need one is the point of this particular exercise.

The magic happens in line 33, a group of three of the helper methods joined by two different boolean or operators. The first one is the fully evaluated or "bitwise" version and the other is the short circuited or "logical" version. According to operator precedence we work with the bitwise operator and work that one first. When going through the loop both sides of this operator will be evaluated, regardless of the results. So in the cases where we have a number evenly divisible by three and five we will get both sides of the expression evaluated, even though we know after fizz that the result will be true.

The second operator, of lower precedence, is the logical or short circuit operator. If either of the methods on the left hand side had printed out their FizzBuzz value then we would be getting a true result on the left side. By short circuit rule we would not evaluate the right hand side and no value would have been printed. This is a good thing, because the method will always print a number regardless of what it is. If we print out Fizz or Buzz or FizzBuzz we are not supposed to print out a number at all. But if neither of the methods return true and no other values have been printed out then we need to print out the number. Since the left hand side is false in those cases the right hand side is evaluated. And as a side effect of the evaluation the number is printed.

So there, in one single expression, we have both a fully evaluated and short circuited logical or operator. It looks like typical developers can use this correctly.

Thursday, January 12, 2012

#4 - Wrap the Math in a Method

Sometimes I think I was born to program, other times I think it's a giant cosmic coincidence.  When I was in  fifth grade my school got lucky and someone donated 15 VIC-20 computers complete with cheapo CRTs. Because of this all of the fifth graders learned how to program basic that year.  All of the fifth graders, not just the nerds.  In junior high school there was a computer elective as well, which I took at the earliest possible time.  Then when I got into high school I was in for a rude shock:  you need to be a Junior to take a computer programming class.  Two whole years without official credit for goofing off on a computer.  What was more awesome was that it was an honest to goodness programming class instead of that survey class I had in junior high.

So I did what any other socially awkward nerd would do: I asked the teacher if I could get an exception.  And I got that exception, and took the class the second semester.  The class was well within my capabilities as I had to endure complaints from other students that I was a curve buster with my 105% score in the class (when adding in extra credit).  It was the only time I have ever been accused of "busting the curve."  But it wasn't all ice cream and lollipops.  The teacher didn't always like the way I coded the solutions, particularly the fact I never used procedures.  My programs were all one long stream of instructions.  Just like a VIC-20 basic program, except there were no line numbers.  My thinking was if you are only going to call a procedure at one point in the code then why type all those extra keystrokes?  Mr. Shepard was not impressed.

public class FizzBuzz04 {

  public static void main(String[] args) {
    for (int i = 1; i <= 100; i++) {
      System.out.println(theValue(i));
    }
  }

  public static String theValue(int i) {
    if ((i % 3 == 0) && (i % 5 == 0)) {
      return "FizzBuzz";
    } else if (i % 5 == 0) {
      return "Buzz";
    } else if (i % 3 == 0) {
      return "Fizz";
    } else {
      return Integer.toString(i);
    }
  }
  
}

I hope Mr. Shepard is impressed now.  This actually does, believe it or not, improve the readability and maintainability of the code.  It pulls out the biggest third of the problem (doing ugly math) and keeps the other two thirds (counting to one hundred and printing out stuff) in a nice neat package.

In the main method the function it calls is a wondrous and magical black box.  Data goes in, answers come out. This is a fundamental abstraction that actually allows a lot of magical code to work.  Consider encryption.  Do you know about congruence in number theory?  What?  Numbers have theories?!  And what's that about the Chinese remainders?  Don't know, and since I have a procedure I can call I don't care.

It's magic.

Tuesday, January 10, 2012

Fizz 3 - Elvis Has Left the Building (Groovy)

Whenever I count "Fizz" in this series I will examine a language that has yet to be examined before. There is no shortage of candidates but the trick will be to keep the languages choices relevant and readily verifyable (this could be tricky).  Ideally I will be able to consider a feature that is relatively unique to that language or family of languages.

For this post I will examine the Groovy programming language.  Picking a relatively unique feature for Groovy is a fairly hard prospect since it tries to pull all the best parts from all other languages.  It is based on Java, so it's a C like curly brace language.  It compiles to JVM byte code.  It is object oriented, but strives to delay it's method dispatch as late as possible, enabling multiple dispatch method invocations as seen in Common Lisp.  It uses closure like blocks much like you would see in Ruby.

There are a lot of neat tricks in Groovy so I see myself coming back to this language later in this series.  But perhaps the most unique feature of Groovy, or the one feature that it has gone the furthest to popularize, then it would be the "Elvis Operator:" ?: a C style ternary operator with the middle operand removed.

for (int i = 1; i <= 100; i++) {
  String answer = ""

  if (i%3 == 0) {
    answer += "Fizz"
  }

  if (i%5 == 0) {
    answer += "Buzz"
  }
  
  println answer ?: i
}

This isn't the most idiomatic Groovy code for this solution. It is intended to demonstrate just the Elvis operator with all other awesomeness removed.  I have a three statement solution that shows other Groovy features such as blocks and ranges. But for the purpose of this post we should focus just on the unique feature. There, on line 12 of the verbosely expressed code, is the Elvis operator. Why is it called Elvis? If you rotate it clockwise the question mark kind of forms Elvis Presley's hair just above his eyes.

But what does it do?  It clearly has no hips to shake suggestively since he is being expressed from the nose up.  Elvis picks the first "true" item it sees and returns only that item.  Mode technically, the left hand side of the operator is evaluated for "groovy truth," and if it returns negative (null, false, zero, or empty string in most cases) then the right hand side of the operator is returned. If the left had side matches any other value, then the left hand side of the operator is returned.

This roughly equates to the C style statement x ? x : y. If the middle operator leaves the building, along with the white space, you are left with the Elvis operator: x ?: y. Even though Elvis has left the building, his legacy remains.

Thursday, January 5, 2012

#2 - Is That Your Final Answer?

When it comes to minor tweaks in the presentation of the problem, there is more than one way to make "the smallest change." Rather than printing out the result immediately we can defer the printing and keep an answer in a variable, changing it as needed.

public class FizzBuzz02 {
 public static void main(String[] args) {
  for (int i = 1; i <= 100; i++) {
   String answer = Integer.toString(i);
   if (i % 3 == 0) {
     answer = "Fizz";
   }
   if (i % 5 == 0) {
     answer = "Buzz";
   }
   if ((i % 3 == 0) && (i % 5 == 0)) {
     answer = "FizzBuzz";
   }
   System.out.println(answer);
  }
 }
}

This example allows two important changes, actually. The first is the introduction of a variable, and the changing of the variable Once we are done deciding what the result should be we can then print out the result of the variable.

The second important change is that we can consider each condition on its own.  Since the most general cases are considered first and then the most specific are considered later.  Since the most specific one is considered last, it can overwrite the previous answer.  When you add these two items together, you can see that the variable will be set once, twice, or four times.  Never three.

Another way to think of this is a game show.  Rather than playing Jeopardy, where only the first answer given is accepted, we are playing Who Wants to Be a Millionaire, where the last answer given is accepted.  Contestants routinely change their answers but the only answer that matters is the last answer.

Tuesday, January 3, 2012

#1 - Common But Boring

Over the next year or so I intend on blogging 100 solutions to the FizzBuzz problem.  Each solution will vary in either technique or language, sometimes both.  The various "FizzBuzz" posts will also have various themes based on where the number lands.  The "number" days will simply be a solution with the prose around it focusing on the solution itself.

To start things off I thought it was best to focus on one of the more common answers.  This solution will be written in Java, which as of this writing was the #1 language on the TIOBE index in December of 2011.  This is merely evidence that it one of the most common languages.

public class FizzBuzz01 {
 public static void main(String[] args) {
  for (int i = 1; i <= 100; i++) {
   if ((i % 3 == 0) && (i % 5 == 0)) {
    System.out.println("FizzBuzz");
   } else if (i % 5 == 0) {
    System.out.println("Buzz");
   } else if (i % 3 == 0) {
    System.out.println("Fizz");
   } else {
    System.out.println(i);
   }
  }
 }
}

This is not a perfectly straightforward translation of the problem statement into a solution.  Without a lot of preparatory code you cannot directly translate the problem statement into code in the order it is presented in the problem statement.

This sample is about as simple as it can be done in Java. The only portion worth commenting on is how it transcribes the solution. Rather than going in the order the clauses are stated in the problem statement we consider the conditions from the last one first.  This changes it from a set of  "except" statements into a series of simpler if-then-else statements.

This is of the more common solutions (only considering correct solutions) presented by job candidates when asked this question in a job interview.  It is also one of the most boring solutions.