The Boston Diaries

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.

Monday, June 08, 2020

I can code that FizzBuzz function with only two tests

Obligatory Picture

Obligatory Contact Info

Obligatory Feeds

Obligatory Links

Obligatory Miscellaneous