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.
