The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

Monday, June 08, 2020

I can code that FizzBuzz function with only two tests

My favorite implementation of FizzBuzz is the Ruby version based upon nothing more than lambda calculus and Church numbers, i.e. nothing but functions all the way down.

Then I saw an interesting version of it in the presentation “Clean Coders Hate What Happens to Your Code When You Use These Enterprise Programming Tricks.” The normal implementation usually involves thee tests, one for divisibility by 3, one for divisibility by 5, and an annoyingly extra one for both or for divisibility by 15. But the version given in the presentation only had two tests. Here's a version of that in Lua:

function fizzbuzz(n)
  local test = function(d,s,x)
    return n % d == 0 
       and function(_) return s .. x('') end
        or x
  end
  
  local fizz = function(x) return test(3,'Fizz',x) end
  local buzz = function(x) return test(5,'Buzz',x) end
  
  return fizz(buzz(function(x) return x end))(tostring(n))
end
  	 
for i = 1 , 100 do
  print(i,fizzbuzz(i))
end

The function test() will return a new function that returns a string, or whatever was passed in x. fizz() and buzz() are functions that return what test() returns. The last line can be broken down into the following statements:

_0 = function(x) return x end
_1 = buzz(_0)
_2 = fizz(_1)
_3 = _2(tostring(n))	
return _3

And we can see how this works by following a few runs through the code. Let's first start with a number that is not divisible by 3 or 5, say, 1.

_0 = function(x) return x end
_1 = buzz(_0) = function(x) return x end
_2 = fizz(_1) = function(x) return x end
_3 = _2("1") == "1"
return _3	

_0 is the identity function—just return whatever it is given. buzz() is called, which calls test(), but since the number is not divisible by 5, test() returns the passed in identity function, which in turn is returned by buzz(). fizz() is then called, and again, since the number is not divisible by 3, _test() returns the identity function, which is returned by fizz(). _3 is the result of the identity function called with “1”, which results in the string “1”.

Next, the number 3 is passed in.

_0 = function(x) return x end
_1 = buzz(_0) = function(x) return x end
_2 = fizz(_1) = function(_) return 'Fizz' .. _1('') end
_3 = _2("3") == 'Fizz'
return _3	

_0 is the identify function. buzz() just returns it since 3 isn't divisible by 5. fizz(), however, returns a new function, one that returns the string “Fizz” concatenated with the empty string as returned by the identify function. This function is then called, which results in the string “Fizz”.

The number 5 works similarly:

_0 = function(x) return x end
_1 = buzz(_0) = function(_) return 'Buzz' .. _0('') end
_2 = fizz(_1) = function(_) return 'Buzz' .. _0('') end
_3 = _2("5") == 'Buzz'
return _3

Here, buzz() returns a new function which returns the string “Buzz” concatenated with the empty string returned by the identify function. fizz() returns the function generated by buzz() since 5 isn't divisible by 3, and thus we end up with the string “Buzz”.

It's the case with 15 where all this mucking about with the identify function is clarified.

_0 = function(x) return x end
_1 = buzz(_0) = function(_) return 'Buzz' .. _0('') end
_2 =_fizz(_1) = function(_) return 'Fizz' .. _1('') end
_3 = _2("15") = 'FizzBuzz'
return _3

Again, _0 is the identify function. buzz() returns a new function because 15 is divisible by 5, and this function returns the string “Buzz” concatenated by the empty string returned by the identity function. fizz() also returns a new function, because 15 is also divisible by 3. This function returns the string “Fizz”, concatenated by the passed in function, which in this case is not the identity function, but the function returned from buzz(). This final function returns “Fizz” concatenated with the string of the function that returns “Buzz” concatenated with the empty string returned by the identity function, resulting in the string “FizzBuzz”.

Yes, it's quite a bit of work just to avoid an extra test, but fear not! Here's a way to do FizzBuzz with just two tests that is vastly simpler:

function fizzbuzz(n)
  local list = { 'Fizz' , 'Buzz' , 'FizzBuzz' }
  list[0]    = tostring(n)
  
  local m = (n % 3 == 0 and 1 or 0)
          + (n % 5 == 0 and 2 or 0)
  return list[m]
end

for i = 1 , 100 do
  print(i,fizzbuzz(i))
end

Here we generate an index into an array of four possible responses, the original number as a string, “Fizz”, “Buzz” and “FizzBuzz”. If the number isn't divisible by either 3 or 5, the index is 0; if it's divisible by 3, the index is 1, if divisible by 5, the index is 2, and if both, the index ends up as 3. It's not quite as mind blowing as the first version, but it is easier to translate to a language that lacks closures, like C.

Obligatory Picture

[It's the most wonderful time of the year!]

Obligatory Contact Info

Obligatory Feeds

Obligatory Links

Obligatory Miscellaneous

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: http://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

http://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.

Copyright © 1999-2020 by Sean Conner. All Rights Reserved.